Integers. Well Ordering Principle. Division & Euclidean Algorithm.

When you have eliminated the impossible, whatever remains, however improbable, must be the truth, Sherlock Holmes

 

Definition. An integer is a positive whole number, a negative whole number, or 0, with no fractional parts or decimals. The set of integers is often denoted by the boldface ℤ.

More formally, we could define an equivalence relation on the set of all ordered pairs of natural numbers (a, b), a, b ∈ ℕ as follows: (a, b) ~ (c, d) ↭ a + d = c + b. The set of integers is the set of all equivalence classes of such ordered pairs. ℤ = {[a, b]: (a, b) ∈ ℕ²}

We can define integer addition and multiplication as two maps +: ℤ x ℤ → ℤ, ·: ℤ x ℤ → ℤ,: [(a, b)] + [(c, d)] = [(a + c, b + d)], [(a, b)] · [(c, d)] = [(ac + bd, ad + bc)]

It is closed under the operations of addition and multiplication, that is, the sum and product of any two integers is an integer, too.

Properties of Integers

• Distributivity: a x (b + c) = (a x b) + (a x c), (a + b) x c = (a x c) + (b x c).
• No zero divisor: if a x b = 0, then a = 0, b = 0, or both.

These properties state that (ℤ, +) is an Abelian group, and (ℤ, +, x) is a commutative ring with unity.

Well Ordering Principle. Every nonempty set of positive integers contains a smallest member.

Divisibility Basics

Definition. Given a, b ∈ ℤ, with a ≠ 0, we say a divides b and write a | b if b = ak for some k ∈ ℤ, e.g., 2 | 16 (16 = 2·8), 3 | 15 (15 = 3·5), but 2 ɫ 27.

$a \mid b$ and $a \nmid b$ are written in LaTeX as a \mid b and a \nmid b respectively.

Proposition. Properties of Division

1. If a | b and b | c, then a | c.
2. If a | b then ca | cb.
3. If a | b and a | c, then ∀x, y ∈ ℤ, a | (bx + cy).
4. If a | 1, then a = ± 1.

Division Algorithm. Let a, b ∈ ℤ, b > 0. Then, there exist unique integers q and r such that a = bq + r, 0 ≤ r < b.

Proof.

Consider the set S = {a - bx | x ∈ ℤ, a - bx ≥ 0}. We claim that S ≠ ∅. There are two cases:

1. a ≥ 0. Let’s set x as zero, then a -b·0 = a ∈ S.
2. a < 0. Let’s set x as a, then a -ba = a(1 -b) ≥ 0 because a, b ∈ ℤ, a < 0 and b > 0 (1 -b ≤ 0) ⇒ a -ba ∈ S.

Therefore, S ≠ ∅ ⇒ By the Well Ordering Principle, it contains a small element. Let r = min(S), then r ≥ 0. Let q be the corresponding x value, r = a -bq ⇒ a = bq + r.

By reduction to the absurd, let’s suppose that r ≥ b ⇒ r = a -bq ≥ b ⇒ r -b = a -b(q + 1) ≥ b - b = 0 ⇒ r -b ∈ S but r-b < r = min(S) ⊥

Let’s prove the uniqueness, and suppose that q, q’, and r, r’ are such that a = bq + r = bq’ + r’, 0 ≤ r < b and 0 ≤ r’ < b. Let’s assume that r’ ≥ r.

a = bq + r = bq’ + r’ ⇒ bq -bq’ = r’ -r ⇒ b(q -q’) = r’ -r ⇒ LHS = RHS = 0 because the only multiple of b (LHS = b(q -q’) is a multiple of b ) that is between 0 and b but does not include b (0 ≤ r < b, 0 ≤ r’ < b, r’ ≥ r ⇒ RHS: 0 ≤ r’ -r < b) is zero ⇒ r’ = r and q = q’∎

Example: If a = 9 and b = 2, the division algorithm gives 9 = 4·2 + 1, q = 4, r = 1, 0 ≤ 1(r) < 2(b). If a = 14 and b = 23, then 14 = 23·0 + 12, q = 0, r = 12, and 0 ≤ 12(r) < 23(b).

An integer d is called a common divisor of a and b if d | a and d | b. The greatest common divisor of two nonzero integers a and b is the greatest positive integer d such that d is a divisor of both a and b, i.e. d is a common divisor of a and b and if d’ is any other common divisor of a and b, then d’ | d. It is generally denoted by gcd(a, b), e.g., gcd(8, 12) = 4, gcd(54, 24) = 6.

Two numbers, say a and b, are called relatively prime or coprime, if their greatest common divisor equals 1, i.e., gcd(a, b) = 1.

Examples:

• gcd(12, 18) = gcd(2²·3, 3²·2) = [The greatest common divisor is the product of the lowest powers of all the common factors] gcd (2·3) = 6.
• gcd(12, 36) = gcd(2²·3, 3²·2²) = gcd (2²·3) = 12.
• gcd(78, 54) = gcd(2·3·13, 2·3³) = 6.

