# CMPUT272 Lecture Notes - Lecture 14: Empty Set, Delaware Route 1, Public-Key Cryptography

For unlimited access to Class Notes, a Class+ subscription is required.

October 23 2014

ETLC 2-001

Thereom: There are infinitely many primes

Lemma: a,b,c,d such that a = b + c, (d|a d|b) d | c∀ ∈ℤ ∧ ⟹

Proof:

Proof by contradiction

Suppose that they are finite.

Let P = {p1, p2, ..., pk} be the finite set of primes

Let n = (p1 p2 ... pk) + 1.⋅ ⋅ ⋅

n is not prime - it's too big to be in P.

Therefore, it is composite, and some prime divides it. Pj|n

Also, Pj|(p1 p2 ... pk).⋅ ⋅ ⋅

Therefore Pj|1 - This contradicts the definition of prime.

⎕

Thereom: Fundemental Thereom of Arithemitic

Every integer n ≥ 2 can be written in a unique way as the product of primes.

Sum (of any empty set)

3

---

\ i = 0

/

---

i=4

Product Sum (of an empty set)

_3__

| | = 1

| |

i=4

Proof:

Every integer ≥ 2 is a product of primes, by theorem proved earlier

We need to show that the prime factorization is unique

Base case: n=2. The fectorization is unique. It's just 2.

Inductive step:

Let n > 2.

Assume IH: i, 2≤i<n, the prime factorization is unique∀

If n is prime, its factorization is unique

Suppose n is composite

Suppose n has prime factorizations

n = p1^e1 p2^e2 ... pk^ek = q1^f1 q2^f2⋅ ⋅ ⋅ ⋅

... qj^fj⋅ ⋅

(all p and q are prime)

p1 < ... < pk and q1 < ... < qj

Now, p1|n. Therefore p1|(q1^f1 q2^f2 ... qj^fj)⋅ ⋅ ⋅

Therefore, by lemma 2, p1|ql for some 1≤l≤j