1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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)$). $\endgroup$
    – Cecilia
    Jul 12, 2018 at 11:35

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .