Thread: Prime Numbers and common divisors

Hello.

Stuck on the following pretty badly. Could someone help?

Let a=(pr1)(pr2)(pr3)....(prn) the r1, etc is a superscript
Let b=(ps1)(ps2)(ps3)...(psn) the s1, etc is a superscript
where p1, p2, pn are distinct positive prime numbers and all r,s are greater than or equal to 0.

Prove these:
a) gcd(a,b)=(pt1)(pt2)(pt3)...(ptn) where for i, ti is the minimum of ri and si.
b) lcm(a,b)=(pw1)(pw2)(pw3)...(pwn) where wi is the maximum of ri and si.

I'm sorry about the confusing notation. But I'm kind of running out of time on a school assignment. Again thanks for any help.

Timothy

Originally Posted by THulchenko

Hello.

Stuck on the following pretty badly. Could someone help?

Let a=(pr1)(pr2)(pr3)....(prn) the r1, etc is a superscript
Let b=(ps1)(ps2)(ps3)...(psn) the s1, etc is a superscript
where p1, p2, pn are distinct positive prime numbers and all r,s are greater than or equal to 0.

Prove these:
a) gcd(a,b)=(pt1)(pt2)(pt3)...(ptn) where for i, ti is the minimum of ri and si.
b) lcm(a,b)=(pw1)(pw2)(pw3)...(pwn) where wi is the maximum of ri and si.

I'm sorry about the confusing notation. But I'm kind of running out of time on a school assignment. Again thanks for any help.

Timothy

Here's a quick sketch for a). b) is tolerably similar.

Don't think so much of proving the result as the fact that you are constructing the gcd. We know that no other prime factors for the gcd of a and b exist other than the list {pi}. We also know that the greatest number of multiples of the factor pi is min{ri, si}. (ie neither a nor b are divisible by any factor pi^n where n>min{ri, si}.) So as we go through each pi, we are step by step constructing the largest possible number that will divide both a and b.

Can you formalize that (construction) into a proof? (And remember that the prime factors of a and b do NOT have to be the same! ie a prime pk can exist in the list of {pi} for the number a that doesn't exist in the list for b. What do you do for the gcd in this case?)

-Dan