Results 1 to 2 of 2

Math Help - gcd(m,n) with powers

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    36

    gcd(m,n) with powers

    If m= p1^a1...pk^ak and n=p1^b1...pk^bk where p1,...,pk are distinct primes and a1,...,ak are nonnegative and b1,...,bk are nonnegative, express gcd(m,n) as p1^c1...pk^ck by describing the c's in terms of the a's and b's.

    I can see that m and n would have the p1^c1...pk^ck as the gcd but I am having trouble coming up with steps to show how the a1,...,ak and b1,...,bk become the c1,...,ck. I'm not sure of how to write this proof. Help? Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by mpryal View Post
    If m= p1^a1...pk^ak and n=p1^b1...pk^bk where p1,...,pk are distinct primes and a1,...,ak are nonnegative and b1,...,bk are nonnegative, express gcd(m,n) as p1^c1...pk^ck by describing the c's in terms of the a's and b's.

    I can see that m and n would have the p1^c1...pk^ck as the gcd but I am having trouble coming up with steps to show how the a1,...,ak and b1,...,bk become the c1,...,ck. I'm not sure of how to write this proof. Help? Thanks!
    It is just: c_j = \min(a_j,b_j).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Powers of Two
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: January 4th 2011, 03:29 AM
  2. Powers
    Posted in the Algebra Forum
    Replies: 4
    Last Post: June 6th 2010, 06:55 AM
  3. Sum of nth powers
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 8th 2010, 11:05 PM
  4. powers of 2
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 3rd 2008, 10:53 PM
  5. powers
    Posted in the Algebra Forum
    Replies: 6
    Last Post: February 14th 2008, 06:20 AM

Search Tags


/mathhelpforum @mathhelpforum