Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Lcm of k,k+1,k+2 where k≡3(mod 4) ?

  1. Feb 12, 2010 #1
    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. jcsd
  3. Feb 12, 2010 #2
    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
  4. Feb 13, 2010 #3
    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...
  5. Feb 13, 2010 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  6. Feb 13, 2010 #5
    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
  7. Feb 13, 2010 #6
    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...
  8. Feb 13, 2010 #7
    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?
  9. Feb 14, 2010 #8
    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).
  10. Feb 14, 2010 #9
    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.
  11. Feb 22, 2010 #10
    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...

    Can someone help me, please?
    Thank you!
  12. Feb 22, 2010 #11
    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.
  13. Feb 22, 2010 #12
    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?
  14. Feb 22, 2010 #13
    so you have GCD(K,K+1,K+2)=1, just use the definition of LCM, which is
  15. Feb 23, 2010 #14
    But that formula is not true...
    [tex] \text{lcm}(2,4,8)\cdot\gcd(2,4,8) = 2\cdot 8\neq 2\cdot 4\cdot 8 [/tex]

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

  16. Feb 24, 2010 #15
    Let [itex]k = p_{1}^{e_1}p_{2}^{e_2}\cdots p_{n}^{e_n}[/itex], [itex]k+1 = q_{1}^{f_1}q_{2}^{f_2}\cdots q_{n}^{f_n}[/itex] and [itex]k + 2 = r_{1}^{g_1}r_{2}^{g_2}\cdots r_{n}^{g_n}[/itex] 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?
  17. Feb 27, 2010 #16
    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)|?

  18. Feb 27, 2010 #17

    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:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook