1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Number theory (LCM , GCD)

  1. May 7, 2012 #1
    1. The problem statement, all variables and given/known data

    Solve in N^2 the following system of equations:

    1- gcd(x,y)=7 and Lcm(x,y)=91

    2- x+y=24 and Lcm =40

    3. The attempt at a solution

    Let d=gcd(x,y)

    I said there exists an α and β so that x=dα and y=dβ and gcd(α,β)=1

    And after doing some work i reached that α divides αβ=13 so that gives only two solutions that satisfy gcd(α,β)=1 and they are α=1 and β=13 and vise versa. So I got S={(7,91);(91,7)}. Can someone help me with the second one. Thank you.
    Last edited: May 7, 2012
  2. jcsd
  3. May 7, 2012 #2
    If you know the prime factorization of x and y, then what can you say about the prime factorization of lcm(x,y)?? Does this have an easy form??
  4. May 7, 2012 #3
    I know that lmc(x,y)=40 ⇔ x divides 40 and y divides 40 , but I don't know what to do from there.
  5. May 7, 2012 #4
    OK, I'll do some examples. See if you can spot the pattern:

    If x=3, y=5, then lcm(x,y)=3*5
    If x=3, y=2*5, then lcm(x,y)=2*3*5
    If x=3², y=5, then lcm(x,y)=3²*5
    If x=3², y=3³*5, then lcm(x,y)=3³*5
    If x=3³*2², y=3²*5, then lcm(x,y)=2²*3³*5

    Can you see an easy way to find the prime factorization of lcm(x,y), given the prime factorization of x and y?
  6. May 7, 2012 #5
    Yes i can but i don't know how to use that with my situation, and I really need to finish this because I still have a lot more stuff to do :(.
  7. May 7, 2012 #6
    Here, you're given


    What are the possibilities for x and y??
  8. May 7, 2012 #7
    Possibilities of x and y could be: (1,40) (5,2^3) and (2^2,10) and the inverse of them too.
  9. May 7, 2012 #8
    The last one is not correct as it would have an lcm of 2^2*5, and you're missing things like (8,10) and (8,40), etc. . But your idea is right: x and y can only be divisible by 2 and 5. Furthermore, at least one of x and y has to be divisible by 8.

    Now, which numbers x and y such that x+y=24 are only divisible by 2 and 5?
  10. May 7, 2012 #9


    Staff: Mentor

    There are quite a few pairs of numbers that you missed.
  11. May 7, 2012 #10
    (14,10) , (4,20) , (8,16) and the inverse of them, but I don't think this system has a solution. Am I correct?
  12. May 7, 2012 #11
    And which ones satisfy lcm(x,y)=40?
  13. May 7, 2012 #12
    Well none of them do. Aren't I correct?

    I had made an edit in the post before.
  14. May 7, 2012 #13
    Yes, there is no solution.
  15. May 7, 2012 #14
    Ok thank you and is there a better way of writing it out. Also I have a different problem that I'm I'm having difficulties with, so i'll post that as well .
  16. May 7, 2012 #15
    I tihnk the simplest way is to focus on the fact that 40 is divisible by the prime number 5, therefore (at least) one of x and y is also divisible by 5. Taking x as divisible by 5, there are only four possible values (in ##\mathbb{N}##) less than 24 for x, and the resulting (x,y) pairs satisfying x+y=24 can be considered in turn and rejected. (Actually there are only three x values consistent with lcm(x,y) = 40, as 15 does not divide 40).
    Last edited: May 7, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook