GCD in PROOF??

CalleighMay

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:

(a,b) stands for the GCD (greatest common divisor)

[a,b] stands for the LCM (lowest common multiple)

LCM = (a x b)/GCD

LCM x GCD = a x b

[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)

Yeah, that's all i know...

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

tiny-tim

Hey CalleighMay!

(have an leq: ≤ )

Hint: if something divides a and b, and if b divides c, then … ?

CalleighMay

how do i do this by writing it out in "proof" format?

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?

ramsey2879

Yes introduce a variable d = c/b and solve for c now compare (a,b) and (a,c) using your new representation for c. Also write e = gcd(a,b) f = b/e and make the substitutions ef = b
eg = a and h = gcd(g,d)