Define a good pair to be a pair $(a, n)$ of positive integers, with $n > 1$, such that any prime dividing $a^n - 1$ also divides $a^k - 1$ for some $0 < k < n$. We claim that the only good pairs are $(2, 6)$, $(1, n)$ for any $n$, and $(2^m - 1, 2)$ for any $m \ge 2$.

It is straightforward to verify that all of these work, so it remains to show that these are the only good pairs. First, note that we have taken care of all cases where $a = 1$, so we may henceforth assume $a \ge 2$. Also, note that if $n = 2$, then $(a, n)$ is a good pair if and only if any prime dividing $a^2 - 1 = (a+1)(a-1)$ also divides $a - 1$. Since the greatest common factor of $a+1$ and $a-1$ is at most $2$, it follows that $a+1$ must be a power of $2$. Thus, we have identified all the good pairs $(a, n)$ with $n = 2$.

It remains to show that the only good pair $(a, n)$ with $a \ge 2$ and $n \ge 3$ is $(2, 6)$. Let $\Phi_n(x)$ be the $n^{\text{th}}$ cyclotomic polynomial, and for a prime $p$, let $v_p(x)$ be the largest $k$ such that $p^k \mid x$. Let $\text{ord}_p(x)$ denote the order of $x$ modulo $p$, meaning the smallest $o$ such that $x^o \equiv 1 \pmod p$. We first prove a sequence of lemmas.

Lemma 4. Let $n, k$, and $d$ be positive integers with $n = kd$. Then if $a$ is a positive integer and $p$ a prime such that either
* $p$ is odd and $p \mid a^k - 1$, or
* $p = 2$ and $4 \mid a^k - 1$,
then we have
$$v_p(a^n - 1) = v_p(a^k - 1) + v_p(d).$$
Proof. Consider the binomial expansion
$$a^n - 1 = ((a^k - 1) + 1)^d - 1 = \sum_{i=1}^{d} \binom{d}{i} (a^k - 1)^i.$$
Under either of the given assumptions, $v_p\left(\binom{d}{i}(a^k - 1)^i\right)$ has a unique minimum at $i = 1$, hence
$$v_p(a^n - 1) = v_p\left(d(a^k - 1)\right) = v_p(a^k - 1) + v_p(d). \quad \square$$

Lemma 5. For any $n \ge 3$ and any prime $p$ such that $\text{ord}_p(a) \ne n$, we have $v_p(\Phi_n(a)) \le v_p(n)$.
Proof. The statement obviously holds if $v_p(\Phi_n(a)) = 0$. Let $k = \text{ord}_p(a)$. Since $\Phi_n(x) \mid x^n - 1$, it follows that $k \mid n$.
Suppose $p$ is odd, and note that $p \mid a^k - 1$. Lemma 4 applies, giving $v_p(a^n - 1) = v_p(a^k - 1) + v_p(n/k)$. Since $\Phi_n(x) \mid \frac{x^n-1}{x^k-1}$, it follows that
$$v_p(\Phi_n(a)) \le v_p\left(\frac{a^n - 1}{a^k - 1}\right) = v_p(n/k) \le v_p(n).$$
Next, we consider the special case when $p = 2$. Since $2 \mid a^k - 1$, $a$ must be odd. Then, since $\Phi_n(x) \mid \frac{x^n-1}{x^k-1}$, we have
$$n \equiv 1 + a + \dots + a^{n-1} \equiv \frac{a^n - 1}{a - 1} \equiv 0 \pmod{2}.$$
Thus, $n$ is even, and we can write $n = 2m$.
Now, note that $4 \mid a^2 - 1$. Also, since $n > 2$, $2$ is a proper divisor of $n$, so $\Phi_n(x) \mid \frac{x^n-1}{x^2-1}$. Thus, by Lemma 4 again, we have the remaining case
$$v_2(\Phi_n(a)) \le v_2\left(\frac{a^{2m} - 1}{a^2 - 1}\right) = v_2(m) \le v_2(n). \quad \square$$

