1. Limited time only! Sign up for a free 30min personal 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!

Number Theory gcd problems

  1. Mar 26, 2009 #1
    1. The problem statement, all variables and given/known data
    Let a,b,c be integers. If (b,c)=1, then (a,bc)=(a,b)(a,c)

    2. Relevant equations
    This is difficult to answer because some theorems that we haven't proven yet, we can't use.

    3. The attempt at a solution
    Let g=(a,b) and h=(a,c), g and h are integers.
    That means g|a and g|b, h|a and h|c.
    That means:
    a=gk, for some integer k
    b=gq, for some integer q
    a=hp for some integer p
    c=ht for some integer t.

    Multiply b and c together to get bc=(a,b)(a,c)qt. Then (a,bc)= (gk, (a,b)(a,c)qt), but that's as far as I got.
     
  2. jcsd
  3. Mar 26, 2009 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Sometimes it is just easier to think what things mean. Suppose that d divides a and bc. Think about the prime factors of d. Can you split them into two types? (Or is uniqueness of prime factorisation something you can't use?)
     
  4. Mar 26, 2009 #3
    Yeah, we can use uniqueness of prime factorization. We proved it last month, so that's why we can use it. I don't know how to do correct mathematical notation on the computer here, so hopefully you'll understand what I'm typing.

    So d=(a,bc). d=(p1^r1)(p2^r2)(p3^r3)... or we can say d=(2^r2)(3^r3)(5^r5)... But I don't see how that's going to help me.
     
  5. Mar 27, 2009 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    So you know that gcd(a,b) is the product of the primes that divide a and b (with the right powers), similarly for gcd(a,c). And b and c are coprime so no primes divide both of them. Do you see where this is going?
     
  6. Apr 22, 2011 #5
    Theorem: If (b,c)=1, then (a,bc)=(a,b)(a,c).

    Let g=(a,b) and h=(a,c), g and h are integers.
    That means g|a and g|b, h|a and h|c.
    Therefore:
    b=qg, for some integer q.
    c=th for some integer t.
    g|b and h|c, and (b,c)=1, so (g,h)=1.
    Therefore a=pgh, for some integer p.
    (a,b)=g => (a,b)/g=1 => (pgh,qg)/g=1 => g(ph,q)/g=1 => (ph,q)=1 => (p,q)=1
    (a,c)=h => (a,c)/h=1 => (pgh,th)/h=1 => h(pg,t)/h=1 => (pg,t)=1 => (p,t)=1
    Therefore (p,qt)=1
    (a,bc)=(pgh,qgth)=gh(p,qt)=gh*1=gh=(a,b)(a,c)
    Therefore (a,bc)=(a,b)(a,c)
    Q.E.D.

    I've never done work like this before, so I'm sure I have several form issues, but I went ahead and showed as much of my thought process as I could in hopes that you understand. To the best of my knowledge, this proves the theorem, but if I took any liberties, please, feel free to correct me.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number Theory gcd problems
Loading...