# Number of solutions to the equation $n=h*gcd(n,k)$ for any $n$ and $h$ such that $h|n$

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?

• You have to put the constraint $k \lt n$, otherwise there is an infinite number of solutions (because $gcd(n ,k) = gcd(n, k + n)$). Jul 12, 2018 at 11:35

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.