Hi everyone!
You probably know that the primitive root modulo $$$m$$$ exists if and only if one of the following is true:
- $$$m=2$$$ or $$$m=4$$$;
- $$$m = p^k$$$ is a power of an odd prime number $$$p$$$;
- $$$m = 2p^k$$$ is twice a power of an odd prime number $$$p$$$.
Today I'd like to write about an interesting rationale about it through $$$p$$$-adic numbers.
Hopefully, this will allow us to develop a deeper understanding of the multiplicative group modulo $$$p^k$$$.
Tl;dr.
For a prime number $$$p>2$$$ and $$$r \equiv 0 \pmod p$$$ one can uniquely define
In this notion, if $$$g$$$ is a primitive root of remainders modulo $$$p$$$ lifted to have order $$$p-1$$$ modulo $$$p^n$$$ as well, then $$$g \exp p$$$ is a primitive root of remainders modulo $$$p^n$$$.
Finally, for $$$p=2$$$ and $$$n>2$$$ the multiplicative group is generated by two numbers, namely $$$-1$$$ and $$$\exp 4$$$.