Results 1 to 2 of 2

Thread: Prime GCD

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

    Prime GCD

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

    I'm guessing that $\displaystyle p^2$ is the answer to this thing, and surely it divides both $\displaystyle m^2$ and $\displaystyle 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 $\displaystyle q$ is a prime number dividing both $\displaystyle m^2$ and $\displaystyle n^2$, then $\displaystyle q$ divides both $\displaystyle m$ and $\displaystyle n$ (because of primality), hence $\displaystyle q$ divides $\displaystyle p$ and $\displaystyle q=p$ (again because of primality of $\displaystyle p$).

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

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

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Oct 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: Jun 19th 2011, 12:56 PM
  3. Replies: 3
    Last Post: Feb 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: Nov 19th 2010, 07:03 PM
  5. Replies: 6
    Last Post: Aug 27th 2010, 11:44 PM

Search Tags


/mathhelpforum @mathhelpforum