euclidean algorithm - a question on gcd of 2 rational integers being 1 and euclid's lemma

I had a problem with a proof on group and a poster aided me with the proof.
But I had problems understanding the final implication relates to GCD and Euclid's lemma:

$$(a^k)^r=e \Rightarrow a^{kr} = e \Rightarrow n | kr \Rightarrow \frac n d | r \cdot \frac k d \Rightarrow \frac n d | r .$$

The last implication is due to the fact that $\gcd \Big( \frac n d, \frac k d \Big) = 1$ and Euclid's lemma.

Thanks in advance.

Answer

$\frac{n}{d}\mid r\cdot\frac{k}{d}$ means exactly that any prime that divides $n/d$ also divides $r\cdot k/d$.

Here is where we use Euclid's lemma: if a prime divides the product $r\cdot\frac{k}{d}$, then it must divide one of the factors. But $\gcd(n/d,k/d)=1$, so they don't share any prime factors. Therefore, the prime must divide $r$. This gives $\frac{n}{d}\mid r$.