GCD in PROOF - Solving the Puzzle

[CalleighMay]

GCD in PROOF??

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]

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

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]

Is there a way to write my original problem in this manner using only variables etc?

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)

 

[blue_raver22]

Hello!

It looks like you are trying to understand how to use GCD (greatest common divisor) in proofs. GCD is a very important concept in number theory and is often used in proofs to show relationships between numbers.

In this particular problem, you are being asked to determine if the statement "If b divides c, then (a,b) <= (a,c)" is true or false. To begin, let's break down the statement. "b divides c" means that c is a multiple of b, or in other words, c = kb for some integer k. This is important to note because it tells us that b is a factor of c. Now, (a,b) <= (a,c) means that the GCD of a and b is less than or equal to the GCD of a and c. So essentially, the statement is saying that if b is a factor of c, then the GCD of a and b is also a factor of the GCD of a and c.

To prove this, we can use the definition of GCD: (a,b) is the largest positive integer that divides both a and b. Similarly, (a,c) is the largest positive integer that divides both a and c. Since b is a factor of c, it must also be a factor of a and c. Therefore, (a,b) is a common factor of a and c, and since it is the largest one, it must also be the GCD of a and c. This proves that (a,b) <= (a,c) when b divides c, making the statement true.

To provide a counterexample for the false statement, we can simply choose a and b to be relatively prime (meaning their GCD is 1) and c to be a multiple of b. In this case, (a,b) = 1 and (a,c) = c, so (a,b) is not less than or equal to (a,c). This counterexample shows that the statement is not always true.

I hope this helps clarify things for you. Remember to always start by breaking down the statement and using definitions and properties to prove or disprove it. Keep practicing and you will get the hang of it! Good luck in your course.