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!

Prime Divisor Problem

  1. Feb 4, 2010 #1
    1. The problem statement, all variables and given/known data
    I have to prove the following:
    Let a1,a2, ...,an be integers and set b=a1*a2*...*an. If c is a nonzero integer and c is relatively prime to each ak, then c and b are relatively prime.


    2. Relevant equations

    Definition of relatively prime: Let a and b be integers, not both zero. if gcd(a,b)=1 then a and b are relatively prime.

    3. The attempt at a solution

    1. Let a1,a2, ...,an be integers and let b=a1*a2*...*an. Suppose there exists a nonzero integer c where c is relatively prime to each ak.

    2. By defn, gcd(c,ak)=1

    I need help showing that the gcd(c,a1*a2)=1

    Thanks
     
    Last edited: Feb 4, 2010
  2. jcsd
  3. Feb 4, 2010 #2
    You don't need to suppose the existence of c; it is given by hyphotesis.

    The best way to do this is to use induction on n and the following result (sometimes called Euclides' lemma): if c|ab and gcd(c,a)=1, then c|b.

    If you haven't covered this lemma, argue like this: if gcd(c,a1*a2)>1, then there must be a common prime divisor p > 1 of c and a1*a2; p cannot divide a1 (because then gcd(a1,c)>1), so it must divide a2 and gcd(c,a2) > 1, and this is also impossible.
     
  4. Feb 4, 2010 #3
    I was just looking at Euclids Lemma actually and wondering how I would prove that c|ab? Is it because c is relatively prime with each a therefore it must divide ab?

    Thank you for your help once again
     
    Last edited: Feb 4, 2010
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook