## 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

STAY CONNECTED