MathNet 2012 Question 51

Find all pairs $(a, n)$ of positive integers with $n \gt 1$ such that for every prime $p$ dividing $a^n - 1$, there exists $0 \lt k \lt n$ such that $p$ divides $a^k - 1$.