2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ If $a=7^5+1$ then clearly $a^5 \equiv 1 \pmod{7^5}$. $\endgroup$ – Lucia Aug 13 '14 at 18:06
  • $\begingroup$ Well, yes, of course! Is the real question, then, whether the condition always forces $a \equiv 1\pmod{b^p}$? $\endgroup$ – Kieren MacMillan Aug 13 '14 at 18:11
  • 2
    $\begingroup$ I don't know. I was just pointing out that the question is not fully in focus yet. $\endgroup$ – Lucia Aug 13 '14 at 18:14
  • $\begingroup$ Thanks. I'll try to focus it more and come back with a clearer question (and more data). $\endgroup$ – Kieren MacMillan Aug 13 '14 at 18:20
  • 1
    $\begingroup$ 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 $\endgroup$ – Gottfried Helms Aug 13 '14 at 18:25
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very nice! I believe this completely answers my question, even without me refocusing/clarifying it. $\endgroup$ – Kieren MacMillan Aug 13 '14 at 18:48
  • $\begingroup$ @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. $\endgroup$ – GH from MO Aug 13 '14 at 18:50
  • 2
    $\begingroup$ 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). $\endgroup$ – Vesselin Dimitrov Aug 13 '14 at 18:59
  • 1
    $\begingroup$ @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$. $\endgroup$ – GH from MO Aug 13 '14 at 19:25
  • 2
    $\begingroup$ @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$. $\endgroup$ – Vesselin Dimitrov Aug 13 '14 at 19:33

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.