Welcome to NRICH.

 
The Importance of Counterexamples
By Joanna Cheng (P2322) on Friday, June 15, 2001 - 07:51 am:

These are problems my maths teacher gave me for homework and I can't figure them out. I'm meant to say whether these are true or false, and give mathematical proof.

1. n2-n+17 is prime when n is a positive integer.

2. Every integer is the sum of 4 or less square numbers.

3. Every prime number larger than 2 can be expressed as the sum of a prime number and a power of 2.

Thanks,
Joanna

By Kerwin Hui (Kwkh2) on Friday, June 15, 2001 - 04:21 pm:

Joanna,

For question 1, a simple minded approach would be to look at some special number n. Can you see a good one to try (looking at the coeffients)?

For question 3, the brute-force approach would work. First, draw up your list of primes 2,3,5,... Now try each one in turn (this method is a bit slow but you will get to a counterexample). We can modify this process to make it work a bit faster:

Let p be a prime which is not a prime+a power of 2. What can you tell me about p-2,p-4 and p-8? Conclude that the largest prime less than p is at most p-6. Now look at your list and eliminate those primes that does not satify this criterion. Work through those. You should get a three digit prime as your minimal counterexample.

Question 2 is the well-known 4-square theorem. Its standard proof is long and involves advanced number theory. and quite involved.

Kerwin

By Michael Doré (Michael) on Friday, June 15, 2001 - 05:07 pm:

Q2 becomes a lot easier if we allow the integers to be negative... I think that must be the required interpretation; otherwise it would be way more difficult than 1 and 3. Now the reason they're all easy is because they're all false, so to disprove them you only need find one counterexample (i.e. one value of n for which the hypothesis fails).

1) Is n2 - n + 17 always prime?

To disprove this we need to find a value of n for which this number is not prime. Try n = 17. It now becomes:

172 - 17 + 17 = 172

Now 172 clearly isn't prime since it is a multiple of 17. So the assertion that n2 - n + 17 is always prime fails for n = 17, so it is false.

Can you adapt this method to show that if a,b are integers then n2 + an + b is not always prime?

2) Can every integer be expressed as the sum of 4 squares (or fewer)?

If you replace integer with positive integer then the answer is yes, but this is not easy to prove. However if we're allowed negative integers, then the assertion is clearly false.

If n = a2 + b2 + c2 + d2

then a2,b2,c2,d2³0 so n³0. Therefore the hypothesis is false for any negative integer n.

3) Can all prime numbers be written as a prime + a power of 2?

Try 127 (which is a prime) and see if it can be done.

The object of this is exercise I think is to be able to recognise assertions which are clearly wrong. Then you don't have to waste time trying to prove them. Counterexamples have an important role in mathematics, because they indicate when research is going in the wrong direction.

By Tom Hardcastle on Monday, June 18, 2001 - 03:17 pm:

For 3), 3 is a simpler counterexample. Note 1 is not a prime.

By Michael Doré on Monday, June 18, 2001 - 03:19 pm:

But 2 is a prime and 1 is a power of 2.

By Tom Hardcastle on Monday, June 18, 2001 - 07:00 pm:

Tch... I've been wrong a lot lately.