Math 115. Slides from Lecture of September 1

This handout contains the slides from the Lecture of September 1 (modified slightly at the end).

Theorem. Let b, c ∈ ℤ with b ≠ 0 or c ≠ 0 , and let

S = {xb + yc : x, y ∈ ℤ} .

Then:

(a). S ∩ ℤ_{>0} is nonempty, so S has a smallest positive element ℓ.

(b). S is equal to the set of multiples of ℓ ( S = ℓℤ).

(c). ℓ = gcd(b, c) .

(d). Let d ∈ ℤ. Then d is a common divisor of b and c ⟺ d | gcd(b, c) .

Proof. (a). If b ≠ 0 then |b| = ±b ∈ S ∩ℤ_{>0} ; otherwise c ≠ 0 and then |c| ∈ S ∩ℤ_{>0} . Therefore S ∩ ℤ_{>0} ≠ ∅. Let ℓ be as above.

(b). S ⊆ ℓℤ: Let a ∈ S. Write a = qℓ + r with q, r ∈ ℤ and 0 ≤ r < ℓ. Since a, ℓ ∈ S, we have

a = xb + yc and ℓ = x_{0}b + y_{0}c , with x, y, x_{0}, y_{0} ∈ ℤ .

Then r ∈ S, because

r = a − qℓ = (x − qx_{0})b + (y − qy_{0})c .

Now assume ℓ ∤ a. Then r ≠ 0 . But then r ∈ S and 0 < r < ℓ, contradicting the choice of ℓ. Therefore ℓ | a, so a ∈ ℓℤ.

S ⊇ ℓℤ: Let a ∈ ℓℤ, say a = nℓ for some n ∈ ℤ. Also, ℓ = x_{0}b + y_{0}c, so a = nℓ = (nx_{0})b + (ny_{0})c ∈ S, so a ∈ S.

(c). Let g = gcd(b, c) . Now b, c ∈ S, so ℓ | b and ℓ | c, so ℓ is a common divisor of b and c; therefore ℓ ≤ g.

On the other hand, ℓ = x_{0}b + y_{0}c is a multiple of g (Theorem 1.1(3)), so g ≤ ℓ (Theorem 1.1(5)). Therefore ℓ = g = gcd(b, c) .

(d). “ ⟹ ”: d | b and d | c ⟹ d | (x_{0}b + y_{0}c) = ℓ = gcd(b, c) .

“ ⟸ ”: d | gcd(b, c) ⟹ d | g and g | b; therefore d | b (Theorem 1.1(2)). Similarly, d | c. Therefore d is a common divisor. □

Theorem. Suppose n ∈ ℤ, n ≥ 2 , b_{1}, …, b_{n} ∈ ℤ, and b_{i} ≠ 0 for some i. Also let

S = {∑ x_{i}b_{i} : x_{1}, …, x_{n} ∈ ℤ} .

Then:

(a). S ∩ ℤ_{>0} is nonempty, so S has a smallest positive element ℓ.

(b). S is equal to the set of multiples of ℓ ( S = ℓℤ).

(c). ℓ = gcd(b_{1}, …, b_{n}) .

(d). Let d ∈ ℤ. Then d | b_{i} for all i ⟺ d | gcd(b_{1}, …, b_{n}) .

(e). If b_{i} ≠ 0 for some i < n, then

gcd(b_{1}, …, b_{n}) = gcd(gcd(b_{1}, …, b_{n−1}), b_{n}) .