Let $n ≥ 1$ and let $a$ be an integer such that $gcd(a, n) = 1$.
Assume $k ≥ 1$ and $a ≥ 2$
$φ$ is Euler's phi function
This is my solution:
I know that $a^k \equiv 1$ (mod $n$)
From this information I can conclude that
$n$ | $a^k - 1$
I can then write
$a^k - 1$ as $nt$ for some integer $t$.
I know that $φ$ is a multiplicative function, so I write
$φ(a^k - 1) = φ(nt) = φ(n)φ(t)$
It is given that $k$ | $φ(n)$ so I know that $k$ | $φ(n)φ(t)$
It then follows that $k$ | $φ(a^k - 1)$
Is this a valid proof?
As Casteels points out in the comments, you can't conclude $\phi(n \cdot t) = \phi(n) \cdot \phi(t)$ because $\phi$ is not completely multiplicative, but you can still prove that $\phi(n) \space\vert\space \phi(n \cdot t)$ using the formula $\phi(\prod p_{i}^{e_i}) = \prod [p_i^{e_i-1} \cdot (p_i-1)]$.