Thread: 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!

Originally Posted by mpryal

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: .