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

40 views3 pages

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
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class