Existence of a prime factor>p

For discussing Olympiad Level Number Theory problems
AourkoPChakraborty
Posts:3
Joined:Tue Feb 09, 2021 5:23 pm
Existence of a prime factor>p

Unread post by AourkoPChakraborty » Fri Feb 12, 2021 4:59 pm

Prove that if $p$ is a prime, then $p^p-1$ has a prime factor, greater than $p.$ :D

~Aurn0b~
Posts:46
Joined:Thu Dec 03, 2020 8:30 pm

Re: Existence of a prime factor>p

Unread post by ~Aurn0b~ » Sun Feb 14, 2021 11:36 am

AourkoPChakraborty wrote:
Fri Feb 12, 2021 4:59 pm
Prove that if $p$ is a prime, then $p^p-1$ has a prime factor, greater than $p.$ :D
$p^p-1=(p-1)(p^{p-1}+p^{p-2}+\cdots+1)$
Now let $q$ be a prime factor of $p^p-1$ such that $q\nmid p-1$. This prime divisor obviously exists because if a prime factor of $p^p-1$, let it be $r$,divides $p-1$, then we have $p^{p-1}+p^{p-2}+\cdots+1\equiv1^{p-1}+1^{p-2}+\cdots+1\equiv p\equiv 1\pmod{r}$, and so $q$ is a prime divisor of $p^{p-1}+p^{p-2}+\cdots+1$
Let, $x=\text{ord}_q(p)$, and we know that $p^p\equiv 1\pmod{q}\Rightarrow x\mid p\Rightarrow x=1,p$
As $q\nmid p-1,\Rightarrow x\neq 1\Rightarrow x=p$
From fermats little theorem, $p^{q-1}\equiv 1\pmod{q}$
So, $p\mid q-1\Rightarrow q>p.\blacksquare$

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Existence of a prime factor>p

Unread post by Asif Hossain » Sat Feb 27, 2021 12:35 pm

~Aurn0b~ wrote:
Sun Feb 14, 2021 11:36 am
AourkoPChakraborty wrote:
Fri Feb 12, 2021 4:59 pm
Prove that if $p$ is a prime, then $p^p-1$ has a prime factor, greater than $p.$ :D
$p^p-1=(p-1)(p^{p-1}+p^{p-2}+\cdots+1)$
Now let $q$ be a prime factor of $p^p-1$ such that $q\nmid p-1$. This prime divisor obviously exists because if a prime factor of $p^p-1$, let it be $r$,divides $p-1$, then we have $p^{p-1}+p^{p-2}+\cdots+1\equiv1^{p-1}+1^{p-2}+\cdots+1\equiv p\equiv 1\pmod{r}$, and so $q$ is a prime divisor of $p^{p-1}+p^{p-2}+\cdots+1$
Let, $x=\text{ord}_q(p)$, and we know that $p^p\equiv 1\pmod{q}\Rightarrow x\mid p\Rightarrow x=1,p$
As $q\nmid p-1,\Rightarrow x\neq 1\Rightarrow x=p$
From fermats little theorem, $p^{q-1}\equiv 1\pmod{q}$
So, $p\mid q-1\Rightarrow q>p.\blacksquare$
What does this mean $x=\text{ord}_q(p)$
Hmm..Hammer...Treat everything as nail

Dustan
Posts:71
Joined:Mon Aug 17, 2020 10:02 pm

Re: Existence of a prime factor>p

Unread post by Dustan » Sat Feb 27, 2021 12:51 pm

:D :D Google 😀

~Aurn0b~
Posts:46
Joined:Thu Dec 03, 2020 8:30 pm

Re: Existence of a prime factor>p

Unread post by ~Aurn0b~ » Sat Feb 27, 2021 2:51 pm

Asif Hossain wrote:
Sat Feb 27, 2021 12:35 pm
~Aurn0b~ wrote:
Sun Feb 14, 2021 11:36 am
AourkoPChakraborty wrote:
Fri Feb 12, 2021 4:59 pm
Prove that if $p$ is a prime, then $p^p-1$ has a prime factor, greater than $p.$ :D
$p^p-1=(p-1)(p^{p-1}+p^{p-2}+\cdots+1)$
Now let $q$ be a prime factor of $p^p-1$ such that $q\nmid p-1$. This prime divisor obviously exists because if a prime factor of $p^p-1$, let it be $r$,divides $p-1$, then we have $p^{p-1}+p^{p-2}+\cdots+1\equiv1^{p-1}+1^{p-2}+\cdots+1\equiv p\equiv 1\pmod{r}$, and so $q$ is a prime divisor of $p^{p-1}+p^{p-2}+\cdots+1$
Let, $x=\text{ord}_q(p)$, and we know that $p^p\equiv 1\pmod{q}\Rightarrow x\mid p\Rightarrow x=1,p$
As $q\nmid p-1,\Rightarrow x\neq 1\Rightarrow x=p$
From fermats little theorem, $p^{q-1}\equiv 1\pmod{q}$
So, $p\mid q-1\Rightarrow q>p.\blacksquare$
What does this mean $x=\text{ord}_q(p)$
It means $x$ is the smallest integer for which $p^x\equiv 1\pmod{q}$
or, there are no smaller power of p for which it gives remainder 1 dividing by $q$. Its called by "order of p mod q"
https://web.evanchen.cc/handouts/ORPR/ORPR.pdf

Post Reply