# Does the congruence $a^p \equiv 1 \pmod{b^p}$ with prime $p \ge 5$ force $b \le p$?

I'm considering the congruence in the title, i.e., $$a^p \equiv 1 \pmod{b^p},$$ where $a \ge b \ge 1$ are positive integers and $p$ is an odd prime.

For $p=3$, a brute-force computer search found many solutions with $b > 3$.

For $p=5$, there appear to be only solutions with $1 \le b \le 5$.

For $p=7$, my search hasn't turned up any solutions yet with $b \ge 7$.

Are there any complete or partial results in this direction?

• If $a=7^5+1$ then clearly $a^5 \equiv 1 \pmod{7^5}$. – Lucia Aug 13 '14 at 18:06
• Well, yes, of course! Is the real question, then, whether the condition always forces $a \equiv 1\pmod{b^p}$? – Kieren MacMillan Aug 13 '14 at 18:11
• I don't know. I was just pointing out that the question is not fully in focus yet. – Lucia Aug 13 '14 at 18:14
• Thanks. I'll try to focus it more and come back with a clearer question (and more data). – Kieren MacMillan Aug 13 '14 at 18:20
• While you are preparing a refocused version of the question, perhaps is my older related treatize of interest: go.helms-net.de/math/expdioph/fermatquotients.pdf – Gottfried Helms Aug 13 '14 at 18:25

## 1 Answer

There are counterexamples with $b=kp$ any multiple of $p$. Namely, for $a=1+k^pp^{p-1}$ we have $$a^p=1+\sum_{j=1}^p\binom{p}{j}(k^pp^{p-1})^j\equiv 1\pmod{k^pp^p}.$$ For example, $p=5$ and $k=3$ yields the congruence $151876^5\equiv 1\pmod{15^5}$.

Let us now assume that $b$ is not a multiple of $p$. Then $a^p\equiv 1\pmod{b^p}$ implies that either $a\equiv 1\pmod{b^p}$, or the multiplicative order of $a$ modulo $b^p$ equals $p$. In the latter case, we have $p\mid \varphi(b^p)=\varphi(b)b^{p-1}$, whence $p\mid\varphi(b)$, i.e. $b$ is a multiple of some prime $q\equiv 1\pmod{p}$. So in looking for a counterexample with $p\nmid b$, we may as well assume that $b$ is a prime congruent to $1$ mod $p$.

Here is a quick way to find a counterexample with $p\nmid b$ (for a full characterization see Vesselin Dimitrov's comment). Let $b$ be a prime congruent to $1$ mod $p$. Then $b^p$ is a prime power such that $\varphi(b^p)$ is divisible by $p$. Let $g$ be a primitive root mod $p$, and put $a:=g^{\varphi(b^p)/p}$. Then obviously $a^p\equiv 1\pmod{b^p}$, while $a\not\equiv 1\pmod{b^p}$.

Added. In retrospect the problem simply asks when does the group $(\mathbb{Z}/b^p\mathbb{Z})^\times$ have an element of order $p$. Formulated in this way, clearly a necessary and sufficient condition is $p\mid\varphi(b^p)$, which holds iff $b$ is divisible by $p$ or by a prime congruent to $1$ mod $p$.

• Very nice! I believe this completely answers my question, even without me refocusing/clarifying it. – Kieren MacMillan Aug 13 '14 at 18:48
• @KierenMacMillan: Thanks. I am sure that less obvious counterexamples also exist, in particular with $b$ not divisible by $p$. In this case one has to focus on $p\mid\varphi(b)$ as in the added paragraph. I don't have time to pursue this further, but maybe someone will. – GH from MO Aug 13 '14 at 18:50
• It remains to see that indeed there are examples with $a \mod{b^p} \in (\mathbb{Z}/b^p)^{\times}$ having multiplicative order exactly $p$. This is true if and only if $b$ is composed only of prime factors $q \equiv 1 \mod{p}$. Indeed, for any such prime $q$ you have an $a_0 \in \mathbb{Z}/q$ with $a_0^{p-1}+ \cdots + a_0+1 = 0$ (take $a_0 = g^{(q-1)/p} \mod{q}$ with $g$ a primitive root mod $q$). Since this polynomial has no multiple roots mod $q$, Hensel's lemma will lift $a_0$ to a solution mod arbitrarily high powers of $q$ (a $q$-adic solution). – Vesselin Dimitrov Aug 13 '14 at 18:59
• @VesselinDimitrov: I think your characterization is too restrictive. A group $G$ contains an element of order $p$ iff $|G|$ is divisible by $p$. In our setting, this means that $p\mid\varphi(b^p)$ which holds iff $p\mid b$ or $b$ is divisible by a prime congruent to $1$ mod $p$. We do not need (in the second case) that all the prime divisors are congruent to $1$ mod $p$. – GH from MO Aug 13 '14 at 19:25
• @GHfromMO: You are right. I was assuming implicitly that $b$ is prime to $a-1$, since we wanted to factor out the $a-1$ that produced the trivial examples. All the prime factors of $b$ not congruent to $1 \mod{p}$ will have to divide $a-1$. – Vesselin Dimitrov Aug 13 '14 at 19:33