# Homework Help: GCD and LCM Proof Help Needed

1. Oct 13, 2008

### 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!

2. Oct 13, 2008

### Vid

prime factorization

3. Oct 13, 2008

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

4. Oct 13, 2008

### HallsofIvy

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

5. Oct 13, 2008

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

6. Oct 13, 2008

### bobber205

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

7. Oct 13, 2008

### CoCoA

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

8. Oct 13, 2008

### 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. ;)

9. Oct 13, 2008

### Dick

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

10. Oct 13, 2008

### bobber205

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

11. Oct 13, 2008

### Dick

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

12. Oct 13, 2008

### 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. ;)

13. Oct 13, 2008

### Dick

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

14. Oct 13, 2008

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

15. Oct 13, 2008

### Dick

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

16. Oct 13, 2008

### 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!

17. Oct 13, 2008

### Dick

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

18. Oct 13, 2008

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

19. Oct 13, 2008

### 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?

20. Oct 14, 2008

### bobber205

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