Prime Numbers and Prime Divisors

Primes

• A prime number is a positive integer greater than 1 that is divisible only by 1 and itself.
• The first ten prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.
• A composite number is a positive integer greater than 1 that is not prime.
• The first ten composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, and 18.
• The number 1 is neither prime nor composite.

Lemma 1.1

• Every positive integer greater than one has a prime divisor.

Theorem 1.8

• There are infinitely many primes.
• Given the integer Qn = n! + 1, where n ≥ 1, Qn has at least one prime divisor denoted by qn.
• qn must be larger than n.
• If qn ≤ n, then qn | n!, and by Proposition 1.4, qn | (Qn – n)! which simplifies to qn | 1.
• Finding a prime number qn larger than n for any n ∈ N proves there must be infinitely many primes.

Theorem 1.9

• If n is a composite integer, then n has a prime factor not exceeding √n.
• A composite number n can be written as n = ab, where 1 < a ≤ b < n.
• It must have a ≤ √n.
• By Lemma 1.1, 'a' must have a prime divisor, which is also a divisor of 'n' and is less than or equal to √n.

Sieve of Eratosthenes

• A procedure for finding all primes less than or equal to a given positive integer n.
• To find primes less than or equal to 100, note that every composite integer less than 100 has a prime factor less than √100 = 10.

Primality Test

• Any method that determines whether a given positive integer n is prime.
• The sieve of Eratosthenes is used to generate primes less than or equal to 'n', but it is inefficient in determining whether a specific number 'n' is prime.

Prime Counter Function

• Denoted π(n), signifies the number of primes less than or equal to n.
• π(10) = 4
• π(100) = 25

Prime Number Theorem

• States that there are approximately x / log x prime numbers that are less than or equal to x for large values of x.
• lim (x→∞) π(x) / (x / log x) = 1

Log-Integral Function

• Denoted li, defined as li(x) = ∫ (from 2 to x) dt / log t
• lim (x→∞) π(x) / li(x) = 1

Proposition 1.8

• For any positive integer n, there are at least n consecutive composite positive integers.
• For n consecutive integers (n + 1)! + 2, (n + 1)! + 3, ..., (n + 1)! + (n + 1),, if 2 ≤ j ≤ n + 1, then j | (n + 1)!.
• By Proposition 1.4, j | (n + 1)! + j, making these n consecutive integers all composite.
• For example, the seven consecutive integers starting with 8! + 2 = 40322 are all composite, but are significantly larger than the first seven consecutive composites (90, 91, 92, 93, 94, 95, 96).

Twin Primes

• Twin primes are two primes p and p + 2.
• Examples of twin primes are 3 and 5, 5 and 7, 11 and 13, and 101 and 103.
• As of May 2018, the largest known twin primes are 2998630348952^(1290000) ± 1.
• The twin prime conjecture posits that there are infinitely many twin primes.

Goldbach's Conjecture

• Every even positive integer greater than two can be expressed as the sum of two primes.

Open Problems

• Are there infinitely many primes of the form n² + 1?

Fermat Number

• A Fermat number Fn is a positive integer in the form 2^(2n) + 1.
• A Fermat prime is a prime Fermat number.
• The only known Fermat primes are F1, F2, F3, and F4.
• F5 is not prime, and it is unknown if F6 and other larger Fermat numbers are primes.
• Is there any other Fermat prime aside from F1, F2, F3, F4?

Mersenne Number and Prime

• A Mersenne number Mn is a positive integer of the form 2^n – 1.
• A Mersenne prime is a prime Mersenne number.
• The largest known Mersenne prime, as of January 2018, is M77232917.
• The Great Internet Mersenne Prime Search (GIMPS) is a distributed computing project focused on discovering large Mersenne primes.