Here is the "general theory" of such congruences.
Consider a sequence $\{a_n \}_{n\ge 1}$ of integers. We'll say it satisfies the necklace congruences if $$\forall n \in \mathbb{N}: \sum_{d \mid n}a_d \mu(\frac{n}{d}) \equiv 0 \bmod n,$$
where $\mu$ is the Mobius function.
Here is an equivalent formulation:
- Formulation 2: $a_{p^{k+1} m} \equiv a_{p^k m} \mod {p^{k+1}}$ for all $p,m,k$ ($p$ prime)
The proof of the equivalence between these two formulation involves a simple coupling argument, see the first two paragraphes of this post for instance.
A less obvious formulation is the following, which I will prove at the end of this answer:
- Formulation 3: $\forall n \in \mathbb{N}: \sum_{d \mid n}a_d f(\frac{n}{d}) \equiv 0 \bmod n$, where $f$ is any function $\in \mathbb{N}^{\mathbb{N}}$ satisfying $\sum_{d \mid n} f(d) \equiv 0 \bmod n$ and $f(1)= 1$. Examples include $\phi(n)$ and $\mu(n)$.
There's also the following formulation, appearing as Exercise 5.2 in "Enumerative Combinatorics, vol. 2":
- Formulation 4: $\exp(\sum_{n\ge 1} \frac{a_n}{n}x^n)$ has integer coefficients.
The congruence you want to prove is the same as saying $$\forall n \in \mathbb{N}: \sum_{d \mid n} a_d \phi(\frac{n}{d}) \equiv 0 \bmod n$$ where
$$a_n := a^n.$$
From Formulation 3 with $f(n) := \phi(n)$, your congruence is equivalent to showing that $a_n := a^n$ is a sequence which satisfies the necklace congruences. The fact that it is indeed such a sequence is immediate from Formulation 2 (for which you need Euler's Theorem) or Formulation 4 (for which you need to know the Taylor series of $-\log(1-x)$).
Proof of Formulation 3:
(I assume familiarity with Dirichlet convolution, denoted "*" below)
Assume that $\{ a_n \}_{n\ge 1}$ satisfies the necklace congruences. Let $f\in \mathbb{N}^{\mathbb{N}}$ be a function satisfying $f(1)=1$ and $\forall n\in \mathbb{N}: \sum_{d \mid n} f(d) \equiv 0 \bmod n$. We know that $n \mid \sum_{d \mid n} \mu(\frac{n}{d})a_d$. Now just write $f ∗ a_n$ as $(\mu∗ a_n) ∗ (1 ∗ f)$ and use the properties of $f$ and $a_n$ to conclude that $n \mid \sum_{d \mid n} a_d f(\frac{n}{d})$.
For the other direction, assume that $\forall n \in \mathbb{N}: n \mid (f * a_n)(n)$. By direct induction, if $n \mid (f ∗ 1)(n)$ then $n \mid (f
^{−1} ∗\mu)(n)$. Now write $\mu ∗ a_n$ as $(f ∗ a_n) ∗ (f
^{−1} ∗ \mu)$ and use the properties of $f$ and $a_n$ to conclude that $n \mid \sum_{d \mid n} a_d \mu(\frac{n}{d})$.