Thread: 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

Suppose n divides ab

Combining both expressions gives: .

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.

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

Suppose n divides ab

Combining both expressions gives: .

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, 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.