Show that $\sum_{k=1}^{a-1}(k,a)\equiv0\pmod{a-1}\iff a $ is prime

Not an answer, but too long for a comment.

Adding $a$ to both sides means you can define:

$$f(a) =\sum_{k=1}^a (k,a)\tag 1$$

And you want $f(a)\equiv 1\pmod{a-1}\iff a$ is prime.

Then show that:

$$f(a)=\sum_{d\mid a} d\phi(a/d)$$

Thus $f$ is multiplicative.

So then compute $f(p^n)=np^{n-1}(p-1)+p^n$, when $p$ is prime.

So that gives you a general formula for $f(a)$ in terms of the prime factorization of $a.$

But I don’t see where to go from there. I’m not even sure there isn’t a counterexample.

Up to $10^8$, there are $4$ counterexamples: $41124, 230867, 358267, 37539572$.

This was possible thanks to Thomas Andrews, where they write a formula for $f(a)$.

I obtained counterexamples by running the formula in PARI/GP:

forcomposite(a=2,10^8,s=0;fordiv(a,d,s+=d*eulerphi(a/d));if(s%(a-1)==1,print([a])))