IMO2003 problem B3

[eepiccolo]

Here is the sixth and last problem from the 44th International Mathematical Olympiad. The other five are posted also. I don't know the answers, but I'll be working on them when I get the chance.

B3. Show that for each prime p, there exists a prime q such that n^p - p is not divisible by q for any positive integer n.

(Oh boy, a problem involving primes!)

[AllPrimesAreOdd]

heres a solution that i hope is correct:

Assume the statement is not true.
ie THere exists a p prime such that for all q prime, there exists an n in the naturals such that q divides n^p - p.

since q divides n^p - p, n^p = p (mod q).
let q equal p, and choose n not a multiple of p.
thus, n^p = p (mod p), n not a multiple of p.
since n is not a multiple of p, (and n not equal to 0 because its in the naturals), n is not congruent to p modulo p.
thus, n^p is not conguent to n modulo p.
THus, p is not prime by the contrapositive of fermats little thm.
Contradiction!

Thus, the statement is true.

I have this gut feeling that I am dead wrong.

[wpolly]

Originally Posted by AllPrimesAreOdd

heres a solution that i hope is correct:

Assume the statement is not true.
ie THere exists a p prime such that for all q prime, there exists an n in the naturals such that q divides n^p - p.

since q divides n^p - p, n^p = p (mod q).
let q equal p, and choose n not a multiple of p.
thus, n^p = p (mod p), n not a multiple of p.
since n is not a multiple of p, (and n not equal to 0 because its in the naturals), n is not congruent to p modulo p.
thus, n^p is not conguent to n modulo p.
THus, p is not prime by the contrapositive of fermats little thm.
Contradiction!

Thus, the statement is true.

I have this gut feeling that I am dead wrong.

There EXISTS an n does not imply that n isn't a multiple of p.



Here is my solution:



We constuct a q satisfy the condition.
let S=(p^p-1)/(p-1),then all divisors of S must have the form kp+1.
Since S=p+1(mod p^2),we could choose a divisor q of S such that q=kp+1, p doesn't divide k.

Then we show that such a q satisfy the condition.
Assume that there is an n such that q|n^p-p
Then we have n^p=p(mod q)
So p^k=(n^p)^k=n^pk=n^(q-1)=1(mod q) (When q doesn't divide n)
or p=n^p=0(mod q) (When q divide n)(contradition since q|p and q>p)
Thus q must divide p^k-1.
but q|p^p-1
So we have q|(p^k-1,p^p-1)=p-1 (since p doesn't divide k so (p,k)=1)
CONTRADICTION.
Q. E. D.