| For any integer n > 1, there exists a prime number p such that p | n. |
Examples:
n = 2 p = 2 2|2
n = 3 p = 3 3|3
n = 7 p = 7 7|7
p p p p
Theorem: Unique Factorization Theorem - Given any integer n > 1, there exists a positive integer k and distinct prie numbers p1, p2, …, pk and positive integers e1, e2, …, ek such that n = p1, p2, …, pk and this factorization is unique (disreguarding the order of factors).
Contradiction rule ~p => c (Where c is a contradiction)
Therefore P
Proof by Contradiction
Suppose, to the contrary, that p is false.
.
.
.
[Show some contradiction]
Therefore, P.
Example
Theorem: There is no greatest integer.
Suppose, to the contrary, that there is a greatest integer, say N.
However, N + 1 is an integer and N + 1 > N.
Threrfore, there is no greater integer.
Example
Theorem: There is no smallest positive real number.
Example
Theorem: The square root of 2 is irrational.
Suppose, to the contrary, that the square root of 2 is rational.
Then there exist integers a and b with b != 0 such that the square root of 2 != a/b and we assume that a/b is in lowest terms.
Squaring both sides, we have 2 = a^2/b^2 or 2b^2 = a^2.
Now since b^2 is an integer, 2b^2 is even.
Thus a^2 is even, which implies a is even.
Thus a = 2k for some integer k. It follows that 2b^2 = (2k)^2 = 4k^2.
So b^2 = 2k^2. Hence b^2 is even, implying b is even.
So b = 2l for some integer l. But this contradicts that a/b is in lowest terms.
Therefore the square root of 2 is irrational.
Alternate Example
Unique Factorization Theorem
Example
Lemma: For any integer a and prime p, if p|a, then p /| (a+1).
Proof: Suppose not. That there exists an integer a and a prime p such that p|a and p|(a+1).
Then a = pr for some integer r
and a+1 = ps for some integer s.
Subtracting, we get 1 = a + 1 = a = ps - pr = p(s-r).
Thus p|1. So p = 1 or p = -1.
This contridicts that p is prime (p >= 2).
Example
Theorem: There are infinately many primes.
Proof: Suppose to the contrary, that there are finitely many primes p1, p2, …, pk. Let a = p1, p2, …, pk. Notice that each pi divides a.
Thus pi /| (a+1). So the integer a+1 has no other prime divisors and thus must be prime.
But this contradicts that the list of p1, p2, …, pk contained all possible primes.
Two integers m and n have the same parity if they are either both even or both odd.
Theorem: For every two integers m and n, 3m + 5 is even if and only if m and n have the same parity.
Proof (<=) Proove if m and n have the same parity, then 3m + 5n is even.
Assume m and n have the same parity.
Case 1: m and n are both even.
[Proove 3m + 5n is even]
Case 2: m and n are both odd.
[Proove 3m + 5n is even.](=>) Prove if 3m + 5n is even, then m and n have the same parity (by contrapositive).
Assume m and n have opposite parity.
Case 1: m is even and n is odd.
[Prove 3m + 5n is odd.]
Case 2: m is odd and n is even.
[Proove 3m + 5n is odd.]
Result: For any sets A, B, and C, (A-B) ⋃ (A-C) = A - (B ⋂ C)
Proof: First we show (A-B) ⋃ (A-C) ⊆ A - (B ⋂ C)
Let x ∈ (A-B) ⋃ (A-C).
Then x x ∈ A-B OR x ∈ A-C
Case 1: x ∈ A - B
[Show x ∈ A - (B ⋂ C)]
Case 2: x ∈ A - C
[Show x ∈ A - (B ⋂ C)]