Simple proof for $\sum_{i=1}^n a^{\gcd(i,n)} $ is divisible by $n$
Our sum equals $$S_n(a):=\sum_{d|n} \varphi\left(\frac{n}d\right)a^d.$$ Fix a prime power $p^k$ which divides $n$ (but $p^{k+1}$ does not divide $n$, we write this as $\nu_p(n)=k$), we have to prove that $p^k$ divides $S_n(a)$. If $p$ divides $a$, then $p^k$ divides each summand. Indeed, $\nu_p(\varphi(n/d))\geqslant \nu_p(n/d)-1=\nu_p(n)-\nu_p(d)-1\geqslant \nu_p(n)-d$ since $d<p^d$), thus $\nu_p(\varphi(n/d)a^d)\geqslant \nu_p(n)$ as desired.
Now consider the remaining case: $p$ does not divide $a$. Fix a divisor $s$ of $n$ such that $p$ does not divide $s$ and consider the set of divisors $\{s,ps,p^2s,\dots,p^ks\}$. I claim that $p^k$ divides the sum of $\varphi\left(\frac{n}d\right)a^d$ over $d$ in each such a group. The claim follows. For proving this denote $\varphi(n/p^ks)=A$, then we have $\varphi(n/p^{k-i}s)=p^{i-1}(p-1)A$ for $i=1,\dots,k$. So, it suffices to prove that (if we denote $b=a^s$) $p^k$ divides $$ b^{p^k}+(p-1)(b^{p^{k-1}}+pb^{p^{k-2}}+\dots+p^{k-1}b)=p^kb+\sum_{i=0}^{k-1} p^i\left(b^{p^{k-i}}-b^{p^{k-i-1}}\right), $$ $p^k$ divides each summand by Euler theorem: $b^{p^m}-b^{p^{m-1}}=b^{p^{m-1}}(b^{\varphi(p^m)}-1)$ is divisible by $p^m$
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})$.