# Lcm of k,k+1,k+2 where k≡3(mod 4) ?

1. Feb 12, 2010

### kingwinner

Find the least common multiple of k,k+1, and k+2 where k≡3(mod 4).

Some ideas:
k≡3(mod 4) => k=3+4z for some z E Z
So k is odd, k+1 is even, and k+2 is odd.
Also, this question asks about the lcm of THREE numbers, so I don't think the the Euclidean algorithm (which only gives the gcd or lcm of TWO numbers) will help us in this question.

So how can we solve this?
Thanks for any help!

2. Feb 12, 2010

### JSuarez

What is the gcd of k, k+1 and k+2? If you know it (and you can), the lcm is immediate.

Last edited: Feb 12, 2010
3. Feb 13, 2010

### kingwinner

Right now, I really don't have any way to calculate the gcd of THREE numbers. My textbook talks about the Euclidean algorithm, but all examples and problems are dealing with the gcd of TWO numbers.

Another thing is we don't know what those numbers k, k+1, k+2 actually are...

4. Feb 13, 2010

### Hurkyl

Staff Emeritus
Yes you do -- they are k, k+1, and k+2.

If you only know how to compute pairwise LCM's, then seek to reduce the problem to that.

5. Feb 13, 2010

### JSuarez

What can you say about the common divisors of consecutive integers? Notice that (k+1)-k = 1 and (k+2)-k = 2 and k is odd. By the way, gcd(a,b,c) = gcd(gcd(a,b),c).

Last edited: Feb 13, 2010
6. Feb 13, 2010

### kingwinner

How can we prove that gcd(a,b,c) = gcd(gcd(a,b),c)?

I know that gcd of two consecutive integers = gcd(k,k+1)=1, i.e. two consecutive integers are always relatively prime, but I have no idea about the gcd or lcm of three consecutive integers...

7. Feb 13, 2010

### JSuarez

Well, suppose that d is a common divisor of a,b and c, then it will also be a common divisor of...

How do you prove this?

8. Feb 14, 2010

### ramsey2879

Yep if 3 divides each of a,b,c it will also divide each of a and b!!!! A common divisor of a and b must equal or divide the gcd(a,b).

9. Feb 14, 2010

### ramsey2879

You can find the lcm of a,b,c by multiplying a,b,c together and dividing that result by gcd(a,b,c) twice and by gcd(a,b)/gcd(abc) and gcd(a,c)/gcd(a,b,c) and gcd(b,c)/gcd(a,b,c) each once. You know how to multiply, add and subtract algebraic numbers don't you.

10. Feb 22, 2010

### kingwinner

k is odd, k+1 is even, and k+2 is odd

I know that two consecutive integers are always relatively prime, so gcd(k,k+1)=1 and gcd(k+1,k+2)=1.

With k and k+2 odd, is it always true that gcd(k,k+2)=1? If so, how can we prove it?

If the above are true, then k, k+1, k+2 are pairwise coprime, then it seems intuitively believable to me that lcm(k,k+1,k+2)=k(k+1)(k+2). But I can't figure out a way to prove this rigorously...

Thank you!

11. Feb 22, 2010

### JSuarez

Yes. What does the equality (k+2)-k = 2 tell you about the possible values of gcd(k,k+2)?

Think of the lcm in terms of the prime factorizations of k,k+1,k+2.

12. Feb 22, 2010

### kingwinner

OK, now I have proved that k, k+1, k+2 are pairwise coprime.

But I still can't figure out how to prove that lcm(k,k+1,k+2)=k(k+1)(k+2).

Can somebody provide some help, please?

13. Feb 22, 2010

### tt2348

so you have GCD(K,K+1,K+2)=1, just use the definition of LCM, which is
LCM(a1,a2,a3....)=(a1*a2*a3*a4...)/(GCD(a1,a2,a3...)

14. Feb 23, 2010

### kingwinner

But that formula is not true...
$$\text{lcm}(2,4,8)\cdot\gcd(2,4,8) = 2\cdot 8\neq 2\cdot 4\cdot 8$$

So how can we PROVE that k, k+1, k+2 are pairwise coprime => lcm(k,k+1,k+2)=k(k+1)(k+2)??

Thanks.

15. Feb 24, 2010

### JSuarez

Let $k = p_{1}^{e_1}p_{2}^{e_2}\cdots p_{n}^{e_n}$, $k+1 = q_{1}^{f_1}q_{2}^{f_2}\cdots q_{n}^{f_n}$ and $k + 2 = r_{1}^{g_1}r_{2}^{g_2}\cdots r_{n}^{g_n}$ be the prime factorizations of k, k+1 and k + 2. They don't have any common prime factors; so, what are the factors that must appear on the lcm?

16. Feb 27, 2010

### kingwinner

So I guess we just multiply all of them.

But k=1 and negative k's don't have prime factorizations, how can we prove for these cases?
Also, LCM(a1,...an) itself is defined to be positive, but the a1,...,an can be integers. So will this change our answer? Maybe the lcm should be |k(k+1)(k+2)|?

Thanks!

17. Feb 27, 2010

### JSuarez

Exactly.

Remember that, if k=1, then any positive integer is a multiple of k, so this doesn't affect the result. Second, negative integers have prime factorizations: you just have to put a minus sign in front.

It is: the expression for two numbers is:

$$\rm{lcm}\left(a,b\right)=\frac{\left|ab\right|}{\rm{gcd}\left(a,b\right)}$$