Bon proviamoci, non sono troppo convinto
Sia $\mu (n)$ una funzione che vale $1$ se $n$ è libero da quadrati e ha un numero pari di fattori primi, $-1$ se è libero da quadrati e ha un numero dispari di fattori primi, $0$ se $n$ non è libero da quadrati. Allora se $f,g$ sono funzioni da Z in Z, vale questa formula (inversione di Mobius):
$$f(n)=\sum_{d\mid n} g(a) \iff g(n)=\sum_{d\mid n}f(\frac{n}{d})\mu (d)$$.
Per prima cosa dimostro che $\sum_{d\mid n} \mu (d)=0$ se $n>1$ mentre ovviamente per $\mu (1)=1$. Sia $n=\prod_{i=1}^k p_i^{\alpha_i}$: considero tutti i termini non nulli (quelli liberi da quadrati), di questi ce n'è 1 con 0 fattori, $k$ ne hanno 1, $k\choose i$ ne hanno i, ma $1-p+{p\choose 2}-\dots \pm {p\choose p}=(1-1)^p=0$ (@dario2994, finalmente questa idea sembra avere un senso
).
Adesso la parte davvero buffa:
$$f(n)=\sum_{d\mid n} g(a) \Rightarrow \sum_{ij=n}f(i)\mu (j)=\sum_{ij=n}\mu (j)\sum_{h\mid i} g(h)=\sum_{ij\mid n}g(i)\mu (j)=\sum_{ij=n} g(i)\sum_{h\mid j}\mu (h)=g(n)$$
Dove l'ultimo passaggio è proprio perchè $\sum_{h\mid j} \mu (h)=0$ tranne che per $j=1$ e quindi $i=n$.
Passiamo al problema: $a_n=\sum_{d\mid n}k^{\frac{n}{d}}\mu (d)$. Non resta che dimostrare $\sum_{d\mid n}k^{\frac{n}{d}}\mu (d) \equiv 0 \pmod n$. Prendo $p$ tale che $p^\alpha \mid\mid n$ e dimostro che $p^\alpha \mid a_n$. Osservo che per avere $\mu (d)$ non nullo è necessario che $p^2\nmid n$. Allora divido i divisori che soddisfano in due insiemi: multipli di $p$ e non-multipli di $p$. Se $t$ appartiene al primo insieme allora $pt$ appartiene al secondo, viceversa se $s$ appartiene al secondo insieme allora $p\mid\mid s$ e quindi $\frac{s}{p}$ appartiene al primo, quindi ho stabilito una bigezione tra ogni elemento del primo con ogni elemento del secondo. Inoltre ovviamente $\mu (t) =-\mu (pt)$, quindi posso scrivere la somma come $\sum_{t\mid n} (k^{\frac{n}{t}} - k^{\frac{n}{pt}})\mu (t)\equiv 0 \pmod {p^\alpha}$ perchè per Fermat lo è ogni addendo.
