GCD in a 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:

 

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)

 

a divides b: b = a (k) with some int k

b divides c: c = b (L) with some int L

a divides c: c = a (k x L) with ints K and L

 

 

Yeah, that's all i know...

 

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

[triclino]

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)

 

a divides b: b = a (k) with some int k

b divides c: c = b (L) with some int L

a divides c: c = a (k x L) with ints K and L

 

 

Yeah, that's all i know...

 

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

 

Suppose (a,b)=x and (a,c) =y and b/c (=b devides c) .

 

We want to prove : [math]x\leq y[/math]

 

From the definition of the GCD ,if (a,b) =x ,we have that:

 

x>0........................................................................................1

 

x/a and x/b ..............................................................................2

 

And if d is any No such that d/a and d/b ,then d/x................................3

 

Also if (a,c) = y we have that:

 

y>0..............................................................................................4

 

y/a and y/c......................................................................................5

 

And if d is any No such that d/a and d/c ,then d/y..............................................................................................6

 

Put in (6) d = x and we have that:

 

If x/a and x/c ,then x/y.....................................................................................7

 

But from (2) we have that x/a and x/b, and also is given that b/c ,hence x/a and x/c.

 

And using (7) we have : x/y

 

Now from the definition of x/y that implies that:

 

y=kx ...........................................................................................8

 

where

 

[math] k\geq 1[/math].......................................................................9

 

Multiply (9) by x>0 and we have:

 

[math]xk\geq x[/math]..................................................................................10

 

And substituting (8) into (10) we have:

 

[math]y\geq x[/math]

 

You can easily see the above problem by using a numerical example.

 

Let (a,b) = (4,12) and (4,36) where 12/36

 

And GCD(=4) of (4,12)[math]\leq[/math] GCD(=4) of (4,36)

[Mr Skeptic]

First, you know that c is a multiple of b. Therefore it follows that the GCD of a and c is a multiple of the GCD of a and b. The multiple could be 1 of course, making them equal, but otherwise one would be greater.

[CalleighMay]

triclino, is that in correct "proof" format? I can't really follow it...

 

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?

[triclino]

"

 

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

 

 

 

 

 

!

 

..

 

 

 

 

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

 

[/b]

 

What does your professor ???,actually want you to prove ,if he wants you to prove anything at all

 

 

Firstly he asks for a proof by using the concept of the GCD.

 

Then he asks for a proof by using the concept of the LCM.

 

To curry on with my example of the air plane:

 

Not only he wants to fly from L.A to New York thru S.Africa ,but now he wants the pilot to get petrol supply in the air.

 

Next ,i suppose, he will ask the pilot to fly the air plane upside down .

 

Do you think he will ever get into an air plane???

[CalleighMay]

My professor wants me to PROVE the statement:

 

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

 

by completing a proof. I can't just give a set of numbers that show it's true, i actually need to have a "proof" with variables that would make the statement work.

 

Does this make sense?

[triclino]

My professor wants me to PROVE the statement:

 

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

 

by completing a proof. I can't just give a set of numbers that show it's true, i actually need to have a "proof" with variables that would make the statement work.

 

Does this make sense?

 

 

Well, did i not write a proof in my post #2 ,apart from the numerical example???.

 

Unless you cannot even recognise what a proof is.

 

I like the expression "proof with variables"

[mooeypoo]

Watch the attitude, please. A question was asked, quite obviously because the poster does not understand. Instead of attacking them, it would be more helpful to explain.

 

If you have nothing constructive to post, please refrain from posting.