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 Help Search Members Login 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 Notify of replies Send Topic Print
 Author Topic: My thoughts on IMO 2003 / 6  (Read 2128 times)
anonymous
Guest

 My thoughts on IMO 2003 / 6   « on: Jul 23rd, 2003, 10:36pm » Quote Modify 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

 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

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

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

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)

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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »