# There exits d such that $d^{p-1} \equiv 1 \pmod p$ where p is prime?

If p is prime, then there exits $d < p$ such that $d^{p-1} \equiv 1 \pmod p$, or equivalently, $p|d^{p-1}-1$?

Also, if possible, prove that at the same time,$d^{p-1} \not\equiv 1 \pmod p$ must not hold for any $v<p-1$.

I am not sure if it is true. But if the function group $\operatorname{Aut}(\mathbb{Z}_p)$ of the automorphism of $\mathbb{Z}_p$ under function composition is homomorphic to the group $\mathbb{Z}_{p-1}$, where $\mathbb{Z}_p$ is the group of integers modulo $p$ under addition, then my assumptions above should be true.

• Fermat's Little Theorem says that it holds for all such integers less than $p$. – Stefan4024 Sep 11 '18 at 23:11
• Also what is $v$ in the second line? – Stefan4024 Sep 11 '18 at 23:11
• @Stefan4024 Hi, I am sorry about the errors in my writing. Part of my writing in that line does not show up. I wanted to say that for all v < p-1 , the equality must not holds for at least one d. That is if v = p-1, the equality holds,but if not, the equality doesn’t . I want such d that the equality only holds when v = p-1. – Johnny Chen Sep 11 '18 at 23:21

## 1 Answer

Your problem is equivalent to proving that there is a primitive root modulo $p$ for prime integers $p$. This is a well-known fact and a quick search on the site yields this answer as nice proof of it.

In the same time this proves that $U(p) \cong \operatorname{Aut}(\mathbb{Z}_p) \cong \mathbb{Z}_{p-1}$, which is hat you wanted. Taking any generator of $U(p)$, the group of units modulo $p$ will satisfy the condition you want.

• Wow, Thank you for telling me this. I learned a lot of these terminologies. I did not know about primitive root at all. All I need is the existence of primitive root. – Johnny Chen Sep 12 '18 at 0:58
• To the proposer: You do not need the existence of a primitive root to prove this. A theorem of Lagrange is that if $G$ is a finite group with $n$ members then $\forall x\in G\;(x^n=1).$ If $p$ is prime then multiplication modulo $p$ on $\{1,...,p-1\}$ is a group with $p-1$ members. – DanielWainfleet Sep 12 '18 at 2:14
• Recently on this site I saw an induction proof by Gauss that a primitive root exists. It was so short and simple that I can't remember it. – DanielWainfleet Sep 12 '18 at 2:18
• @DanielWainfleet However we need to prove that the group is cyclic for the second part of the question. Your proof isn't enough to conclude that. – Stefan4024 Sep 12 '18 at 10:39