GCD and LCM with a Proof?

C

CalleighMay

Junior Member
Joined
Aug 2, 2008
Messages
66
Hey everyone,

I'm taking this course called "Number Theory" and am having a lot of difficulty with it. We're currently on "proofs" and i am having some issues.

Last week was my first weeks classes. The first day my professor jumped right into the material without giving much background. He's assigning problems left and right without giving any class examples, and the textbook seems like more of a novel than a math book.

I'm stuck on one problem. I "think" it's asking for a proof, but the directions are very unclear.

It asks:

"Tell whether each statement is true and give counterexamples to those that are false. Assume a, b, and c are arbitrary nonzero integers."

And the statement is:

"If b divides c, then (a,b) <= (a,c)."

So in english, if "c divided by b", then the GCD of "a" and "b" is less than or equal to the GCD of "a" and "c".



The back of the book lists the answer as "TRUE" but doesn't give any reasoning or proof to go along with it.

He gave us two proof examples in class using GCD and LCM etc, but i honestly don't understand them. Making up variables here and there, it doesn't look like any math i've seen before.

Here are some random facts i picked up on:

LCM = (a x b)/GCD
LCM x GCD = a x b
(a,b) stands for the GCD (greatest common divisor)
[a,b] stands for the LCM (lowest common multiple)

Yeah, that's all i know...

Can anyone help me out with this problem? I have honestly no idea where to begin. Thanks!
 
CalleighMay said:
Hey everyone,

I'm taking this course called "Number Theory" and am having a lot of difficulty with it. We're currently on "proofs" and i am having some issues.

Last week was my first weeks classes. The first day my professor jumped right into the material without giving much background. He's assigning problems left and right without giving any class examples, and the textbook seems like more of a novel than a math book.

I'm stuck on one problem. I "think" it's asking for a proof, but the directions are very unclear.

It asks:

"Tell whether each statement is true and give counterexamples to those that are false. Assume a, b, and c are arbitrary nonzero integers."

And the statement is:

"If b divides c, then (a,b) <= (a,c)."

So in english, if "c divided by b", then the GCD of "a" and "b" is less than or equal to the GCD of "a" and "c".



The back of the book lists the answer as "TRUE" but doesn't give any reasoning or proof to go along with it.

He gave us two proof examples in class using GCD and LCM etc, but i honestly don't understand them. Making up variables here and there, it doesn't look like any math i've seen before.

Here are some random facts i picked up on:

LCM = (a x b)/GCD
LCM x GCD = a x b
(a,b) stands for the GCD (greatest common divisor)
[a,b] stands for the LCM (lowest common multiple)

Yeah, that's all i know...

Can anyone help me out with this problem? I have honestly no idea where to begin. Thanks!
Click to expand...

Here's a REALLY good beginning: lose that photo. This is a homework help site where we work with kids of all ages. We DO NOT need this kind of thing.

Try posting your question again, WITHOUT the suggestive photo, and I'll give you my thoughts on your problem.
 
Going through my notes, i am getting some other weird equivalences...

[a,b] = (a x b) / (a,b)

(a,b) x [a,b] = a x b

a ( (b / (a,b)) ) = (a x b) / (a,b)

b ( (a / (a,b)) ) = (a x b) / (a,b)

Don't know of these mean anything??
 
If b divides c, then we can write c as b*n where n is a positive integer.

(a, b) is the greatest common divisor of a and b.

(a, c) is the greatest common divisor of a and c.

Consider (a, b) and (a, c)...we know that c = b*n.

How does (a, b) compare to (a, b*n)? If "a" and "n" have no factors other than 1, (a, b) and (a, b*n) must be the same. If "a" and "n" do have a common factor other than 1, then (a, b*n) will be greater than (a, b). So, (a, b) <= (a, b*n) or (a, b) <= (a, c)
 
Mrspi gave a good proof of the problem. Below are a few comments that might help you make sense of the whole topic.

