Prove that if $p$ is a prime, then $p^p-1$ has a prime factor, greater than $p.$
$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$
Prove that if $p$ is a prime, then $p^p-1$ has a prime factor, greater than $p.$
$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$
Prove that if $p$ is a prime, then $p^p-1$ has a prime factor, greater than $p.$
$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
