wu :: forums
wu :: forums - My thoughts on IMO 2003 / 6

Welcome, Guest. Please Login or Register.
Aug 8th, 2022, 3:11pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Grimbal, Eigenray, SMQ, Icarus, william wu, towr)
   My thoughts on IMO 2003 / 6
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: My thoughts on IMO 2003 / 6  (Read 2128 times)
anonymous
Guest

Email

My thoughts on IMO 2003 / 6  
« on: Jul 23rd, 2003, 10:36pm »
Quote Quote Modify Modify Remove Remove

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

Email

Re: My thoughts on IMO 2003 / 6  
« Reply #1 on: Jul 26th, 2003, 4:08pm »
Quote Quote Modify Modify Remove 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

Email

Re: My thoughts on IMO 2003 / 6  
« Reply #2 on: Jul 27th, 2003, 4:51am »
Quote Quote Modify Modify Remove 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

Email

Re: My thoughts on IMO 2003 / 6  
« Reply #3 on: Jul 27th, 2003, 5:37am »
Quote Quote Modify Modify Remove 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

Email

Re: My thoughts on IMO 2003 / 6  
« Reply #4 on: Aug 1st, 2003, 1:11am »
Quote Quote Modify Modify Remove 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: male
Posts: 4863
Re: My thoughts on IMO 2003 / 6  
« Reply #5 on: Aug 1st, 2003, 2:33pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board