wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> My thoughts on IMO 2003 / 6
        
(Message started by: anonymous on Jul 23^rd, 2003, 10:36pm)

Title: My thoughts on IMO 2003 / 6
Post by anonymous on Jul 23^rd, 2003, 10:36pm

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

Title: Re: My thoughts on IMO 2003 / 6
Post by anonymous on Jul 26^th, 2003, 4:08pm

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

Title: Re: My thoughts on IMO 2003 / 6
Post by anonymous on Jul 27^th, 2003, 4:51am

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

Title: Re: My thoughts on IMO 2003 / 6
Post by anonymous on Jul 27^th, 2003, 5:37am

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

Title: Re: My thoughts on IMO 2003 / 6
Post by anonymous on Aug 1^st, 2003, 1:11am

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.

Title: Re: My thoughts on IMO 2003 / 6
Post by Icarus on Aug 1^st, 2003, 2:33pm

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!