2
$\begingroup$

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$.

$\endgroup$
5
  • $\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
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.