Corollary 1.3.7. Let a, b 1 , and b 2 be integers such that a and b 1 are coprime, and so are a and b 2 . Then a is coprime with b 1 b 2 .

Proof. The following relations hold:

1 = αa + β 1 b 1 ,

1

=

′

α

a

+

β2

b2

.

By multiplying them, we get

1 = (αα ′ a + α β 2 b 2 + α ′ β 1 b 1 )a + ( β 1 β 2 )(b 1 b 2 ),

proving the claim.

⊔⊓

Corollary 1.3.8. Let a, b, and n be integers such that a | n, b | n and GCD(a, b) = 1. Then ab | n.

Proof. We have n = n 1 a = n 2 b. Moreover, a relation of the form (1.15) holds. Multiplying it by n we get

n = αna + β nb = αn 2 (ab) + β n 1 (ab),

proving the claim.

⊔⊓ 1.3 The Euclidean algorithm

19

Corollary 1.3.9. Let a and b be two coprime positive integers, and let n be any integer. If a | bn then a | n.

Proof. By hypothesis there exists an integer m such that

bn = am.

(1.16)

By B´ezout’s identity, there exist integers α and β satisfying equation (1.15). Multiplying both sides of this equation by n and keeping in mind equation (1.16), we get

n = αan + β bn = αan + β am;

hence, a | n.

⊔⊓

Notice that the expression for GCD(a, b) yielded by equation (1.14) is not at all unique. For instance: 1 = 3 · 7 + (−4) · 5 = (−2) · 7 + 3 · 5.