1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

GCD proof in Number Theory

  1. May 31, 2006 #1
    Here is my problem:

    Prove or disprove: If gcd(m, n) = d, then the gcd(a, mn) = gcd(a,m) * gcd(a.n)/d.

    I can seem to get it started, sort of, but it just does not seem to get anywhere. I know by definition d | m and d | n. Then arbitrary integers x and y can be used such that m = xd and n = yd. I can then have gcd(a, mn) = E. Then E | a and E | mn. I can do the same as I did for the other. But the last part of gcd(a,m) * gcd(a.n)/d is giving me a really rough time getting it to know how tie it all in. I have a lot of integers and letters and I think I am very lost at this point. Please help!

    melmath
     
    Last edited: May 31, 2006
  2. jcsd
  3. May 31, 2006 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Do you know the fundamental theorem of arithmetic which says that every number can be written uniquely as a product of primes? So we can write:

    [tex]m = \prod _{i=1}^{\infty}p_i^{\mu _i},\ n = \prod _{i=1}^{\infty}p_i^{\nu _i}[/tex]

    where pi is the ith prime, and the [itex]\mu _i,\, \nu _i[/itex] are eventually zero since m and n are finite numbers. Using the notation above, how would you express gcd(m,n)?
     
    Last edited: May 31, 2006
  4. Jun 1, 2006 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    x and y are not aribtrary integers. x is m/d and y is n/d.

    AKG's way is very useful, but it is also good to do it from the defining characteristics: the gcd of A and B is a the largest divisor of A and B. There is also another way of thinking about it: gcd(m,n) is the integer d such that m=dx, n=dy for some x,y and gcd(x,y)=1
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: GCD proof in Number Theory
Loading...