Originally Posted by

**Showcase_22** I'm still not that brilliant at proving things and i'm having trouble with this lemma.

I started with $\displaystyle hcf(a,n)=1 \Rightarrow \ \exists u,v \in \mathbb{Z} \ s.t \ au+nv=1.$

Suppose n divides ab $\displaystyle \Rightarrow \ n=kab \Rightarrow \ a=\frac{n}{kb}$

Combining both expressions gives: $\displaystyle \frac{nu}{kb}+nv=1 \Rightarrow n \left( \frac{u}{kb}+v \right)=1 \Rightarrow \ n=\frac{kb}{u+vkb}$.

This is an integer multiple of b so n must divide b.