# Thread: Proof of a lemma

1. ## Proof of a lemma

Lemma: Let a and n be integers with hcf(a,n)=1. Then

n divides ab if and only if n divides b.
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.

Is this right?

I'm also having trouble with the converse of the statement as well. I'll post any progress I make.

2. 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.
What? n is an integer multiple of b so n must divide b? 6 is an integer multiple of 3 but 6 does not divide three! You want to show that b is an integer multiple of n. In any case, $\displaystyle n= \frac{kb}{u+ vkb}$ alone does NOT show that "this is an integer multiple of b". Some factors of u+ vkb may cancel factors of b.

Is this right?

I'm also having trouble with the converse of the statement as well. I'll post any progress I make.