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:

iteration123456
x662414248166822
y4142481668220
r2481668220

⇒ .


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).