0
$\begingroup$

Let $p$ be a prime number. I'd like to prove that there are primitive roots modulo $p^2$. Could someone check this argument?


Note that if $r\in\mathbb Z$ is a primitive root modulo $p^2$, it must be a primitive root modulo $p$ as well, since it must have powers congruent to $1, 2, 3, ... p$ modulo $p^2$ and therefore those powers will also be congruent to $1, 2, 3, ... p$ modulo $p$.

So, we restrict our search to primitive roots modulo $p$. Let $r$ be such a root, and let's look for one of order $\phi(p^2)=p(p-1)$. Let $n$ be the order of $r$ modulo $p^2$. $n$ must divide $\phi(p^2)=p(p-1)$. But it must also be a multiple of $\phi(p)=p-1$, since $r^n\equiv 1$ modulo $p^2$ and therefore also modulo $p$. This implies that $n/(p-1)$ divides $p$ and thus either $n=p(p-1)$ or $n=(p-1)$.

So we just need to find out if all values of $r$ are of order $p-1$. Well, if $n$ is the order of $r$, then $r+p$ is another primitive root modulo $p$ and thus another candidate in our search. But $(r+p)^n\equiv r^n + pr^{n-1}\equiv1 + pr^{n-1}$ modulo $p^2$. But the $pr^{n-1}$ can't be zero because $r^{n-1}$ is a unit modulo $p^2$. So $(r+p)^n\not\equiv 1$, and in particular $r$ and $r+n$ have different orders.

So, if there is even one value of $r$ of order $p-1$, then there is another that isn't (namely $r+p$), and is therefore of order $p(p-1)$, and therefore is a primitive root. Of course, if there aren't any values of $r$ of order $p-1$, then they're all of order $p(p-1)$, so we still reach the desired result.

$\endgroup$
  • $\begingroup$ Looks fine, quite close to the standard proof. In fact, precisly one of the $r+kp$, $k=0$ to $p-1$, will have order $p-1$, but we do not need to prove that to get the result. Some typos, early on you have $1,2,\dots, p$ and you mean $1,2,\dots,p-1$. $\endgroup$ – André Nicolas Jan 26 '15 at 22:01
  • $\begingroup$ The argument can be pushed to higher powers if $p$ is odd: if $r \bmod p^2$ is a primitive root then $r \bmod p^k$ is a primitive root for all $k \geq 2$ provided $p \not= 2$. This is not so when $p = 2$ since there is no primitive root mod $2^k$ when $k \geq 3$. $\endgroup$ – KCd Jan 26 '15 at 22:05
1
$\begingroup$

There is actually a serious flaw in this proof which I didn't spot. In the second paragraph I want to show that $r$ and $r+p$ are always of different orders. I write:

$$(r+p)^n\equiv r^n+pr^{n-1} \text{ modulo $p^2$}$$

I got the binomial formula wrong - it should be

$$(r+p)^n\equiv r^n+npr^{n-1} \text{ modulo $p^2$}$$

Thus we also need $n$ to be coprime with $p$ in order to conclude. In our case we really just want this argument to work when $n=p-1$, so we're fine, although we can't show the more general statement (which might be false) that the orders of $r$ and $r+p$ are always different.

This flaw becomes apparent when we try to generalize this argument to show that if there are primitive roots modulo $p^n$, there are primitive roots modulo $p^{n+1}$, in which case the argument fails if $p=2$, basically because to go from $2^2$ to $2^3$ we need to take $n=\phi(4)$, which is not coprime to $2$ at all.

$\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.