Bézout’s identity Let a and be non-zero integers with greatest common divisor d, then there exists x, y ∈ ℤ, such that ax + by = d. Written more concisely in letters, ∀a, b ∈ ℤ, ∃x, y ∈ ℤ: gcd(a, b) = ax + by.

Proof.

Let consider the set S = {ax + by | x, y ∈ ℤ, ax + by > 0} ⊆ ℕ. First, we establish that S ≠ ∅, there are four possibilities:
a > 0 ⇒ 1·a + 0·b ∈ S
a < 0 ⇒ (-1)·a + 0·b ∈ S
b > 0 ⇒ 0·a + 1·b ∈ S
b < 0 ⇒ 0·a + (-1)·b ∈ S

As by assumption, it is not the case that both a = b = 0, then S ≠ ∅ ⇒ [By the Well Ordering Principal] ∃d = min(S).

We claim that d = gcd(a, b). First, take into consideration that d = min(S), so d = ax₀ + by₀ for some x₀, y₀ ∈ ℤ.

Claim: d | a. By Reductio ad absurdum, let’s suppose that d ɫ a ⇒ [Division algorithm] a = dq + r with 0 < r < d (0 < r because d ɫ a).

d = ax₀ + by₀ ⇒ [*q] dq = aqx₀ + bqy₀ ⇒ a - r = [a = dq + r ⇒ a - r = dq] aqx₀ + bqy₀ ⇒ r = (1 -x₀q)a -(qy₀)b, 0 < r < d, r ∈ S, r < d = min(S) ⊥ By a similar argument, d | b.

Let’s prove that it is the greatest common divisor indeed. Let c ∈ ℕ such that c | a and c | b ⇒ [Properties of Division, 3.] c | (ax + by) ∀x, y ∈ ℤ. In particular, c | (ax₀ + by₀), and therefore c | d = gcd(a, b)∎

Euclidean Algorithm

The Euclidean Algorithm is an easy and efficient way of calculating the GCD of two integers. If n goes into x and y, it must go into x-y. In other words, gcd(x, y) = gcd(x -y, y). Therefore, we can subtract the smaller integer from the larger integer until the remainder is less than the smaller integer. A significant improvement in performance is possible, however, by using the remainder operator (%) rather than subtraction. We keep going until the remainder is 0, and thus leaving us with the GCD.

Examples.

• gcd(7469, 2464)

1. 7469 = 2464 · 3 + 77. In the following step, we replace 7469, 2464 by 2464 and 77 because gcd(7469, 2464) = gcd(77, 2464)
2. 2464 = 77 · 32 + 0. The gcd is the last remainder different from zero, gcd(7469, 2464) = 77.

• gcd(1819, 3587)

1. 3587 = 1819 · 1 + 1768
2. 1819 = 1768 · 1 + 51
3. 1768 = 51 · 34 + 34
4. 51 = 34 · 1 + 17
5. 34 = 17 · 2 + 0. Therefore, gcd(1819, 3587) = 17.

Now we are going to use the equations above to build 17 as a linear combination of 1819 and 3587. 17 = [4] 51 - 34 = [3] 51 - (1768 -51·34) = (1+34)·51 - 1768 = 35·51 -1768 = [2] 35·(1819 - 1768) -1768 = 35·1819 -36·1768 = [1] 35·1819 -36·(3587 - 1819) = (35+36)·1819 - 36·3587 = 71·1819 - 36·3587. Thus, 17 = 71·1819 - 36·3587.

Definition. Let p ∈ ℤ, p > 1. We say that p is a prime number if the only divisors of p are 1 and p itself. Otherwise, p is said to be composite.

Corollary. If a and b are relatively prime or coprime, then there exist x, y ∈ ℤ, such that gcd(a, b) = ax + by = 1, e.g., gcd(4, 15) = 1 = 4 x 4 + 15 x (-1) .

Euclid’s Lemmma. If a prime number p divides the product ab of two integers a and b, then p must divide at least one of those integers a or b. Written more concisely, if p is prime, p | ab, then either p | a or p | b.

For example, if p = 7, a = 56, b = 12, then ab = 672, and since ab = 672 is divisible by 7 (7 | 672), Euclid’s lemma implies that one or both of 56 and 12 are divisible by 7 as well. In fact, 56 = 8·7 (7 | 56).

p is required to be prime. Otherwise, Euclid’s Lemma may fail, e.g., 6 | (4·3), but 6 ɫ 4 and 6 ɫ 3.

Proof.

Suppose p is prime, p | ab. If p | a, then we are done.

Suppose p is prime, p ɫ a ⇒ [Corollary. If a and b are relatively prime or coprime, then there exist x, y ∈ ℤ, such that gcd(a, b) = ax + by = 1,] ∃x, y ∈ ℤ, ax + py = 1 ⇒ b = abx + pyb ⇒ [Proposition. Properties of Division 3. If a | b and a | c, then ∀x, y ∈ ℤ, a | (bx + cy), and p | ab and p | pyb] p | b ∎

Theorem. There exist infinitely many prime numbers.

Proof.

For the sake of contradiction, let’s suppose there are only a finite number of primes, p₁, p₂,…, p_r. Let q = p₁·p₂···p_r + 1.

