The smallest power e in Fermat's little theorem

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.

• What can you say about $a^r$? – Jaap Scherphuis Sep 3 '18 at 11:17
• I see that it's also is congruent to 1 modulo p. I mean that $a^r \equiv 1 \pmod{p}$ – E. Shcherbo Sep 3 '18 at 11:18
• Keep going. Use what you assume about $e$. – John Brevik Sep 3 '18 at 11:20
• $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. – E. Shcherbo Sep 3 '18 at 11:27

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

• 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}$. – E. Shcherbo Sep 3 '18 at 11:34
• @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$. – J.G. Sep 3 '18 at 11:35
• 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? – E. Shcherbo Sep 3 '18 at 11:39
• @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. – J.G. Sep 3 '18 at 11:48

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$

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$.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 1, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.971774160861969, "perplexity": 347.8865891866355}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-05/segments/1579250593994.14/warc/CC-MAIN-20200118221909-20200119005909-00143.warc.gz"}