September 03, 2006

Simple but satisfying

Hypothesis: If (n - 1) and (n + 1) are both prime (i.e. they form a "prime pair") and n is greater than 6, then n²(n² + 16) is divisible by 720.

True or false? Proof, please.

(Thanks go to Ani).

(Here's some more about primes and prime pairs).

7 comments:

Suresh said...

not the most elegant, but here goes.

Let M = n^2(n^2 + 16).

1. if n > 2 then n must be even (n-1/n+1 are both prime, and therefore are odd).

2. if n > 5, then n must be divisible by 3 (of the triple n-1, n, n+1, exactly one must divide 3, and the other two are prime).

3. If n > 6, n must be either 5k+2 or 5k-2 for some k (same reason as in (2))

therefore, n^2 is divisible by 4, n^2+16 is divisible by 4 (from 1.) and therefore 16 divides M.

n^2 is divisible by 9, and so 9 divides M. (from 2.)

(5k+2)^2 = 5( some terms) + 4, and so n^2+16 is 5(some terms) + 20 which is divisible by 5 (same holds for 5k-2)

so M is divisible by 5. (from 3.)

therefore M is divisible by 16 * 9 * 5 = 720.

QED.

gaddeswarup said...

Never liked number theory; but even I can do it. First n is even and divisible by 3 since one of three successive numbers is divisible by 3 and the other two are not. Since we are squaring and since n^2+16 is also divisible by 4, 144 divides the given number. Now n must be of the form 5k+2 or 5k+3 if it is not divisible by 5. So n^2+16 is divisible by 5. But, what is the point about this question?

b. said...

dilip,
welcome back. a delight to read you, as always.

here's one for you. consider non-zero numbers of the form 231*a + 3250*b, where a and b are integers. What is the smallest such number? How about numbers of the form 231*a + 2750*b?

Extension: What about sqrt(2)*a + 231*b? How small can you make it?

Dilip D'Souza said...

Thanks Suresh. Of course, n could also be 5k for some k (which much more trivially makes M divisible by 5).

Thanks Swarup too -- there's no point really, it's just that I like figuring out little problems like this from time to time just to keep the grey cells churning!

b, thanks! It's good to be back. I'm a little puzzled by your problem, am I missing something? Because surely the smallest number of the form 231*a + 3250*b, assuming you mean positive numbers, is when you have a = b = 1, which gives us 3481. (Similarly for the others).

Did you mean something else?

b. said...

dilip,
a and b can be negative, if necessary. thus, the smallest non-zero positive number of the type 3a + 10b is 1, obtained, for example, when a = -3, b = 1.

the "extension" problem came up in a discussion yesterday. thought it was a nice coincidence that you put up a prime-number problem this morning.

b.

sbrk said...

This follows as a consequence of Euclid's algorithm (the one used to find the GCD -- greatest common divisor of two integers). Any multiple of the gcd(m,n) can be written as am + bn, where a,b are integers. So the smallest in both of the integer cases will be the gcd of the sets of numbers that you have given.

The gcd of 231 and 3250 is 1. So 1 is the smallest positive number of the form 231a + 3250b.

The gcd of 231 and 2750 is 11. So the smallest positive number of the form 231a + 2750b is 11.

Since sqrt(2) is irrational, one can show (somewhat tediously) that we can produce arbitrarily small positive numbers (but not zero) of the form sqrt(2)a + 231b.

gaddeswarup said...

Dilip,
I just meant that mathematics is full of this kind of gymnastics and there may be other interesting ones like Simpson's Paradox which are 'useful' and challenging.
Swarup