# Let $H$ and $K$ be subgroups of a finite cyclic group $G.$ Prove $|H \cap K| = \gcd(|H|,|K|)$

Let $$H$$ and $$K$$ be subgroups of a finite cyclic group $$G.$$ Prove $$|H \cap K| = \gcd(|H|,|K|)$$

My attempt:

$$H$$ and $$K$$ are subgroups of $$G.$$ Therefore, $$H$$ and $$K$$ are cyclic. Further, $$|H|$$ and $$|K|$$ divide $$|G|$$. Every divisor $$m$$ of $$G$$ has a unique cyclic subgroup of order $$m$$. So

$$H = \langle g^\frac{|G|}{|H|}\rangle, \quad K = \langle g^\frac{|G|}{|K|}\rangle$$

By Lagrange's theorem, $$\frac{|G|}{|H|} = [G : H]$$ and $$\frac{|G|}{|K|} = [G : K]$$

So:
$$|H\cap K| = |\langle g^{[G:H]}\rangle \cap \langle g^{[G:K]}\rangle|$$

I don't know how this implies that this equals $$\gcd(|H|,|K|)$$. Any help would be appreciated.

You have a good start - you need to deal more explicitly with the elements for the critical step, however. In particular, you can write $$H = \{g^{n[G:H]} : n\in\mathbb Z\}$$ and $$K=\{g^{n[G:K]} : n\in\mathbb Z\}$$. A reasonable thing to do is to ask which elements are in common between these sets. Note that if you already have a strong handle on sets of the form $$n\mathbb Z$$, you may be able to very quickly get this result by using that - but if not, you can also do things in a more group-theoretic fashion.
First, observe that $$g^{\operatorname{lcm}([G:H],[G:K])}$$ is in $$H\cap K$$ where $$\operatorname{lcm}$$ is the least common multiple, since the exponent is a multiple of both $$[G:H]$$ and $$[G:K]$$ by definition. Let $$R=\langle g^{\operatorname{lcm}([G:H],[G:K])}\rangle$$ be the subgroup generated by this element. First of all, note that the exponent divides $$|G|$$ since both $$[G:H]$$ and $$[G:K]$$ do, thus the order is just $$\frac{|G|}{\operatorname{lcm}([G:H],[G:K])}$$. Then you can use some number theory to observe that if $$a$$ and $$b$$ divide $$n$$, then $$\operatorname{lcm}\left(\frac{n}a,\frac{n}b\right)=\frac{n}{\gcd(a,b)}$$ which essentially follows by noting that reciprocation reverses divisibility.
Applying this with $$n=|G|$$ and $$a=|H|$$ and $$b=|K|$$ and using the formulas you gave for the indices of the subgroups gives that $$|R| = \gcd(|H|,|K|)$$. Then, we are almost done since we know that $$R \subseteq H\cap K$$. The only remaining step is to note that $$R$$ is actually all of it - but we know that $$|H\cap K|$$ divides both $$|H|$$ and $$|K|$$, so the intersection cannot have more than $$\gcd(|H|,|K|)$$ elements, so must be exactly $$R$$.