Author |
Topic: My thoughts on IMO 2003 / 6 (Read 2169 times) |
|
anonymous
Guest
|
Conjecture: Suppose that x^p=p(mod q) has a solution, then x^p=p(mod q) has a solution x=a such that |a|<p
I cannot prove this conjecture yet and I don't know if this conjecture is true, but I can prove IMO 2003 problem 6 using this conjecture.
Proof:
suppose on the contrary that for every prime number q, n^p=p(mod q) has a solution, by lemma we may consider all solutions where |n|<p, by pigeonhole principle, there exist integer a in (-p,p) such that a^p-p=0(mod q) for infinitely many prime q, this is a contradiction because a^p-p is finite, it cannot have infinitely many prime divisors
|
|
 IP Logged |
|
|
|
anonymous
Guest
|
 |
Re: My thoughts on IMO 2003 / 6
« Reply #1 on: Jul 26th, 2003, 4:08pm » |
 Quote  Modify
 Remove
|
Here is another thought: this proof use the fact that p^p-1 contain a prime divisor q such that q-1 is not divisible by p^2, which I still haven't found a proof, therefore this proof is uncomplete
let q be a prime divisor of p^p-1 such that q-1 is not divisible by p^2, then I claim that n^p-p is not divisible by q for all integer n
proof by contradiction:
assume on the contrary q is a prime, p^p=1(mod q), q-1 is not divisible by p^2 and there exist n such that n^p=p(mod q)
from p^p=1(mod q) we note that the order of p modulus q is p, so we have these two collorary:
(1) every prime divisor of p^p-1 is of the form kp+1
(2) for all a such that p^a=1(mod q), we must have p|a
by Fermat Small Theorem,we have n^(q-1)=1(mod q)
by collorary (1) we may write q=kp+1
we have n^q=(n^p)^k=p^k=1(mod q)
therefore by collorary (2) we have p|k =>q-1=kp is divisible by p^2, a contradiction
|
|
IP Logged |
|
|
|
anonymous
Guest
|
|
Re: My thoughts on IMO 2003 / 6
« Reply #2 on: Jul 27th, 2003, 4:51am » |
Quote Modify
Remove
|
I've finally found a solution.
Lemma 1: let q be a prime divisor of p^(p-1)+...+p+1, then q>p
proof by contradiction:
let q be a prime divisor
we have p^(p-1)+...+p+1=0(mod q), p^p=1(mod q)
assume on the contrary that p>=q
write p=kq+r, where k,r are integers and 0<=r<q
if r=0, then q|p, so p^(p-1)+...+p+1=1=0(mod q), a contradiction
if r=1, then p^(p-1)+...+p+1=1+1+...+1=p=0(mod q), a contradiction with p=kq+1
if r>1, then p^p=r^p=1(mod q)
let a be the order of r modulus q => r^a=1(mod q), a<q
then a|p, a<q => a=1 => r=1(mod q) => r=1, contradiction with r>1
Lemma 2: all prime divisors of p^(p-1)+...+p+1 are of the form kp+1
Proof:
let q be a prime divisor
we have p^p=1(mod q)
by Fermat Small Theorem, we have p^(q-1)=1(mod q)
since p is order of p modulus q, therefore p|(q-1) => q=kp+1 for some positive integer k
Lemma 3: p^(p-1)+...+p+1 contains a prime divisor q such that q-1 is not divisible by p^2
proof by contradiction:
by lemma 2, we may assume on the contrary that all prime divisors are of the form kp^2+1
we have
p^(p-1)+...+p+1
=product of prime of the form kp^2+1
=lp^2+1 (for some positive integer l)
contradiction
theorem: let p be a prime, there exist a prime q such that n^p-p is not divisible by q for all integer n
we choose q as a prime divisor of p^(p-1)+...+p+1 such that q-1 is not divisible by p^2, such a q exist because of lemma 3, now we use proof by contradiction to show that n^p-p is not divisible by q for all integer n
proof by contradiction:
assume that n^p=p(mod q) for some integer n
by Fermat small theorem, n^(q-1)=1(mod q)
write q=kp+1
on one hand, since we have chosen q such that q-1 is not divisible by p^2, therefore k is not divisible by q
on the other hand, n^(q-1)=(n^p)^k=p^k=1(mod q)
since p^p=1 (mod q), therefore p must be the order => p|k, a contradiction
|
|
IP Logged |
|
|
|
anonymous
Guest
|
|
Re: My thoughts on IMO 2003 / 6
« Reply #3 on: Jul 27th, 2003, 5:37am » |
Quote Modify
Remove
|
I left out an important lemma. This lemma plays an important role in the proof above.
Lemma: if p<q are primes and p^p=1(mod q), then the order of p modulus q is p
proof:
let a be the order of p modulus q
i.e. a is the smallest positive integer such that p^a=1(mod q)
since a is order and p^p=1(mod q), therefore a|p => a=1 or a=p
if a=1, then p=1(mod q), contradiction with p<q
therefore a=p, i.e. the order of p modulus q is p
|
|
IP Logged |
|
|
|
anonymous
Guest
|
|
Re: My thoughts on IMO 2003 / 6
« Reply #4 on: Aug 1st, 2003, 1:11am » |
Quote Modify
Remove
|
I can solved this problem because I have seen a similar problem in this book:
An Introduction To The Theory Of Numbers (Fifth Edition)
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery
The exercise on page 108, problem 36 from the book is similar to IMO 2003/6. Problem 36 ask for a proof that there are infinitely many primes in 1+m , 1+2m , 1+3m , ... The solution involved a study of prime divisors of m^m-1. I learn this trick and applied it on IMO 2003/6 by considering prime divisors of p^p-1.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
|
Re: My thoughts on IMO 2003 / 6
« Reply #5 on: Aug 1st, 2003, 2:33pm » |
Quote Modify
|
So Niven & Zuckerman invited a third author in for the 5th edition? Unfortunately, my 4th edition doesn't have exercises on page 108.
Actually, the only reason I'm posting is to let you know you haven't been talking to an empty room. I gave some thought to this one, but when you posted your solution I didn't have anything to add, and apparently no one else did either.
Good work!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print