My assignment is to prove this:
Problem. For an integer $ n \geq 1 $, show that $ \displaystyle n = \sum_{d|n} \phi \! \left( \frac{n}{d} \right) $.
I have a hint: Define an equivalence relation $ \sim $ on $ \mathbb{N} $ by $ a \sim b \iff \gcd(n,a) = \gcd(n,b) $.
Let's start out with the hint. I assume you can verify that $\sim$ is an equivalence relation.
We can define the set $H_d = \{a \in \mathbb N\ |\ a \leq n, \gcd(a,n) = d\}$. Because $\sim$ is an equivalence class, all of the $H_d$ are disjoint for each $d|n$ and the size of their union is $n$: $$n = \sum_{d|n}|H_d|$$
So we want to see how big each $H_d$ is. Suppose that $m \in H_d$ $$\Leftrightarrow \gcd(m,n) = d$$ $$\Leftrightarrow \gcd(m/d, n/d) = 1$$
Why? Because if there was anything left over after dividing by the $\gcd$, it would have been possible to select a larger initial $\gcd$, a contradiction. So now we have a better definition for $H_d$ (rename $a = kd$, since we know $d|a$): $$H_d = \{k \in \mathbb N \ |\ k \leq n, \gcd(k, n/d) = 1\}$$
But we know what this is - $H_d$ is the set of all integers coprime to $n/d$ and smaller than $n/d$, and there are exactly $\phi(n/d)$ of these. Put that in the original sum, and we get $$n = \sum_{d|n}|H_d| = \sum_{d|n}\phi(n/d)$$