p-adic exponent or why there is a primitive root modulo powers of prime numbers (except 2)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

$$$ \exp r = \sum\limits_{k=0}^\infty \frac{r^k}{k!} \pmod{p^n}. $$$

In this notion, if $$$g$$$ is a primitive root of remainders modulo $$$p$$$, 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 $$$\log 4$$$.

$$$p$$$-adic numbers

We define a $$$p$$$-adic number $$$r$$$ as a formal power series $$$r = \sum\limits_{i=k}^\infty r_i p^i$$$, where $$$0 \leq r_i < p$$$ are integer coefficients.

Essentially, as formal power series of $$$x$$$ extend polynomials of $$$x$$$, $$$p$$$-adic numbers extend regular numbers base $$$p$$$, using the same rules for the summation and multiplication of the base $$$p$$$ numbers. The number $$$k$$$ in the definition above is called the $$$p$$$-adic valuation of $$$r$$$.

Generally, any rational number can be uniquely represented as $$$p^k \frac{n}{d}$$$, where $$$n$$$ and $$$d$$$ are co-prime integers, also co-prime with $$$p$$$ and $$$d$$$ is positive. In this representation, the possibly negative number $$$k$$$ corresponds to the number $$$k$$$ in the definition above.

This number $$$k$$$ is called the $$$p$$$-adic valuation of $$$r$$$. The numbers with non-negative valuation are called $$$p$$$-adic integers and we will focus on such numbers in this article, because then we can say

$$$ r \equiv \sum\limits_{i=0}^{k-1} r_i p^i \pmod{p^k} $$$

and treat the $$$p$$$-adic number as nested set of remainders modulo $$$p^k$$$ for increasing $$$k$$$, which is essentially the same as with regular polynomials of $$$x$$$ that are much more known in competitive programming.

$$$p$$$-adic logarithms and exponents

One of the things that we regularly do with formal power series is taking logarithms and exponents of it. They have some combinatorics meaning in terms of generating functions, but also e.g. provide an efficient way to compute several first coefficients of $$$P^k(x)$$$ as

$$$ P^k = \exp (k \log P). $$$

Similar thing could be done for $$$p$$$-adic numbers. But in this case it would be done to investigate multiplicative group of remainders modulo $$$p^k$$$ in additive terms. Let's recall the power series definitions of log and exp:

$$$ \begin{matrix} \log (1 - x) = -\sum\limits_{k=1}^\infty \frac{x^k}{k}, \\ \exp x = \sum\limits_{k=0}^\infty \frac{x^k}{k!}. \end{matrix} $$$

The former can be rewritten for $$$\log x$$$ as

$$$ \log x = -\sum\limits_{k=1}^\infty \frac{(1-x)^k}{k}. $$$

For these expressions to be meaningful we would need them to converge. That is, for each coefficient near $$$p^k$$$ we should be able to eventually determine the exact value of such coefficient. Since we have $$$x^k$$$ in the summation, a natural thing to demand here is $$$x \equiv 0 \pmod p$$$ for $$$\exp x$$$ and $$$x \equiv 1 \pmod p$$$ for $$$\log x$$$.

In this case, $$$x^k$$$ for $$$\exp$$$ and $$$(1-x)^k$$$ for $$$\log$$$ would be divisible by $$$p^k$$$, generally leading for increasing valuation of each summand.

Note that dividing by $$$k$$$ for $$$\log$$$ and by $$$k!$$$ would drag the valuation of the $$$k$$$-th summand down.

For $$$\log$$$ it would generally be decreased by at most $$$\log_p k$$$ and for $$$\exp$$$ by at most $$$\frac{k}{p} + \frac{k}{p^2} + \dots \approx \frac{k}{p-1}$$$.

Therefore the valuation of $$$k$$$-th summand for $$$\log$$$ is at least $$$k-\log_p k$$$, which is good, as it limits to infinity. But for $$$\exp$$$ it is nearly $$$\frac{k(p-2)}{p-1}$$$ which is also fine for most $$$p$$$. For most $$$p$$$ except $$$2$$$, for which we will consistently get valuation of exactly $$$1$$$ when $$$k$$$ is a power of $$$2$$$.

So, for odd prime numbers, $$$\exp x$$$ converges for all $$$x$$$ that are divisible by $$$p$$$.

