Results 1 to 2 of 2

Math Help - Prime Numbers and common divisors

  1. #1
    Newbie
    Joined
    Oct 2006
    Posts
    5

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1
    Quote Originally Posted by THulchenko View Post
    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
    Last edited by topsquark; October 1st 2006 at 06:56 PM. Reason: Got a) and b) mixed up!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. common divisors of p^3q^2 and p^2qr?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 19th 2011, 10:25 AM
  2. Relitivly prime, unique divisors of divisors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 24th 2010, 08:40 AM
  3. Norms and common divisors
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: May 27th 2010, 07:51 AM
  4. Odd prime divisors
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 1st 2008, 11:39 AM
  5. Please Help with this Grestest Common Divisors Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 2nd 2007, 05:11 PM

Search Tags


/mathhelpforum @mathhelpforum