For non-zero integers a & b verify the following condition are equivalent.

a) a divides b

b) gcd(a,b)= (Absolute value of a)

c) lcm(a,b)= (Absolute value of b)

Results 1 to 2 of 2

- Sep 19th 2012, 03:43 PM #1

- Joined
- Sep 2012
- From
- New York
- Posts
- 55

- Sep 19th 2012, 04:57 PM #2

- Joined
- Sep 2012
- From
- Washington DC USA
- Posts
- 1,061
- Thanks
- 410

## Re: Gcd/lcm

When you're asked to "show the following are equivalent", the idea is create a "path of implication" so that, thinking of it as a directed graph, once you are at one vertices (meaning one of those conditions is true), the implications take you through all the verticies (meaning all the statements are true). Such a "path" isn't unique.

For instance, you could prove it this way: Prove A if-and-only-if B (A implies B and B implies A) and prove A if-and-only-if C.

But the most efficient way is to prove it as a "ring": Prove A implies B, and prove B implies C, and prove C implies A.

With three statements it's easy, but it can be unclear how to proceed (there are lot's of choices of how to try) when there are many statement.

I'll do one step: B implies C:

Claim: gcd(a,b)= |a| implies lcm(a,b) = |b|.

Proof:

Let gcd(a,b) = |a|. First note that the property of being an integer multiple or divisor of another integer is unchanged by sign.

Since gcd(a,b)= |a|, have that a divides |b|. Also always have that b divides |b|. Since both a and b divide |b|, the lcm(a,b) divides |b|.

But lcm(a,b) is a multiple of |b|, so |b| divides lcm(a,b).

Since have that lcm(a,b) divides |b|, and |b| divides lcm(a,b), by the Lemma below, it follows that lcm(a,b) = |lcm(a,b)| = |b|. QED (B implies C).

Lemma: If u, v nonzero integers such that u divides v and v divides u, then |u| = |v|.

Proof:

The givens say that v = ru, and u = sv for some integers r, s. But then u = sv = s(ru) = (sr)u, so (sr-1)u = 0.

But (rs-1)u = 0 and u not zero, so have that rs-1 = 0. Therefore rs = 1.

But because r and s are integers, rs=1 forces that either r=s=1 or r=s=-1.

Either way |r|=|s|=1.

Thus v = ru implies |v| = |r||u| = |u|, which proves the lemma.

Click on a term to search for related topics.