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

  • $\begingroup$ 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$. $\endgroup$ – Alex B. Apr 2 '11 at 12:52
  • 1
    $\begingroup$ that may be, but why would that imply the OP's theorem isn't true? $\endgroup$ – Jason S Apr 2 '11 at 13:36
  • $\begingroup$ @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$. $\endgroup$ – PrimeNumber Apr 2 '11 at 16:59
  • $\begingroup$ :confused: b is any given odd positive integer, that's a condition on b... I'm just not following why the contrapositive is false. $\endgroup$ – Jason S Apr 2 '11 at 19:09
  • $\begingroup$ @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. $\endgroup$ – 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}$.


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.