1. Not finding help here? Sign up for a free 30min 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!

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Here, you're given

    [tex]lcm(x,y)=2^3*5[/tex]

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    Mark44

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number theory (LCM , GCD)
  1. GCD and LCM (Replies: 2)

Loading...