Proof question?

Question

Prove that if gcd(a_i, m) = 1 for 1 ≤ i ≤ k, then gcd(a_1*a_2*….*a_k, m) = 1.

Answer

Prove that if gcd(a_i, m) = 1 for 1 ≤ i ≤ k, then gcd(a_1*a_2*….*a_k, m) = 1.

We use “proof by contradiction” method. Let
d = gcd (a_1*a_2*….*a_k, m).
Let p be ANY prime factor of d. So,
( p divides m ) AND
( p divides (a_1*a_2*….*a_k, m). ) meaning that p MUST divide at LEAST one of “a_i’s”. Suppose
p divides a_j for some 1 <= j <= k.
and since we showed above ( p divides m ), thus p divides BOTH ‘m’ and ‘a_j’. This means that
gcd ( a_j , m ) >= p …(1)
But we are given by the “condition” in the problem that
gcd ( a_j , m ) = 1. …(2)

(1) & (2) gives us,
1 >= p which is a contradiction since the “smallest prime is 2” and thus p > 2.

Hence our “initial assumption” is wrong. Thus, “d must NOT have any prime factors”. Only the integer ‘1’ is not defined as a prime and does not have any prime factors. Hence d = 1.
QED