Proving GCD and LCM for Beginners

[bobber205]

I am *totally* blanking on how to even begin on this one.

I need to prove that the gcd(a,b) | lcm[a,b].


I know that means that a| lcm[a,b] and that b | lcm[a,b]
but I don't really know where to go from there.

I think a small kickstart is all I really need for now. :)

Thanks!

 

[Vid]

prime factorization

 

[bobber205]

I guess I need help that much more basic. As I don't have any real clue, w/o googling that term, what prime factorization is.

 

[HallsofIvy]

Use the definition 0f "lcm" and "gdc".

 

[bobber205]

Here's what I have so far. C = gcd(a,b) and X = lcm[a,b]

the lcm of [a,b] means that x | a and x | b.
The gcd means that C | X.

I have written a in terms of a = some integer times x. same thing with b.

but I don't know where to go from there.

 

[bobber205]

Did I say something dumb and scary everyone away? ;)

 

[CoCoA]

Sorry for barging in the topic, but it seems that you need to recheck your definitions precisely.

 

[bobber205]

To the best of my knowledge they are correct. Would you mind saying that exactly is incorrect? I've been trying to figure out that the whole time. ;)

 

[Dick]

a | lcm(a,b) and b | lcm(a,b). Not necessarily the reverse.

 

[bobber205]

Any hints on how that integrates into the problem? As you can see, I've extremely confused.

 

[Dick]

If i | j and j | k then i | k. Use that.

 

[bobber205]

Let me see where you're going with this.

i is the GCD? k is the LCM?
But what would be J?

I've always extremely disliked proofs because of the "abstract" and non concrete answers they always give. Too much open interpretation for me in my math. ;)

 

[Dick]

Let me see where you're going with this.

i is the GCD? k is the LCM?
But what would be J?

I've always extremely disliked proofs because of the "abstract" and non concrete answers they always give. Too much open interpretation for me in my math. ;)

I think you have two choices for j. You can flip a coin if you want. You'll be right either way. :)

 

[bobber205]

I am never sure what to assume is ok "to assume" and what isn't. Can I just write?

a | lcm(a,b)
gcd(a,b) | a

so gcd(a,b) | lcm(a,b)

That makes sense to me and is what I wanted to write a hour or two ago. But I convinced myself that it was wrong.

 

[Dick]

I'd be interested to know how you convinced yourself it was wrong. You must be very persuasive.

 

[bobber205]

Well I thought there was something I need to write that a | lcm(a,b)
and that gcd(a,b) | a

Thought if you say it outloud it seems d'uh easy huh?

Here's the next one I guess I'll try to tackle now that I'm "on a roll". ;)

gcd(a,a+2) = {2 if a even, 1 if a is odd}

wish me luck!

 

[Dick]

Good thing you look up the definitions. That's all the justification you need. Good luck on the next one.

 

[bobber205]

Here's what I got for the even odd one so far.

Taking the even case:
even means a = 2k where k is some integer.

where x is the GCD:
x | 2k
x | 2k + 2

by a theorem, this means that x | 2k + 2k + 2 or x | 4k + 2

After this I don't where to go.

 

[Dick]

If x | 2k then either x | 2 or x | k. 2k+2=2*(k+1). So if x | 2*(k+1) then either x | 2 or x | (k+1). Can x divide both k AND k+1?

 

[bobber205]

I see what you're saying but how does that prove the answer HAS to be 2?

 

[Dick]

Either x doesn't divide k or it doesn't divide k+1. If it doesn't divide one of those, then it must divide the other factor. The other factor in both cases is 2.

 

[bobber205]

Ok. Thanks for the help. That was a lot more complex than I was expecting! :)