Results 1 to 2 of 2

Math Help - Prime GCD

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Prime GCD

    Suppose that gcd(m,n)=p, p prime, find gcd(m^2,n^2) .

    I'm guessing that p^2 is the answer to this thing, and surely it divides both m^2 and n^2. But I'm having trouble afterward, thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    You can first look at prime divisors. If q is a prime number dividing both m^2 and n^2, then q divides both m and n (because of primality), hence q divides p and q=p (again because of primality of p).

    So \gcd(m^2,n^2) is a power of p. It is at least p^2, as you said, so it suffices to rule out the case \gcd(m^2,n^2)=p^3. However, in the prime decomposition of m^2, the exponents are even (twice what they are for m), so that p^3|m^2 implies p^2|m (you could also simply say that p|\left({m\over p}\right)^2 and p is prime, so that p|{m\over p}, which means p^2|m). And the same holds with n, whereas p^2 does not divide both m and n (it is greater than their gcd). This concludes that p^3 can't be the gcd, hence it is p^2.

    Laurent.
    Last edited by Laurent; September 17th 2008 at 06:40 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 07:51 AM
  4. why is a prime squared + itself + 1 also a prime
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: November 19th 2010, 07:03 PM
  5. Replies: 6
    Last Post: August 27th 2010, 11:44 PM

Search Tags


/mathhelpforum @mathhelpforum