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