If an integer is not prime and is strictly greater then 1 it is composite
Prime Divisor Theorem
All composite integers have a prime divisor less than or equal to
Pf:
We first show that has a divisor
Since is composite and by def of divides ,
such that and WLOG
We show either or
using contradiction:
Suppose
Then , CONTR
Thus
We now show has a prime divisor
By the fundamental theorem of arthimetic, has a unique prime factorization. Therefore, is prime. Since is a prime divisor of with
Sieve of Eratosthenes
Because of Prime Divisor Theorem
Find all primes
When you find a prime number, remove all of its multiples
Repeat until you reach
Infinite Primes Theorem
There are infinitely many primes
Pf: Suppose there are not infinitely many prime, then there are a finite amount of primes. Then we can list them:
Let P =
Let Q = P + 1. Q must be compistive bc its larger then all primes. Thus such that q is prime and . Since Q is prime, . Thus , which implies q | 1$, which implies q = 1, which is not prime. CONTR, q is prime.
Mersenne Primes
, where is prime is a Mersenne prime. However, is prime does not neccessarily imply is prime.