find all a,n >= 1 so that for all primes $p$ dividing $a^n-1$ there is a positive integer $m
(USA Winter TST 2012) Find all positive integers $a,n\ge 1$ such that for all primes $p$ dividing $a^n-1$ there is a positive integer $m<n$ so that $p | a^m-1$.
Let $v_p(n)$ denote the highest possible exponent of $p$ dividing $n$, where $p$ and $n$ are a prime and a positive integer respectively. Suppose $n$ and $a$ satisfy the constraints. Clearly $a=1$ works for any $n\ge 2$, so assume $a > 1.$ We must have $n\ge 2$. $a^n-1$ can only be prime if $a=2$ as otherwise $a-1$ is a nontrivial factor. Write $n=2^k q$ where $q$ is odd. Then $a^{2^k}-1$ divides $q$. Also, if $p$ is a prime dividing $a^n-1,$ then $p$ divides $a-1$ or $p$ divides $1+a+\cdots + a^{n-1}.$ I'm not sure if the Lifting the Exponent Lemma is useful if $p | (a-1).$ The lemma gives that $v_p(a^n - 1) = v_p(n)+v_p(a-1)$ for an odd prime p. Also, $v_2(a^n-1) = v_2(n) - 1 + v_2(a^2-1)$ provided $2 | a-1.$ I know that $(1+2a+\cdots + (p-1)a^{p-1}) (a-1) = -a - \cdots - a^{p-1} + (p-1)a^{p}.$ It's possible that a factoring trick could be useful. It might also be useful to observe that $p | (a^n-1)$ implies $ord_p(a) | n.$ We also know $ord_p(a) | (p-1)$ by Fermat's little theorem (clearly a is coprime to $p$). So $ord_p(a) | \gcd(n,p-1).$ If $p$ is the smallest prime divisor of $n$, then $\gcd(n,p-1) = 1,$ which implies $ord_p(a) = 1$ or $a\equiv 1\mod p.$ It could help to guess some possible pairs $(a,n)$ and see if there's a general pattern or attempt to prove there are no more solutions when a and n are too "large". As a first guess, we'll try $a=3, n=2$. Then $p=2$ is the only prime dividing $a^n-1$ and $2 | 3^1 - 1$. In general, if $a-1$ is divisible by a prime p, $a^n-1$ is a power of $p$, then the claim clearly holds.
 A: You're correct that with $a = 1$, all $n \ge 2$ works. However, as for always requiring $n \ge 2$, there's one case where $n = 1$ also works. This is with $a = 2$ since $a^n - 1 = 1$, so there are no primes which divide $a^n - 1$ and, thus, the requirement for an $m \lt n$ where $p \mid a^m - 1$ is vacuously true.
For the other cases, I think your approach of trying to use the multiplicative order is a good one. However, the problem requires to determine the values of $n$ and $a$ where all prime factors $p$ of $a^n-1$ have $\operatorname{ord}_p(a) \lt n$. Unfortunately, I can't think of any relatively simple & easy way to show this in general. Instead, as Sil's comment indicates, we can use Zsigmondy's theorem, which states

... if $a>b>0$ are coprime integers, then for any integer $n\geq 1$, there is a prime number $p$ (called a primitive prime divisor) that divides $a^{n}-b^{n}$ and does not divide $a^{k}-b^{k}$ for any positive integer $k<n$, ...

In our case, $b = 1$ so it's always coprime with $a$. The theorem states that, for everything which it applies to, there's always at least one prime number $p$ which divides $a^n - 1$, but which for all positive integers $m \lt n$, we have $p \nmid a^m - 1$.
Thus, the only $n \gt 1$ and $a \gt 1$ which work are those among the $3$ specific exceptions. I've already dealt with the first one earlier, with the second one being

$n=2$, $a+b$ a power of two; then any odd prime factors of $a^{2}-b^{2}=(a+b)(a^{1}-b^{1})$ must be contained in $a^{1}-b^{1}$, which is also even

As such, $a=2^k-1$ for any integer $k \ge 2$, and $n = 2$, work. The third, and final, exception is

$n=6$, $a=2$, $b=1$; then $a^{6}-b^{6}=63=3^{2}\times 7=(a^{2}-b^{2})^{2}(a^{3}-b^{3})$

This gives that the last set of values which work are $a=2$ and $n=6$.
