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!

Homework Help: 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

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook