# Another relatively prime problem

• Sep 18th 2006, 01:58 PM
suedenation
Another relatively prime problem
a) Show that if a, b, and c are integers with (a,b)=(a,c)=1, then (a,bc)=1.
b) Use mathematical induction to show that if a1, a2,.....,an are integers, and b is another integer such that (a1,b)=(a2,b)=...=(an,b)=1, then(a1a2...an, b)=1

• Sep 18th 2006, 04:07 PM
topsquark
Quote:

Originally Posted by suedenation
a) Show that if a, b, and c are integers with (a,b)=(a,c)=1, then (a,bc)=1.
b) Use mathematical induction to show that if a1, a2,.....,an are integers, and b is another integer such that (a1,b)=(a2,b)=...=(an,b)=1, then(a1a2...an, b)=1

a) (a,b) = 1 so the (unique) prime factorization of b contains NO primes in the prime factorization of a. Similarly (a,c) = 1 implies that the prime factorization of c contains no primes in the prime factorization of a. This means that the prime factorization of bc also contains no primes in the prime factorization of a. Thus (a,bc) = 1.

b) You really want to "turn this around" and start with (a_1,b) = 1 and (a_2,b) = 1 implies (a_1*a_2,b) = 1. (After all, the symbol is symmetric.)

(a_1,b) = 1, (a_2,b) = 1, and (a_3,b) = 1.
Let a_1*a_2 = d. Thus we need to prove
(a_1*a_2*a_3,b) = (d*a_3,b) = 1.
We know that (d,b) = (a_1*a_2,b) = 1 from a) and (a_3,b) = 1.
Thus by a) we know that (d*a_3,b) = 1.

Can you generalize this procedure?

-Dan
• Sep 18th 2006, 04:13 PM
ThePerfectHacker
Quote:

Originally Posted by suedenation
a) Show that if a, b, and c are integers with (a,b)=(a,c)=1, then (a,bc)=1.

Watch from die miester and learn.
---
Let d=gcd(a,bc)
thus,
d|a and d|bc since, gcd(a,b)=d then,
d|c (by Euclid's lemma :eek: )
but,
gcd(a,c)=1
thus,
the maximal nature of d is 1.