prime divisors
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Let $p$ be an odd prime.Prove $p^{p}-1$ has at least one prime divisor of the form $kp+1$
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: prime divisors
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?
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?
বড় ভালবাসি তোমায়,মা
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: prime divisors
${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$
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$
Re: prime divisors
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 ])
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: prime divisors
Yeah, and it directly kills SL-2006-N5. And this very problem(and a little গুতানি from Masum vai ) motivated me to learn about cyclotomic polynomials.
বড় ভালবাসি তোমায়,মা
Re: prime divisors
I think this can be done without using any sledgehammers too. May be BY Exponent GCD Lemma
One one thing is neutral in the universe, that is $0$.