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.

  • 1
    $\begingroup$ Fermat's Little Theorem says that it holds for all such integers less than $p$. $\endgroup$ – Stefan4024 Sep 11 '18 at 23:11
  • $\begingroup$ Also what is $v$ in the second line? $\endgroup$ – Stefan4024 Sep 11 '18 at 23:11
  • $\begingroup$ @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. $\endgroup$ – Johnny Chen Sep 11 '18 at 23:21

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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Johnny Chen Sep 12 '18 at 0:58
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Sep 12 '18 at 2:14
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Sep 12 '18 at 2:18
  • $\begingroup$ @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. $\endgroup$ – Stefan4024 Sep 12 '18 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.