If q is composite ⇒ there must be divisible by some prime number, say p_i for some i ⇒ [p_i|q and p_i | p₁·p₂···p_r. Proposition. Properties of Division 3. If a | b and a | c, then ∀x, y ∈ ℤ, a | (bx + cy)] p_i|q - p₁·p₂···p_r = 1, that is, p_i|1 ⊥ (p_i = 1 that is not a prime number).

Therefore, q must be a prime number, but by construction q > p_i ∀i ⊥

Fundamental Theorem of Arithmetic. Every integer greater than 1 is a prime or can be represented or written as a product of prime numbers. This product is unique up to reordering, that is, if n = p₁^α₁p₂^α₂ ··· p_k^α_k = $\prod_{i=1}^{k}p_i^{α_i}$ and n = q₁^β₁q₂^β₂ ··· q_l^β_l = $\prod_{i=1}^{l}q_i^{β_i}$, where the p’s and q’s are primes, then k = l and, after renumbering or renaming the q’s, we have p_i = q_i and α_i = β_i ∀i.

36 = 2²·3², 126 = 2·3²·7, 999 = 3³·37. The Fundamental Theorem of Arithmetic states that 999 can be represented as a product of primes and that no matter how this is done, there will always be exactly three 3s and one 37.

Proof.

For the sake of contradiction, let’s suppose that there is a natural number without such a representation. Let m be the smallest number without such a representation, that is, without being able to factor into a product of primes.

Notice that m must be composite, m = ab where 1 < a, b < m. Obviously, as a, b < m ⇒ a and b are either prime numbers or they can be written as product of primes ⇒ m = a·b can be written as product of primes ⊥

Suppose n = p₁^α₁p₂^α₂ ··· p_k^α_k = q₁^β₁q₂^β₂ ··· q_l^β_l.

Notice that p_i | LHS ∀i, so p_i | q₁^β₁q₂^β₂ ··· q_l^β_l ⇒ [Euclid’s Lemmma. If a prime number p divides the product ab of two integers a and b, then p must divide at least one of those integers a or b. ] p_i | q_r^β_r for some r ⇒ p_i | q_r, and q_r prime ⇒ p_i = q_r. Therefore, every prime in RHS, p_i, is a prime in LHS, but by a similar argument every prime in LHS is a prime in RHS ⇒ k = l, ∀i, p_i = q_r for some r.

After some reordering and renaming, p_i = q_i ⇒ p₁^α₁p₂^α₂ ··· p_k^α_k = p₁^β₁p₂^β₂ ··· p_k^β_k.

By reduction to the absurd, let’s suppose α_i ≠ β_i, and α_i > β_i ⇒ [Let’s divide by p_i^β_i] p₁^α₁p₂^α₂ ··· p_i-1^α_i-1p_i^α_i-β_ip_i+1^α_i+1 ··· p_k^α_k = p₁^β₁p₂^β₂ ··· p_i-1^β_i-1p_i+1^β_i+1 ··· p_k^β_k ⇒ [p_i | LHS ⇒ p_i | RHS ] ⇒ p_i | p_j for i ≠ j ⊥ Therefore, α_i = β_i.

Definition. The least common multiple or smallest common multiple of two non-zero integers a and b, typically denoted by lcm(a, b), is the smallest positive integer that is a multiple of (or divisible by) both a and b.

Theorem. The product of the least common multiple and the greatest common divisor of two numbers equals the product of both numbers, i.e., lcm(a, b) = $\frac{|ab|}{gcd(a, b)}$

Proof:

From the Fundamental Theorem of Arithmetic, we can write n and m as a product of primes, m = p₁^k₁p₂^k₂···p_r^k_r, n = p₁^l₁p₂^l₂···p_r^l_r, where some (or many) of these powers are obviously zero.

Futhermore, lcm(m, n) = p₁^{max{k₁, l₁}}p₂^{max{k₂, l₂}}···p_r^{max{k_r, l_r}}, gcd(m, n) = p₁^{min{k₁, l₁}}p₂^{min{k₂, l₂}}···p_r^{min{k_r, l_r}}.

gcd(m, n)·lcm(m, n) = [min{k_i, l_i} + max{k_i, l_i} = k_i + l_i] p₁^{k₁ + l₁}p₂^{k₂ + l₂}···p_r^{k_r + l_r} = p₁^k₁p₂^k₂···p_r^k_r · p₁^l₁l₂^l₂···p_r^l_r = m · n ∎

The least common multiple is the product of each prime factor raised to the highest power. Examples:

• lcm (21, 6) = lcm(3·7, 2·3) = 3·7·2 = 42 = $\frac{21·6}{3}$.
• lcm(4, 6) = lcm(2², 2·3) = 2²·3 = 12 = $\frac{4·6}{2}$.
• lcm (126, 24) = lcm(2·3²·7, 2³·3) = 2³·3²·7 = 504 = $\frac{126·24}{6}$ where gcd(126, 24) = gcd(2·3²·7, 2³·3) = 2·3 = 6.