0
$\begingroup$

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

  • 0
    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$.2011-04-02
  • 1
    that may be, but why would that imply the OP's theorem isn't true?2011-04-02
  • 0
    @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$.2011-04-02
  • 0
    :confused: b is any given odd positive integer, that's a condition on b... I'm just not following why the contrapositive is false.2011-04-02
  • 0
    @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.2011-04-02
  • 0
    @Arturo: OK, I follow. (though your restatement is slightly off: the claim is that for fixed *m* and *n*, for any odd *b*, there are infinitely many primes p such that (if p^n congruent to 1 (mod b^m), then b^(m-1) | n). (my parentheses as per the original problem statement))2011-04-02
  • 0
    @Jason: I don't see the original problem as making that claim. The plain reading seems to me to be the one I give: "There are infinitely many primes $p$ such that $p^n\equiv 1\pmod{b^m}$" $\Rightarrow$ "$b^{m-1}|n$." You are reading it as claiming that there are infinitely many primes such that "$p^n\equiv 1\pmod{b^m}\rightarrow b^{m-1}|n$" but that statement does not make much logical sense, since there is no connection between the premise of the implication and the consequent... If that was the intended meaning, then the OP did not make himself clear (IMO).2011-04-02
  • 0
    @Amir Hossein: There is obviously some confusion about what you meant. Did you mean:$$\Bigl(\text{there exist infinitely many primes }p\text{ such that }p^n\equiv 1\pmod{b^m}\Bigr)\Rightarrow(b^{m-1}|n)$$or did you mean$$\text{there exist infinitely many primes }p\text{ such that }\Bigl( p^n\equiv 1 \pmod{b^m}\Rightarrow b^{m-1}|n\Bigr)$$? They are not quite equivalent statements...2011-04-02

1 Answers 1

1

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

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

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