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!

Discrete math (don't know how to start)

  1. May 19, 2009 #1
    1. The problem statement, all variables and given/known data

    Find all pairs of integers a, b such that their GCD and LCM are 14 and 168 respectively.

    2. Relevant equations

    a x b = gcd(a,b) x lcm(a,b) (useful?)

    3. The attempt at a solution

    confused...
     
  2. jcsd
  3. May 19, 2009 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Maybe, maybe not. What does it tell you?
     
  4. May 19, 2009 #3
    that i can use the gcd and lcm to get axb

    so, a x b = 14 x 168

    a x b = 2352...
     
  5. May 19, 2009 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That looks correct. Is it useful?
     
  6. May 19, 2009 #5
    it's somewhat useful, gives me one more piece of information, but i can't see the way to solve it....
     
  7. May 19, 2009 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You don't know how to find all of the solutions to a x b = 2352?
     
  8. May 19, 2009 #7
    i can find pairs, but some of them would be incorrect ex. a = 1 and b = 2352. i was wondering if there would be a better way or shortcut without having to go through all the pairs.
     
  9. May 19, 2009 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ah. So you do know how to solve the problem, you're just fishing for other methods.

    This particular method could be streamlined a bit, because it's easy enough to limit yourself to writing down just those pairs with, for example, a dividing lcm(a,b). There are probably other constraints you could easily impose at the same time.
     
  10. May 19, 2009 #9
    wait a dividing lcm(a, b)?

    can you explain more?
     
  11. May 19, 2009 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    BTW, a different method would be to look at prime factorizations.

    But in the end, I think that after optimization, both methods would lead to the same algorithm.
     
  12. May 19, 2009 #11
    because i have trouble spotting them...

    could you lead me though it?
     
  13. May 19, 2009 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Er, what is there to explain? You know how to find all the solutions to a x b = 2352, so now we're just imposing some of the information from the original problem to streamline our work.

    I thought that's what I was doing....
     
  14. May 19, 2009 #13
    hold on, give me a sec. i'll do trial and error until i find something. if i'm having more trouble, i'll post a reply.

    Thanks. =D
     
  15. May 19, 2009 #14
    so are the answers (14, 168) and (42, 56)?
     
  16. May 19, 2009 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's late for me, so I'll just leave you with two more comments.


    (1) There's no shame in having an inelegant solution!

    If you have a line of thought that looks like it will work, then it's worth pursuing. I'm fairly good at solving hard problems, and one of the reasons is that if I see a path that I can make progress upon, then I go down that path, even if it appears long and tedious. Quite often, I can finish that long and tedious path in much less time than it would take to come up with the clever, "quick" proof.

    And that said, once you take a path and have worked stuff out... you can learn from it and use that experience to continue attacking the problem.


    (2) Divisibility is very, very important in number theory.

    This is something you should take the time to understand thoroughly -- you should be able to answer questions like "find all numbers x such that 12 divides x and x divides 2160" just as easily as you can answer questions like "find all factors of 504".
     
  17. May 19, 2009 #16

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Hrm. I expected three answers. (But I could be wrong)
     
  18. May 19, 2009 #17
    ... can't find the other one.... was looking at it and can't seem to come up with another pair....
     
  19. May 19, 2009 #18
    thanks, i have no trouble with prime factorization, it's just that lcm and gcd are a little iffy with me... i was hoping for a quicker solution since i don't want to take so long on one problem on test not to mention a final
     
  20. May 19, 2009 #19
    wait, if you think there is a third answer can you just tell me? this was actually a test question and i just want to know if there are other answers.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Discrete math (don't know how to start)
  1. Discrete Math (Replies: 0)

  2. Discrete Maths (Replies: 9)

  3. Discrete Math (Replies: 1)

Loading...