So using group theory I reached the conclusion that this equation $n=h*gcd(n,k)$ for any $n$ and $h$ such that $h|n$ has $\phi(h)$ solutions for k. Is this true?
How I reached this conclusion. Say we have a cyclic group of order $n$. Hence, we have a unique subgroup of each divisor order. Let $h$ be that divisor. Now since there is only one subgroup of order $h$, all elements of order $h$ are in it. Since there is $\phi(h)$ generators, there are these many elements of order $h$. Now we also know that $|a^k|=\frac{n}{gcd(n,k)}$ so by what we have gathered $\frac{n}{gcd(n,k)}=h$ has $\phi(h)$ solutions, as it was to be proven.
Is there an error in this proof? Is this somehow obvious?
Your proof seems correct to me, but there is one using only simple number theory:
Let $q = \frac n h$. Then your equation becomes $hq = h * gcd(hq, k)$, so $q = gcd(hq, k)$. Obviously $q|k$. Now set $k=iq$ and divide by $q$, which gives $1=gcd(h, i)$, so there are $\phi(h)$ possibilities for i and as many for k.