1. Primes
Definition 1
- An integer is prime if its only positive factors are and .
- An integer that is not prime is composite ⇔ there is with and .
Theorem 1 — Fundamental Theorem of Arithmetic
Every integer can be written uniquely as a prime or a product of primes in non-decreasing order.
| factorization | |
|---|---|
| 100 | |
| 641 | (prime) |
| 999 | |
| 1024 |
(Existence is proved in §5.2; uniqueness is proved at the end of this section.)
Theorem 2 — small prime divisor
If is composite, has a prime divisor .
Proof: with . If both then — contradiction. So one factor is , and it is prime or has a smaller prime divisor.
Trial division
Primality test: is prime iff no prime divides it.
- : primes are 2, 3, 5, 7; none divides 101 ⇒ prime.
Factorization procedure: divide by successive primes starting at 2. When a factor is found, continue factoring starting from (it has no smaller factors). Stop when what remains is prime.
Example: (). 2, 3, 5 fail; ; ; (prime).
Theorem 3 — There are infinitely many primes (Euclid)
Proof by contradiction: suppose are all the primes. Let . If some then — impossible. So is prime or has a prime factor not in the list. Contradiction.
Theorem 4 — Prime Number Theorem
where = number of primes (conjectured by Gauss and Legendre).
- Probability a random integer near is prime .
- Near : (double the odds by only trying odd numbers).
2. Greatest Common Divisor and Least Common Multiple
Definition 2 — gcd
For not both zero, is the largest with and .
- For : , , .
Definitions 3 & 4
- are relatively prime if . e.g. .
- are pairwise relatively prime if for all . e.g. 10, 17, 21.
Definition 5 — lcm
= smallest positive integer divisible by both and .
Using prime factorizations
If and (same primes, zero exponents allowed):
Examples
- , ⇒ .
- .
Theorem 5
3. The Euclidean Algorithm
Lemma 1
If , then .
Proof: is a linear combination of and , and is a linear combination of and ; by Corollary 1 (§4.1) they have exactly the same common divisors.
The algorithm
With , divide repeatedly:
Remainders strictly decrease, so a 0 is reached. Then = the last nonzero remainder.
procedure gcd(a, b: positive integers)
x := max(a, b)
y := min(a, b)
while y ≠ 0
r := x mod y
x := y
y := r
return x
Example 1: : , , ⇒ 7.
Example 2:
| iteration | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| x | 662 | 414 | 248 | 166 | 82 | 2 |
| y | 414 | 248 | 166 | 82 | 2 | 0 |
| r | 248 | 166 | 82 | 2 | 0 |
⇒ .
4. Bézout’s Theorem
Theorem 6 — Bézout
For positive there exist integers with
are Bézout coefficients; the equation is Bézout’s identity. e.g. .
Method: run Euclid, then substitute backwards
Example: express .
Back-substitute:
Lemma 2
If and , then .
Proof: ; divides both terms, so .
Lemma 3
If is prime and , then for some .
Uniqueness of prime factorization
Suppose in two different ways. Cancel common primes to get with no prime on both sides. By Lemma 3, divides some — impossible for distinct primes. So the factorization is unique.
Theorem 7 — when you can divide a congruence
If and , then .
Proof: and ⇒ (Lemma 2).