# Can we find all primes $p$ that we can find a number $a \neq 1$ that has the same order in $\mathbb{Z}_p^{*}$ and $\mathbb{Z}_{p^2}^{*}$

Supposed that there is a prime $p$, we may define $\mathbb{Z}_p^{*}$ as the multiplication group of integer modulo $p$. Each element in $\mathbb{Z}_p^{*}$, $\{1, 2, \ldots, p-1\}$, has finite order. Meanwhile, if we consider $\mathbb{Z}_{p^2}^{*}$, all $a \in \{1, 2,\ldots, p-1\}$ also have finite order in $\mathbb{Z}_{p^2}^{*}$, but the order of $a$ could be different from the order of respective $a$ in $\mathbb{Z}_p^{*}$.

The problem is that, could we find all prime $p$ that there is a number $a \in \{2, \ldots, p-1\}$ that the order of $a$ in $\mathbb{Z}_p^{*}$ is the same as the order of $a$ in $\mathbb{Z}_{p^2}^{*}$?

Edit: $a = 1$ definitely satisfies the condition for all primes $p$, so we should consider if there is another nontrivial one which satisfies the property.

• You probably want $\{2, 3, \dotsc, p-1\}$. – rogerl Nov 13 '17 at 19:13
• @rogerl Thank you for your comment. That is what I really want to find. I have edited my question. Thanks again. – alphazeta Nov 14 '17 at 0:23
• If $p=3$, the only candidate would be $a=2$ which doesn't work. – Daniel Schepler Nov 14 '17 at 0:25

## 1 Answer

The primes you want are listed at OEIS/A134307. The first 20 ones are $$11, 29, 37, 43, 59, 71, 79, 97, 103, 109, 113, 127, 131, 137, 151, 163, 181, 191, 197, 199$$

Not much is known about them. Heuristically, the density of such primes is $1 - \dfrac1e \approx 0.632$.

• By the way, I am wondering what if the order of $a$, $g$, is less than $p-1$ in $\mathbb{Z}_{p}^*$ when $a^{p-1} \mod p^2 = 1$ . Can we still say that $a^g \mod p^2 =1$? I used Mathematica to verify(e.g. a=3, p=11, g=5), but I failed to find a way to prove it. Thank you in advance! – alphazeta Nov 14 '17 at 2:00
• @aczzdx, perhaps you could ask a separate question – lhf Nov 14 '17 at 9:58
• Is there a reasonably strong mathematical reason for the "heuristically" claim? – user21820 Dec 11 '17 at 14:40