# 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) ∈ ℕ2}

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

Closure a + b ∈ ℤ a x b ∈ ℤ
Associative a + (b + c) = (a + b) + c a x (b x c) = (a x b) x c
Commutativity a + b = b + a a x b = b x a
Existence of an identity element a + 0 = a a x 1 = a
Existence of inverse elements a + (-1) = 0 The only invertible integers are -1 and 1
• 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(22·3, 32·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(22·3, 32·22) = gcd (22·3) = 12.
• gcd(78, 54) = gcd(2·3·13, 2·33) = 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 = ax0 + by0 for some x0, y0 ∈ ℤ.

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 = ax0 + by0 ⇒ [*q] dq = aqx0 + bqy0 ⇒ a - r = [a = dq + r ⇒ a - r = dq] aqx0 + bqy0 ⇒ r = (1 -x0q)a -(qy0)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 | (ax0 + by0), 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, p1, p2,…, pr. Let q = p1·p2···pr + 1.

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

Therefore, q must be a prime number, but by construction q > pi ∀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 = p1α1p2α2 ··· pkαk = $\prod_{i=1}^{k}p_i^{α_i}$ and n = q1β1q2β2 ··· qlβ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 pi = qi and αi = βi ∀i.

36 = 22·32, 126 = 2·32·7, 999 = 33·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.

The Fundamental Theorem of Arithmetic is one of the main reasons why 1 is not considered a prime number. if 1 were prime, then factorization into primes would not be unique, e.g., 999 = 33·37 = 33·37·1 = 33·37·12 = ···

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 = p1α1p2α2 ··· pkαk = q1β1q2β2 ··· qlβl.

Notice that pi | LHS ∀i, so pi | q1β1q2β2 ··· qlβ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. ] pi | qrβr for some r ⇒ pi | qr, and qr prime ⇒ pi = qr. Therefore, every prime in RHS, pi, is a prime in LHS, but by a similar argument every prime in LHS is a prime in RHS ⇒ k = l, ∀i, pi = qr for some r.

After some reordering and renaming, pi = qi ⇒ p1α1p2α2 ··· pkαk = p1β1p2β2 ··· pkβk.

By reduction to the absurd, let’s suppose αi ≠ βi, and αi > βi ⇒ [Let’s divide by piβi] p1α1p2α2 ··· pi-1αi-1piαiipi+1αi+1 ··· pkαk = p1β1p2β2 ··· pi-1βi-1pi+1βi+1 ··· pkβk ⇒ [pi | LHS ⇒ pi | RHS ] ⇒ pi | pj 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 = p1k1p2k2···prkr, n = p1l1p2l2···prlr, where some (or many) of these powers are obviously zero.

Futhermore, lcm(m, n) = p1max{k1, l1}p2max{k2, l2}···prmax{kr, lr}, gcd(m, n) = p1min{k1, l1}p2min{k2, l2}···prmin{kr, lr}.

gcd(m, n)·lcm(m, n) = [min{ki, li} + max{ki, li} = ki + li] p1k1 + l1p2k2 + l2···prkr + lr = p1k1p2k2···prkr · p1l1l2l2···prlr = 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(22, 2·3) = 22·3 = 12 = $\frac{4·6}{2}$.
• lcm (126, 24) = lcm(2·32·7, 23·3) = 23·32·7 = 504 = $\frac{126·24}{6}$ where gcd(126, 24) = gcd(2·32·7, 23·3) = 2·3 = 6.
Bitcoin donation