Proving GCD and LCM: A Step-by-Step Guide for Beginners

  • Thread starter bobber205
  • Start date
  • Tags
    Gcd Proof
In summary: Taking the odd case:odd means a = 2k + 1 where k is some integer.where x is the GCD:x | 2k+1x | 2k+1 + 1by a theorem, this means that x | 2k+1 + 1 or x | 3k+1After this I don't where to go.If x | 2k+1 then either x | 2 or x | k. 2k+1=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?again, I
  • #1
bobber205
26
0
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!
 
Physics news on Phys.org
  • #2
prime factorization
 
  • #3
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
Use the definition 0f "lcm" and "gdc".
 
  • #5
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
Did I say something dumb and scary everyone away? ;)
 
  • #7
Sorry for barging in the topic, but it seems that you need to recheck your definitions precisely.
 
  • #8
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
a | lcm(a,b) and b | lcm(a,b). Not necessarily the reverse.
 
  • #10
Any hints on how that integrates into the problem? As you can see, I've extremely confused.
 
  • #11
If i | j and j | k then i | k. Use that.
 
  • #12
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
bobber205 said:
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. :)
 
  • #14
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
I'd be interested to know how you convinced yourself it was wrong. You must be very persuasive.
 
  • #16
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
Good thing you look up the definitions. That's all the justification you need. Good luck on the next one.
 
  • #18
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
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
I see what you're saying but how does that prove the answer HAS to be 2?
 
  • #21
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.
 
  • #22
Ok. Thanks for the help. That was a lot more complex than I was expecting! :)
 

1. What is GCD and LCM?

GCD (Greatest Common Divisor) is the largest number that divides both given numbers with no remainder. LCM (Least Common Multiple) is the smallest number that is a multiple of both given numbers.

2. Why is it important to prove GCD and LCM?

Proving GCD and LCM allows us to have a better understanding of the factors and multiples of given numbers. It also helps in solving various mathematical problems and equations.

3. What is the step-by-step process for proving GCD and LCM?

The step-by-step process for proving GCD and LCM involves finding the prime factors of the given numbers, identifying the common factors and multiples, and then using the prime factors to calculate the GCD and LCM.

4. Can GCD and LCM be proved for more than two numbers?

Yes, GCD and LCM can be proved for any number of numbers. The process remains the same, but the calculations become more complex as the number of numbers increases.

5. What are some real-life applications of GCD and LCM?

GCD and LCM are used in various fields such as computer science, engineering, and economics. They are used to optimize algorithms, design computer networks, and calculate the least common multiple of different currencies, among others.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
922
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
13
Views
682
  • Calculus and Beyond Homework Help
Replies
4
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Back
Top