prime divisors

For discussing Olympiad Level Number Theory problems
User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh
prime divisors

Unread post by asif e elahi » Tue Feb 18, 2014 6:25 pm

Let $p$ be an odd prime.Prove $p^{p}-1$ has at least one prime divisor of the form $kp+1$

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: prime divisors

Unread post by Tahmid Hasan » Tue Feb 18, 2014 9:30 pm

By Zsigmondy's theorem $p^p-1$ has a prime divisor not dividing $p-1$[Check the exceptions, none works]. Let it be $q$.
Let $d=ord_qp$. So $p^d \equiv 1 \pmod q$. So $d|p \Rightarrow d=1,p$.
If $d=1$, then $q|p-1$, a contradiction!
So $d=p$. Now $d|\phi (q) \Rightarrow p|q-1 \Rightarrow q=kp+1$, done!
Err... anyone have a solution without using sledgehammers?
বড় ভালবাসি তোমায়,মা

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: prime divisors

Unread post by asif e elahi » Wed Feb 19, 2014 9:57 pm

${p}^{p}-1=(p-1)({p}^{p-1}+{p}^{p-2}..........p+1)$
Here gcd$(p-1,{p}^{p-1}+{p}^{p-2}..........p+1)=1$
Let $q$ be a prime divisor of ${p}^{p-1}+{p}^{p-2}..........p+1$
So $gcd(p-1,q)=1$
${p}^{p}\equiv 1(mod q)$
Again ${p}^{q-1}\equiv 1(mod q)$
or ${p}^{gcd(p,q-1)}\equiv 1(mod q)$
As $p$ is a prime,gcd$(p,q-1)=1$ or $p$
If gcd$(p,q-1)=1$,then $p\equiv 1(mod q)$
So $q$ divides $p-1$,but gcd$(p,q-1)=1$
That means gcd$(p,q-1)=p$
So $p$ divides $q-1$
This implies $q$ is of the for $kp+1$ :mrgreen:

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: prime divisors

Unread post by *Mahi* » Thu Feb 20, 2014 2:24 pm

Actually all of the divisors of $\frac {p^p-1}{p-1}$ will be congruent to $1 \bmod p$ (which comes directly from cyclotomic polynomials [Another sledgehammer :P ])
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: prime divisors

Unread post by Tahmid Hasan » Thu Feb 20, 2014 7:35 pm

Yeah, and it directly kills SL-2006-N5. And this very problem(and a little গুতানি from Masum vai :P ) motivated me to learn about cyclotomic polynomials.
বড় ভালবাসি তোমায়,মা

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: prime divisors

Unread post by Masum » Sun Mar 30, 2014 11:06 am

I think this can be done without using any sledgehammers too. May be BY Exponent GCD Lemma :P
One one thing is neutral in the universe, that is $0$.

Post Reply