A lot of GCD and LCM proofs will require you to work with the prime factorization of a number. To find the prime factorization, just keep dividing the number until you have only prime number left. Basically, it's the list of prime numbers that you multiply together to get the number.

Example prime factorization: 12 = 2*6 = 2*2*3

You can write a generalized prime factorization like this: A = k1*k2*...*kn (where 1, 2, ... , n are all subscripts)

So, looking at an examples of your problem:

A = 12 = 2*2*3
B = 8 = 2*2*2
C = 24 = 2*2*2*3

8/24=3, so 8|24 (8|24 reads 8 divides 24)

Then, the GCD of any two number is just the product of all their common prime factors. For 12 and 8, both have two 2s in their prime factorization, so GCD(12, 8) = 2*2 = 4. Similarly, 12 and 24 have two 2s each and one 3 each, so GCD(12, 24) = 2*2*3 = 12.

So, in our random example, we can see that GCD(12, 8) < GCD(12, 24), so the original proposition is true in this case.

Keep in mind the identity used at the beginning of Mrspi's proof as you will use it a lot: b|c implies that c = b*n for some number n.

I think this should give you the basic framework you need to understand GCD and LCM problems in general, and to really understand the explanation given by Mrspi.

I really recommend you take the time to prove all of the equivalences in your notes to make sure you really understand them. Most of them are quite trivial if you understand what they say.
 
Is there a way to answer this problem as a "proof" rather than with an example?

We're not supposed to use an example, we're supposed to prove it with all those variables and everything, that shows one thing equals something and what not...




Here's an example of a proof in the fashion he wants us to write them:

"if c divides a and c divides b, then [a,b] <= ab"

Assuming this is true, the proof would look like:

We need to show that ab/c is a multiple of "a" and "b".

a = ck
b = cj ...(for ints k and j)

(ck x b) / c = bk.... so ab/c is a multiple of b

(a x cj) / c = aj..... so ab/c is a multiple of a

Therefore ab/c is a common multiple of "a" and "b". So it's either the lowest multiple, or a larger.
aka.... ab/c = LCM .... or.... ab/c < LCM

This shows that [a,b] <= ab/c




Is there a way to write my original problem in this manner using only variables etc?
 
CalleighMay said:
... we're supposed to prove it with all those variables and everything,
that shows one thing equals something and what not...
Click to expand...
What does that mean?

I'm sure your teacher wants to see how YOU handle the proof, not how one of us does it :idea:
 
It has to be written in proof form. Meaning the proof needs to contain step by step instructions using variables etc.

I can't just submit a set of numbers that prove it to be true. I have to SHOW why it's true by making a proof. And i don't get it...

What should it look like??
 
CalleighMay said:
It has to be written in proof form. Meaning the proof needs to contain step by step instructions using variables etc.

I can't just submit a set of numbers that prove it to be true. I have to SHOW why it's true by making a proof. And i don't get it...

What should it look like??
Click to expand...

Mrspi's answer is a proof. What's wrong with it?
 
Oh i get it now... i just needed to put everything together.

So i have b dividec c, and we want to prove the gdc of a and b is less than or equal to the gcd of a and c. So if i can prove that (a,b) is a common divisor of a and c, we're good.

From the def. of GCD, we have that (a,b) divides a, and also that (a,b) divides b.

And from the given that b divides c, we can say that (a,b) divides c.

Therefore (a,b) is a common divisor of a and c.
So, (a,b) is either the least or equal to (a,c).

Does this sound about right?
 
Yes, that's right.

There is one more subtle issue that your teacher may or may not be interested in. You are asked to prove <=, so you may want to show that in some cases it will be = and in some cases it will be <. To put this in other words, you may need to show that you cannot make the stronger statements (a, b) < (a, c) or (a, b) = (a, c).

For this reason, Mrspi's explanation of the two cases of the common factors of a and n, or more correctly, the common factors of a/(a,b) and n.
 
You must log in or register to reply here.
Top