Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Find a and b where a, b \in\mathbb{Z}^+

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Find a and b where a, b \in\mathbb{Z}^+

    gcd(a,b)=20 \ \mbox{and} \ lcm(a,b)=840

    What is an easy, efficient way to do these sort of problems?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    gcd(a,b)=20 \ \mbox{and} \ lcm(a,b)=840

    What is an easy, efficient way to do these sort of problems?
     20=2^2\cdot5 and  840=2^3\cdot3\cdot5\cdot7

    Also  (a,b)=\prod p_i^{\min(a_i,b_i)} and  [a,b]=\prod p_i^{\max(a_i,b_i)}

    So here's the prime factors we're interested in and the appropriate powers:

    <br />
      \begin{tabular}{|c|c|c|}\hline<br />
      p & \text{min} & \text{max}\\\hline\hline<br />
      2 & 2 & 3\\\hline<br />
      3 & 0 & 1\\\hline<br />
      5 & 1 & 1\\\hline<br />
      7 & 0 & 1\\\hline<br />
     \end{tabular}<br />

    So to find an  a and  b , just choose an exponent from each row to assign to  a and choose the other for  b .

    For example we could take  a=2^2\cdot3\cdot5\cdot7 , which forces  b=2^3\cdot5 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    What do you mean by just choose an exponent?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    What do you mean by just choose an exponent?
    Choose an exponent for each row, either from the min column or the max column.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by chiph588@ View Post
    Choose an exponent for each row, either from the min column or the max column.
    \forall p_i\mbox{?} so there are 5 to try?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    \forall p_i\mbox{?} so there are 5 to try?
    Yes, for every prime dividing the gcd or lcm. In this case we have 4 primes: 2,3,5,7.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Then there are 5*4=20 possibilities to try.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    Then there are 5*4=20 possibilities to try.
    No there are  2^4=16 solutions.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chiph588@ View Post
    No there are  2^4=16 solutions.
    Well the exponent of prime factor 5 for both a and b is always 1, so it's actually  2^3=8 distinct pairs (a,b). Note that this number counts (420, 40) and (40, 420) as distinct.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by chiph588@ View Post
    No there are  2^4=16 solutions.

    Are the possible solutions always can to be 2^{number of primes}?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    Are the possible solutions always can to be 2^{number of primes}?
    Let a be the number of primes where  a_i\neq b_i .

    Then the number of solutions is  2^a .
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Is there a way to do permutations of the exponents to solve all the solutions or must I just plug them in?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    Is there a way to do permutations of the exponents to solve all the solutions or must just plug them in?
    All possible permutations form all the solutions.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Here is another solution.
    Since gcd(a,b)=20, you can write a=20A and b=20B, where A and B are relatively prime.

    Beacuse ab=gcd(a,b)lcm(a,b), 20^2AB=20\cdot840 and then AB=42=2\cdot3\cdot7.
    Now choose A,B such that (A,B)=1. There are 8 possible ways.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by melese View Post
    Here is another solution.
    Since gcd(a,b)=20, you can write a=20A and b=20B, where A and B are relatively prime.

    Beacuse ab=gcd(a,b)lcm(a,b), 20^2AB=20\cdot840 and then AB=42=2\cdot3\cdot7.
    Now choose A,B such that (A,B)=1. There are 8 possible ways.
    I see what you are doing but can you expand your example?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. \mathbb{Q}\times\mathbb{Q} is not cyclic
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: October 10th 2011, 02:22 PM
  2. Replies: 3
    Last Post: August 26th 2011, 07:59 PM
  3. [SOLVED] f:\mathbb{N}\to S
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 13th 2011, 06:47 PM
  4. x,y\in\mathbb{R} x<y, there exist an irrational between x and y
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: May 12th 2011, 01:47 PM
  5. Replies: 7
    Last Post: February 19th 2010, 07:21 AM

/mathhelpforum @mathhelpforum