But for $$$p=2$$$, we need $$$x$$$ to be divisible by at least $$$4=p^2$$$ for $$$\exp$$$ to converge.

Why does it matter for primitive roots?

Let's take for granted that primitive root $$$g$$$ does exist for every prime number $$$p > 2$$$.

Any invertible remainder modulo $$$p^k$$$ can be represented as $$$r \equiv g^{l}t \pmod{p^k}$$$, where $$$t \equiv 1 \pmod p$$$.

It is possible to prove that $$$\exp \log x = x$$$ when both $$$\log x$$$ and $$$\exp \log x$$$ converge. That being said, any $$$p$$$-adic number $$$x$$$ such that $$$x \equiv 1 \pmod{p}$$$ can be uniquely represented as $$$x = \exp \alpha = \exp \log x$$$.

Note that there are $$$p^{k-1}$$$ numbers $$$x$$$ (taken modulo $$$p^k$$$) such that $$$x \equiv 1 \pmod p$$$, as well as $$$p^{k-1}$$$ numbers $$$\alpha$$$ (modulo $$$p^k$$$) such that $$$\alpha \equiv 0 \pmod p$$$, making $$$\log$$$-$$$\exp$$$ define a one-to-one correspondence between numbers having remainder $$$0$$$ and $$$1$$$.

Therefore, the remainder $$$r$$$ be represented alternatively as

$$$ r \equiv g^{l(r)} \exp \alpha(r) \pmod{p^k}. $$$

Here $$$l(r)$$$ is a number such that $$$r \equiv g^{l(r)} \pmod p$$$ and $$$\alpha(r)$$$ is a number such that the equation above is true.

There are $$$p-1$$$ different meaningful values of $$$l(r)$$$ and $$$p^{k-1}$$$ different meaningful values of $$$\alpha(r)$$$, making up for $$$(p-1)p^{k-1}$$$ different invertible numbers modulo $$$p^k$$$. If we were to multiply to numbers modulo $$$p^k$$$, the following would stand:

$$$ xy \equiv g^{l(x) + l(y)} \exp(\alpha(x) + \alpha(y)) \pmod{p^k}. $$$

So, any number in the multiplicative group can be uniquely represented by the pair $$$(l,\alpha)$$$, where $$$l$$$ goes from $$$0$$$ to $$$p-1$$$ and $$$\alpha$$$ goes from $$$0$$$ to $$$(p-1)(p+p^2+\dots+p^{k-1})=p^k - p$$$, traversing all remainder modulo $$$p^k$$$ that are divisible by $$$p$$$.

In this notion, all meaningful values of $$$l$$$ are generated by the multiples number $$$1$$$, granted that they're taken modulo $$$p-1$$$ and all meaningful values of $$$\alpha$$$ are generated by the multiples of number $$$p$$$, taken modulo $$$p^k$$$.

First number has a period of $$$p-1$$$, second number has a period of $$$p^{k-1}$$$. These numbers are co-prime, hence the joint period of $$$(1, p)$$$ is $$$(p-1)p^{k-1}$$$, which means that $$$(1, p)$$$ generates all possible pairs of $$$(l, \alpha)$$$.

This, in turn, means that all remainders modulo $$$p^k$$$ are generated by the $$$p$$$-adic number $$$g \exp p$$$.

Ok, and what about $$$p=2$$$?

As we mentioned earlier, $$$\exp r$$$ is still well-defined for $$$r \equiv 0 \pmod 4$$$, so modulo $$$2^k$$$ for $$$k>2$$$, $$$\exp$$$-$$$\log$$$ pair define a bijection between numbers that have remainder $$$1$$$ modulo $$$4$$$ and numbers that have remainder $$$0$$$ modulo $$$4$$$.

As such, it means that powers of $$$\log 4$$$ generate all the numbers that are equal to $$$1$$$ modulo $$$4$$$. This fact highlights that in remainders modulo $$$2^k$$$, there is an element of degree $$$2^{k-2}$$$ that generates a multiplicative subgroup of numbers that are equal to $$$1$$$ modulo $$$4$$$.

Therefore the whole multiplicative group of remainders modulo $$$2^k$$$ is generated by $$$-1$$$ and $$$\exp 4$$$.