How can I find positive integers $a$ and $p$ satisfying $a^{p-1}=1($mod $p^2)$?

Question

How can I find positive integers $a$ and $p$ satisfying $a^{p-1}=1$ ($\mathrm{mod}\ p^2$)? Let's say $1\lt a \lt 100, p \lt 10^8$.

Answer 1

When $p$ is an odd prime, the multiplicative group $\mathbb{Z}_{p^2}^*$ is cyclic of order $\varphi(p^2) = p(p-1)$ by the Primitive Element Theorem. Thus any $a$ coprime to $p$ will have multiplicative order mod $p^2$ which divides $p(p-1)$, and there are $\varphi(p(p-1))$ elements of $\mathbb{Z}_{p^2}^*$ which attain order $p(p-1)$ exactly (here $\varphi$ is Euler's totient function).

There is a possibility for confusion between the primitive element of the cyclic ring $\mathbb{Z}_{p^2}$ under discussion and one for a finite field of order $p^2$. The latter is a quadratic field extension of $\mathbb{Z}_p$ and has multiplicative order $p^2-1$, while here we intend a residue mod $p^2$ with multiplicative order $p(p-1)$.

Now the proof of the Primitive Element Theorem includes the observation that if $g$ is a primitive root in $\mathbb{Z}_p$, then either $g$ or $g+p$ will be primitive in $\mathbb{Z}_{p^2}$.

Any one of these primitive elements $g$ generates all of $\mathbb{Z}_{p^2}^*$ by taking successive powers, $g,g^2,g^3,\ldots,g^{p(p-1)}$. But since such $g$ has the maximum order $p(p-1)$, it does not satisfy $g^{p-1} \equiv 1 \bmod{p^2}$ (because that happens only if the order divides $p-1$).

The elements $a\in \mathbb{Z}_{p^2}^*$ (residues mod $p^2$ coprime to $p$, and hence to $p^2$) whose order divides $p-1$ form a subgroup, as is easily checked by taking the product of two such elements. We get the number of these whose orders divide $p-1$ by counting the powers of a generator $g$ which are multiples of $p$, i.e. $a=g^p,g^{2p},g^{3p},\ldots,g^{(p-1)p}$.

Omitting the last of these (which is $1\bmod{p^2}$), we have $p-2$ nontrivial solutions. The difficulty (suggested by the Question's requirement that $1\lt a \lt 100$) lies in finding fairly small such solutions (because their density is about $1/p$).

Indeed finding primes where base $a=2$ works turns out to be a particularly difficult case (Wieferich primes, OEIS A001220), for which only two primes $1093$ and $3511$ are known to exist (possible primes have been checked out to $10^{18}$).

Taking into account the rather modest sizes for primes $p$ considered here (so that in particular $p-1$ is easily factored), and the desire for a small $a$, it would be natural to simply test the possible values of $1\lt a \lt 100$ to find any that satisfy $a^{p-1} \equiv 1 \bmod{p^2}$. Possibly it will be useful to work out an addition chain for $p-1$ in connection with a modular exponentiation scheme to check this.

Answer 2

The $p-1$ solutions of $a^{p-1}=1 \pmod{p^2}$ are the numbers of the form $n^p$, with $n=1,2,\dots,p-1$, I think. Compute them by binary powering modulo $p^2$, and see if any of them satisfies your additional requirement $1<a<100$.