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.

Tables | Addition | Multiplication |
---|---|---|

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.

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**

- If a | b and b | c, then a | c.
- If a | b then ca | cb.
- If a | b and a | c, then ∀x, y ∈ ℤ, a | (bx + cy).
- 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:

- a ≥ 0. Let’s set x as zero, then a -b·0 = a ∈ S.
- 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
^{2}·3, 3^{2}·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
^{2}·3, 3^{2}·2^{2}) = gcd (2^{2}·3) = 12. - gcd(78, 54) = gcd(2·3·13, 2·3
^{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_{0} + by_{0} for some x_{0}, y_{0} ∈ ℤ.

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_{0} + by_{0} ⇒ [*q] dq = aqx_{0} + bqy_{0} ⇒ a - r = [a = dq + r ⇒ **a - r = dq**] aqx_{0} + bqy_{0} ⇒ r = (1 -x_{0}q)a -(qy_{0})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_{0} + by_{0}), and therefore c | d = gcd(a, b)∎

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)

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

- gcd(1819, 3587)

- 3587 = 1819 · 1 + 1768
- 1819 = 1768 · 1 + 51
- 1768 = 51 · 34 + 34
- 51 = 34 · 1 + 17
- 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_{1}, p_{2},…, p_{r}. Let q = p_{1}·p_{2}···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_{1}·p_{2}···p_{r}. Proposition. **Properties of Division** 3. If a | b and a | c, then ∀x, y ∈ ℤ, a | (bx + cy)] p_{i}|q - p_{1}·p_{2}···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_{1}^{α1}p_{2}^{α2} ··· p_{k}^{αk} = $\prod_{i=1}^{k}p_i^{α_i}$ and n = q_{1}^{β1}q_{2}^{β2} ··· 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^{2}·3^{2}, 126 = 2·3^{2}·7, 999 = 3^{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.

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 = 3^{3}·37 = 3^{3}·37·1 = 3^{3}·37·1^{2} = ···

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_{1}^{α1}p_{2}^{α2} ··· p_{k}^{αk} = q_{1}^{β1}q_{2}^{β2} ··· q_{l}^{βl}.

Notice that p_{i} | LHS ∀i, so p_{i} | q_{1}^{β1}q_{2}^{β2} ··· 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_{1}^{α1}p_{2}^{α2} ··· p_{k}^{αk} = p_{1}^{β1}p_{2}^{β2} ··· p_{k}^{βk}.

By reduction to the absurd, let’s suppose α_{i} ≠ β_{i}, and α_{i} > β_{i} ⇒ [Let’s divide by p_{i}^{βi}] p_{1}^{α1}p_{2}^{α2} ··· p_{i-1}^{αi-1}p_{i}^{αi-βi}p_{i+1}^{αi+1} ··· p_{k}^{αk} = p_{1}^{β1}p_{2}^{β2} ··· p_{i-1}^{βi-1}p_{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_{1}^{k1}p_{2}^{k2}···p_{r}^{kr}, n = p_{1}^{l1}p_{2}^{l2}···p_{r}^{lr}, where some (or many) of these powers are obviously zero.

Futhermore, lcm(m, n) = p_{1}^{max{k1, l1}}p_{2}^{max{k2, l2}}···p_{r}^{max{kr, lr}}, gcd(m, n) = p_{1}^{min{k1, l1}}p_{2}^{min{k2, l2}}···p_{r}^{min{kr, lr}}.

gcd(m, n)·lcm(m, n) = [min{k_{i}, l_{i}} + max{k_{i}, l_{i}} = k_{i} + l_{i}] p_{1}^{k1 + l1}p_{2}^{k2 + l2}···p_{r}^{kr + lr} = p_{1}^{k1}p_{2}^{k2}···p_{r}^{kr} · p_{1}^{l1}l_{2}^{l2}···p_{r}^{lr} = 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}, 2·3) = 2^{2}·3 = 12 = $\frac{4·6}{2}$. - lcm (126, 24) = lcm(2·3
^{2}·7, 2^{3}·3) = 2^{3}·3^{2}·7 = 504 = $\frac{126·24}{6}$ where gcd(126, 24) = gcd(2·3^{2}·7, 2^{3}·3) = 2·3 = 6.