# There are infinitely many primes such that $p^n \equiv 1 \pmod{b^m}$ implies $b^{m-1} \mid n$

I think I found this problem in papers of Titu Andeerscu, but I do not remember the solution. I have just added this one to my LTE article since the solution I saw used this method to solve it. Here it is:

Let $m$ and $n$ be positive integers. Prove that for each odd positive integer $b$ there are infinitely many primes $p$ such that $p^n \equiv 1 \pmod{b^m}$ implies $b^{m-1} \mid n$.

-
This is not true. By Dirichlet's theorem, there exist infinitely many primes congruent to 1 modulo $b^m$. The same will then be true of their $n$th powers, without any conditions on $n$ or $b$ or $m$. –  Alex B. Apr 2 '11 at 12:52
that may be, but why would that imply the OP's theorem isn't true? –  Jason S Apr 2 '11 at 13:36
@Jason S: Consider the contrapositive. Then $b^{m-1} \not | n \implies p^{n} \not \equiv 1 \pmod {b^m}$ which is false since there are no conditions on $b$ or $m$. –  PEV Apr 2 '11 at 16:59
:confused: b is any given odd positive integer, that's a condition on b... I'm just not following why the contrapositive is false. –  Jason S Apr 2 '11 at 19:09
@Jason: The claim is that for fixed $m$ and $n$, for any odd $b$, if there are infinitely many primes $p$ such that $p^n\equiv 1\pmod{b^m}$, then $b^{m-1}$ divides $n$. But pick $b$, $m$, and $n$ that do not satisfy the condition; e.g., $b=3$, $m=2$, $n=5$. Then $b^{m-1}=3$ does not divide $5$. By Dirichlet's Theorem, there are infinitely many primes $p$ such that $p\equiv 1\pmod{9}$, ($9=b^m$) and all such primes also satisfy $p^{5}\equiv 1\pmod{9}$. So the premise (infinitely many primes that satisfy the condition exist) holds, but the conclusion ($b^{m-1}|n$) does not. –  Arturo Magidin Apr 2 '11 at 19:16

There seems to be some question as to exactly how to read the proposition, but I will address it interpreted this way:

Given $b$ and $m$, call a prime $p$ acceptable if every $n$ for which $p^n \equiv 1\pmod {b^m}$ also satisfies $b^{m-1}|n$. Show that for any choice of positive integers $b,m$ with $b$ odd there are infinitely many acceptable primes.

Proof: Write $b=\prod q_i^{a_i}$ for distinct odd primes $q_i$ with $a_i>0$. Then for each $i$ there exists a generator for the multiplicative group mod $q_i^{m a_i}$, call it $g_i$ satisfying $$g_i^{\phi(q_i^{m a_i})} \equiv 1 \pmod{q_i^{m a_i}}$$ where $\phi$ is the totient function and $$g_i^l \not\equiv 1 \pmod{q_i^{m a_i}} \text{ for } 0<l<\phi(q_i^{m a_i})=q_i^{m a_i-1}(q_i-1)$$ So for each i, if $p\equiv g_i \pmod{q_i^{m a_i}}$, then $$p^n \equiv 1\pmod{b^m} \implies p^n \equiv 1\pmod{q_i^{m a_i}} \implies q_i^{m a_i-1}(q_i-1) | n \implies q_i^{(m-1)a_i} | n$$

And if $p\equiv g_i \pmod{q_i^{m a_i}}$ for all $i$, then $$p^n \equiv 1\pmod{b^m} \implies \prod{q_i^{(m-1)a_i}} | n \implies b^{m-1} | n$$ and $p$ is acceptable.

But by the Chinese remainder theorem there is some $0<r<b^m$ satisfying $r\equiv g_i \pmod{q_i^{m a_i}}$ for all $i$ simultaneously, $\gcd(r,b^m)=1$, and by Dirichlet's theorem there are infinitely many primes of the form $kb^m+r$, all of which are acceptable, QED.

Note 1: My statement is equivalent to @Arturo Magidin's second formulation $$\text{there exist infinitely many primes }p\text{ such that }\Bigl( p^n\equiv 1 \pmod{b^m}\Rightarrow b^{m-1}|n\Bigr)$$ but it's perhaps a bit less confusing because it might seem like there is a problem when $b=3,m=2,n=5$ since $3 \nmid 5$. But this is not actually a problem, because any prime $p\not\equiv 1 \pmod{9}$ does not satisfy $p^5 \equiv 1\pmod{9}$, and since logically $False \implies False$, the implication is true for $p$.

Note 2:@Arturo Magidin's first formulation $$\Bigl(\text{there exist infinitely many primes }p\text{ such that }p^n\equiv 1\pmod{b^m}\Bigr)\Rightarrow(b^{m-1}|n)$$ is not true. As @Alex B. commented, for any choice of $b>1$ and $m>1$, there are infinitely many primes $p\equiv 1\pmod{b^m}$ which will satisfy $p^n\equiv 1\pmod{b^m}$ for every $n$, particularly for some $n$ not divisible by $b^{m-1}$.

-