2
$\begingroup$

If $r$ is a primitive root of $p$ and $p^2$, then show that it is also a primitive root of $p^3$

This is part of a bigger proof and I'm stuck at understanding this part.

Here some lines of proof from my textbook:

$r^{p-1}\equiv 1 \pmod{p}$
$r^{p-1}\not\equiv 1 \pmod{p^2}$

By Euler,
$r^{\phi(p^2)} = r^{p(p-1)}\equiv 1\pmod{p^2}$
$\Rightarrow r^{p(p-1)} = 1 + ap^2$ for some integer $a$.

Then my textbook simply claims $p\nmid a$ by hypothesis.
I don't get this. Why can't $p$ divide $a$ ? How does it follow from hypothesis?

$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

$r^{p-1} = 1 + kp$. So $$r^{p(p-1)} = \sum_{j=0}^p \binom{p}{j}k^j p^j = 1 + kp^2 + lp^3$$ because of the fact that $p|\binom{p}{j}$ for $2\le j\le p$. So $k + lp= a$. If $p|a$ then $p|k$ and so $r^{p-1} \equiv 1 \left[p^2\right]$.

$\endgroup$
5
  • $\begingroup$ Neat! Thank you so much for the quick response:) If I may ask is it obvious that $p\mid a \Rightarrow p\mid k$ without spending lots of time. Because I spent more than an hour on this and couldn't figure out on my own... :( $\endgroup$
    – across
    Sep 12, 2021 at 4:11
  • $\begingroup$ Yes because $a = k + lp$ which means that $p | k - a$. If also $p | a$ then $p | k$ because $k = k-a + a$. $\endgroup$
    – Kroki
    Sep 12, 2021 at 4:14
  • $\begingroup$ Yes I totally understand that. It is trivial to see after employing binomial theorem. I was wondering how one comes up with such working ideas... $\endgroup$
    – across
    Sep 12, 2021 at 4:18
  • $\begingroup$ That is a good question that I do not have an answer to. $\endgroup$
    – Kroki
    Sep 12, 2021 at 4:19
  • 2
    $\begingroup$ +1. BTW: If $p$ is an odd prime and if $s$ is a primitive root mod $p$ but s is not a primitive root mod $p^2$ then $s+p$ is a primitive root mod $p^n$ for all $n\in\Bbb N.$ $\endgroup$
    – DanielWainfleet
    Sep 12, 2021 at 9:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .