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$.
-
$\begingroup$ Did you mean to restrict $p$ to prime solutions? $\endgroup$ – hardmath Jun 28 '17 at 1:42
-
$\begingroup$ $p$ an odd prime is of particular interest, but $p$ in general might be of interest too. I did forget to require $a>1$, sorry. $\endgroup$ – Justin Jun 29 '17 at 12:55
-
$\begingroup$ The topic of such positive $a$ and prime $p$ is that of Wieferich primes base $a$, where a variety of related OEIS sequences are linked. $\endgroup$ – hardmath Jun 30 '17 at 17:16
-
$\begingroup$ For composite $n$ such that there exists $1\lt a \lt n$ satisfying $a^{n-1}\equiv 1 \bmod{n^2}$, see OEIS sequence A267288. $\endgroup$ – hardmath Jun 30 '17 at 17:49
-
$\begingroup$ The smallest composite example is then $a=68$ and $n=133$, since $68^{132}\equiv 1 \bmod{133^2}$. $\endgroup$ – hardmath Jun 30 '17 at 18:13
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.
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$.