Author 
Topic: My thoughts on IMO 2003 / 6 (Read 2128 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^pp=0(mod q) for infinitely many prime q, this is a contradiction because a^pp is finite, it cannot have infinitely many prime divisors


IP Logged 



anonymous
Guest


Re: My thoughts on IMO 2003 / 6
« Reply #1 on: Jul 26^{th}, 2003, 4:08pm » 
Quote Modify
Remove

Here is another thought: this proof use the fact that p^p1 contain a prime divisor q such that q1 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^p1 such that q1 is not divisible by p^2, then I claim that n^pp 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), q1 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^p1 is of the form kp+1 (2) for all a such that p^a=1(mod q), we must have pa by Fermat Small Theorem,we have n^(q1)=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 pk =>q1=kp is divisible by p^2, a contradiction


IP Logged 



anonymous
Guest


Re: My thoughts on IMO 2003 / 6
« Reply #2 on: Jul 27^{th}, 2003, 4:51am » 
Quote Modify
Remove

I've finally found a solution. Lemma 1: let q be a prime divisor of p^(p1)+...+p+1, then q>p proof by contradiction: let q be a prime divisor we have p^(p1)+...+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 qp, so p^(p1)+...+p+1=1=0(mod q), a contradiction if r=1, then p^(p1)+...+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 ap, a<q => a=1 => r=1(mod q) => r=1, contradiction with r>1 Lemma 2: all prime divisors of p^(p1)+...+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^(q1)=1(mod q) since p is order of p modulus q, therefore p(q1) => q=kp+1 for some positive integer k Lemma 3: p^(p1)+...+p+1 contains a prime divisor q such that q1 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^(p1)+...+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^pp is not divisible by q for all integer n we choose q as a prime divisor of p^(p1)+...+p+1 such that q1 is not divisible by p^2, such a q exist because of lemma 3, now we use proof by contradiction to show that n^pp 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^(q1)=1(mod q) write q=kp+1 on one hand, since we have chosen q such that q1 is not divisible by p^2, therefore k is not divisible by q on the other hand, n^(q1)=(n^p)^k=p^k=1(mod q) since p^p=1 (mod q), therefore p must be the order => pk, a contradiction


IP Logged 



anonymous
Guest


Re: My thoughts on IMO 2003 / 6
« Reply #3 on: Jul 27^{th}, 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 ap => 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 1^{st}, 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^m1. I learn this trick and applied it on IMO 2003/6 by considering prime divisors of p^p1.


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 1^{st}, 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



