# Prove Each of the Following:### a. \[(\gcd(a, b) = 1 \land \gcd(a, c) = 1) \Rightarrow \gcd(a, bc) = 1\]**Hint:** From the given \(\exists s, t, u, v \in \mathbb{Z}: sa + tb = 1, \; ua + vc = 1\). Multiply and rearrange terms.### b. \[(a \mid bc \land \gcd(a, b) = 1) \Rightarrow a \mid c\]### c.\[\gcd(a, b) = \gcd(b, \text{rem}(a, b)), \; \text{where } \text{rem}(a, b) \text{ is the remainder of } a \text{ divided by } b.\]

a) To prove : For any three given integers, a, b, c if gcd(a, b) = 1 and gcd(a, c) = 1. then gcd(a, bc) = 1 We know for a fact that, for a, b∈ℤ such that gcd(a, b) = 1, ∃ x, y ∈ℤ such that ax + by = 1. Now, gcd(a, b) = 1, ⇒ ax + by = 1, such that x, y∈ℤ. and gcd(a, c) = 1, ⇒ au + cv = 1, such that u, v∈ℤ. Multiplying both the equations we get, a2xu + bcyv= 1⇒a(axu) + bc (yv) = 1 Since product of integers is again an integer, we can write axu = s, yv = t, where s, t∈ℤThus, we get as +bct = 1 ⇒gcd(a, bc) = 1b) To prove that for given integers, a, b, c such that a | bc and gcd(a, b) = 1, we get a | c We have, a | bc ⇒bc = am, m ∈ℤ and a | bc ⇒a | b or a | c But gcd(a, b) = 1 ⇒a| b ⇒a | c c) To prove that for given integers, a, b, we have gcd(a, b) = gcd(b, r), where r is the remainder when a is divided by b. Part 1: Suppose d = gcd(b, r) ⇒d | b and d | r. But, r = a - bq, q∈ℤ. Then, we get a = bq+r, and d |b, d |r, so d| bq+r. This gives d | a, and d | b (already known). Therefore, gcd(b, r) = d ≤ gcd(a, b) ......(1)Part 2: Now let e = gcd(a, b).Then we know that a - bq = r. As, e | a, and e | b, we get e | a -bq ⇒e | r Therefore, gcd(a, b) = e ≤ gcd(b, r) ......(2)From (1) and (2), we get that gcd(a, b) = gcd(b, r)