We show that every prime number $p$, $2 \le p \le n$, divides the product $(a-1)(a^2-1)\cdots(a^{n-1}-1)$ to at least as high a power as it divides $n!$. The exponent of the highest power of $p$ which divides $n!$ is
$$\varepsilon = \sum_{k \ge 1} \lfloor n/p^k \rfloor < \sum_{k \ge 1} n/p^k = n/(p-1).$$
On the other hand, by hypothesis, $p$ does not divide $a$, so at least $\lfloor(n-1)/(p-1)\rfloor$ factors of the product $(a-1)(a^2-1)\cdots(a^{n-1}-1)$ are divisible by $p$, by Fermat's Little Theorem. Finally, notice that $\varepsilon \le \lfloor(n-1)/(p-1)\rfloor$. If $n/(p-1)$ is integral, then $\varepsilon \le n/(p-1)-1 = (n-p)/(p-1) \le \lfloor(n-1)/(p-1)\rfloor$; otherwise, $p \ge 3$ and $n/(p-1)-(n-1)/(p-1) = 1/(p-1) < 1$, so $\varepsilon \le \lfloor n/(p-1)\rfloor = \lfloor(n-1)/(p-1)\rfloor$.