Lemma 6. For any $a \ge 2$ and $n > 1$, we have $\Phi_n(a) \ge \frac{1}{4}a^{\phi(n)}$.
Proof. Let $p_n = \prod_{i=1}^n (1 - 2^{-i})$. We first prove that $p_n \ge \frac{1}{4}$ for all $n \ge 1$. It is clear that $p_n \le \frac{1}{2}$ for all $n \ge 1$. Hence, for each $k$, $p_k - p_{k+1} = 2^{-k-1}p_k \le 2^{-k-2}$. We therefore have
$$p_1 - p_n = \sum_{i=1}^{n-1} (p_i - p_{i+1}) \le \sum_{i=1}^{n-1} 2^{-i-2} \le \frac{1}{4}.$$
Since $p_1 = \frac{1}{2}$, it follows that $p_n \ge \frac{1}{4}$. We can now bound $\Phi_n(a)$. We have
$$\begin{align*} \Phi_n(a) &= \prod_{d|n} (a^{n/d} - 1)^{\mu(d)} = a^{\sum_{d|n} (n/d)\mu(d)} \prod_{d|n} (1 - a^{-n/d})^{\mu(d)} \\ &\geq a^{\phi(n)} \prod_{i=1}^{n} (1 - a^{-i}) \geq a^{\phi(n)} \prod_{i=1}^{n} (1 - 2^{-i}) \geq \frac{1}{4} a^{\phi(n)}. \quad \Box \end{align*}$$

Lemma 7. The only solutions to $a^{\phi(n)} \le 4n$, where $a \ge 2$ and $n \ge 3$ are integers, are $(a, n) = (4, 4), (3, 3), (3, 4)$, and $(2, x)$ where $x \in \{3, 4, 5, 6, 8, 12, 24\}$.
Proof. Let $f(m) = \frac{2^{\phi(m)}}{m}$, and note that $f$ is multiplicative. For any prime $p$ and any $k \ge 2$,
$$f(p^k) = \frac{2^{p^{k-1}(p-1)}}{p^k} = \frac{2^{p^{k-2}(p-1)^2}}{p} f(p^{k-1}) \ge \frac{2^{(p-1)^2}}{p} f(p^{k-1}) \ge f(p^{k-1}),$$
where we have used the fact that $2^{(p-1)^2} \ge p$ when $p \ge 2$. It is easy to check that $f(p) > 4$ for any prime $p \ge 7$. Furthermore, $f(n) > 4$ for $n = 2^4, 3^2, 5^2$. Thus, if $f(n) \le 4$, then $n$ must be a divisor of $2^3 \cdot 3 \cdot 5$. Noting that $f(2) = 1, f(4) = 1, f(8) = 2, f(3) = \frac{4}{3}$, and $f(5) = \frac{16}{5}$. From this and the multiplicativity of $f$, it is easy to see that the only solutions of $f(n) \le 4$ are $n = 2, 3, 4, 5, 6, 8, 12, 24$. This shows that $n \in \{3, 4, 5, 6, 8, 12, 24\}$ are the only solutions for $a = 2$ with $n \ge 3$. If $a \ge 3$ and $\phi(n) \ge 4$, then $\frac{a^{\phi(n)}}{n} = f(n) \cdot (a/2)^{\phi(n)} > 4$. Thus, the only possible solutions for $a \ge 3$ must satisfy $n \in \{3, 4\}$. Checking, we see that the only other solutions are $(a, n) = (4, 4), (3, 3), (3, 4)$. $\square$

We can now find all good pairs $(a, n)$ with $a \ge 2$ and $n \ge 3$. First, note that if $(a, n)$ is a good pair, then for any prime $p \mid a^n - 1$, we must not have $\text{ord}_p(a) = n$. Hence, by Lemma 5, we must have $v_p(\Phi_n(a)) \le v_p(n)$. This applies in particular to all primes dividing $\Phi_n(a)$, so $\Phi_n(a) \le n$.
By Lemma 6, we must then have $n \ge \frac{a^{\phi(n)}}{4}$. Thus, we see that the pairs in Lemma 7 are the only possible good pairs. Checking these finitely many cases, we find that $(2, 6)$ is the only good pair with $a \ge 2$ and $n \ge 3$, as needed.