Let:
- $[]$ denote Iverson brackets, where $[P]=1$ if $P$ is true and $[P]=0$ if $P$ is false
- $(a,b)$ denote the gcd of $a,b$
- $\phi$ denote Euler's totient function
- $\sigma_0(n)=d(n)$ denote the number of divisors of $n$
Then can we show $$\sum_{i=1}^{n}(i-1,n)[(i,n)=1] = \phi(n) \sigma_0(n)?$$
Another way of writing this sum is:
$$\sum_{\substack{1\le i\le n\\ (i,n)=1}} (i-1,n) = \phi(n) \sigma_0(n)$$
This is known as Menon's identity. It has some generalizations, including one by an author who I know well!
It has a fantastic proof by Burnside's lemma. Let $G$ be any group of order $n$ and $U_n$ be the set of units modulo $n$ i.e. $U_n = \{k \in \mathbb N : \gcd(k,n) = 1\}$. This acts on $G$ by the action $(k,g) \to g^k$.
Look at the orbits. Two elements belong in the same orbit if and only if they generate the same cyclic subgroup. Therefore, the number of orbits of this action, equals the number of cyclic subgroups of $G$.
Now, by Burnside's lemma, the number of cyclic subgroups is equal to : $$ \frac 1{\phi(n)}\sum_{\ \ \ \ \ \ \ k=1 \\ \gcd(k,n) = 1}^n \#\{g \in G : g^k = g\} \tag{*} $$
Let $G$ be the cyclic group of order $n$. Then the number of cyclic subgroups of $G$ is equal to $\sigma_0(n)$ (one for each divisor), and if $g^k = g$ then $g^{k-1} = 1$, so we get that $\#\{g \in G : g^k = g\} = \gcd(k-1,n)$. Now the identity follows from $(*)$.