Frog jumping on leaves $N$ leaves are arranged round a circle. A frog is sitting on first leaf and starts jumping every $K$ leaves. How many leaves can be reached by a frog?
 A: A couple of hints to get you started: recall Bezout's identity and think about the greatest common divisor of $N$ and $K$.
Full solution: 
Let $d$ be the greatest common factor of $N$ and $K$.
Label the vertices $0,1,2\dots N-1$. Then the from starts at position $0$ and then jumps $K$ spaces to reach the position congruent to $K\bmod N$ and then it reaches the position congruent to $2K\bmod N$ and so on. So the frog can reach the posistions of the form $sK\bmod N$. So every position it can reach is a multiple of the greatest common factor of $N$ and $K$. because of bezout's identity there exists $s$ and $t$ so that $sK+tN=d$ in other words $sK\equiv d\bmod N$ and so after $s$ steps we reach position $d$, from here it is clear we can reach position $2d$ after $2s$ steps, $3d$ after $3s$ steps and so on up to position $N-d$ and finally position $0$. So we can reach $\frac{N}{d}$ positions.
A: Similar to dREam, consider the ring $\mathbb Z_N$, then let $K \in Z_N$ generates a subring $K(Z_N)$. The answer is |K(Z(N)| , the size of the ring generated by $K$ in $Z_N$.
