0
$\begingroup$

I have an exercise that is connected to Fermat's little theorem. I should prove that the smallest positive integer $e$ for which $a^e \equiv {1} \pmod{p}$ must be a divisor of $p - 1$. Also, there are some hints: Divide $p - 1$ by $e$, obtaining $p - 1 = ke + r$, where $0 \le r \lt e$, and use the fact that $a^{p-1} \equiv a^e \equiv 1 \pmod{p}$.

I have no ideas except $a^{ke + r} \equiv a^e \equiv 1$.

I will be appreciated for any help and hints.

$\endgroup$
  • 1
    $\begingroup$ What can you say about $a^r$? $\endgroup$ – Jaap Scherphuis Sep 3 '18 at 11:17
  • $\begingroup$ I see that it's also is congruent to 1 modulo p. I mean that $a^r \equiv 1 \pmod{p}$ $\endgroup$ – E. Shcherbo Sep 3 '18 at 11:18
  • 1
    $\begingroup$ Keep going. Use what you assume about $e$. $\endgroup$ – John Brevik Sep 3 '18 at 11:20
  • $\begingroup$ $e$ is the smallest integer for which $a^e \equiv 1 \pmod{p}$ is truth. So, $r$ is either greater than $e$ (that is not impossible) or ... I don't know how to continue. $\endgroup$ – E. Shcherbo Sep 3 '18 at 11:27
1
$\begingroup$

You want to prove $r=0$, so assume otherwise. Then $a^r\equiv a^{ke+r}\equiv 1$, contradicting the definition of $e$.

$\endgroup$
  • $\begingroup$ I'm sorry if it's stupid, but I can't understand why $r = 0$ is an answer. $0$ is also less than $e$ and $a^0$ is also congruent to $1$ modulo $p$: $a^0 = 1 \equiv 1 \pmod{p}$. $\endgroup$ – E. Shcherbo Sep 3 '18 at 11:34
  • $\begingroup$ @E.Shcherbo Since any alternative for $r=0$ would contradict $e$ being the least positive $n$ satisfying $a^n\equiv 1$, we must have $r=0$. $\endgroup$ – J.G. Sep 3 '18 at 11:35
  • $\begingroup$ Ok, I think I got you. The keyword is positive. $0$ is not positive, so, $r$ is either greater than $e$, that is not impossible, or $0$. Are these thoughts correct? $\endgroup$ – E. Shcherbo Sep 3 '18 at 11:39
  • $\begingroup$ @E.Shcherbo Well, $r$ is already $<e$ because it's defined as a remainder, so you its being positive would yield a contradiction automatically. As soon as you've eliminated that option, $r=0$ is all that's left. $\endgroup$ – J.G. Sep 3 '18 at 11:48
1
$\begingroup$

Note that $$r=(p-1)-ke$$

$$a^{p-1} \equiv a^e \equiv 1 \pmod{p}$$

Thus $$a^r= a^{p-1}a^{-ke}\equiv 1 \pmod{p}$$

Since $0\le r<e$ and $e$ is the smallest positive integer satisfying $a^e \equiv 1 \pmod{p}$ we have $r=0$ and $(p-1)=ke$

$\endgroup$
0
$\begingroup$

A variant approach:

We may suppose $a\not\equiv 0\mod p$. Consider the homomorphism \begin{align} f:(\mathbf Z, +)&\longrightarrow (\mathbf Z/p\mathbf Z)^\times, \\ n & \longmapsto f(n)=a^n. \end{align} $e$ is the positive generator of the subgroup $\ker f$.

$\endgroup$

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.