Proofs and Prime Numbers

What does ℕ represent?

The natural numbers (counting numbers) {1, 2, 3, 4} which may sometimes include 0 depending on the context and can be written ℕ₀

What does ℤ represent?

The integers (whole numbers including negatives) {-2, -1, 0, 1, 2}

What does ℚ represent?

The rational numbers (numbers that can be written as fractions) {-1/2, 1, 2/3}

What does ℝ represent?

The real numbers (all points on the number line) {-√2, π, −3}

What does ℂ represent?

The complex numbers (numbers of the form a + bi) {-2, 2 + 3i, 4i}

What does a divides b mean and how is it written?

a divides b if there exists an integer k such that b = ak and is written a | b

What divisibilities including 0 are true?

a | 0 is true for all a since 0 = a x 0

0 | a is not true as a / 0 is undefined unless a is also 0

What are the properties of divisibility?

If a | b and b | c, then a | c
If a | b and a | c, then a | (b±c)

If a | b, then a | kb for any integer k

How do you prove If a | b and a | c, then a | (b+c)

Since a | b, ∃ m ∈ ℤ such that b = am
Since a | c, ∃ n ∈ ℤ such that c = an
Then b+c = am+an = a(m+n)
As m+n is an integer, a | (b+c)

What is a composite number?

A natural number n ∈ N is called a composite number if n 6= 1 and there exist a, b ∈ N with 1 < a, b < n such that n = ab.

What are Mersenne numbers?

Numbers of the form 2^p - 1

What is Euclid’s theorem?

Proof of infinite primes:

Assume, for contradiction, that there are finitely many primes:

p₁, p₂, p₃, …, p_n

Let N = p₁p₂…p_n + 1 (form a new number by multiplying all the primes together and adding 1)

When you divide N by any of the primes p_i you always get a remainder of 1 because N = (p₁p₂…p_n) + 1 = kp_i + 1 for some integer k so no p_i divides N

Hence, N is either prime itself, or divisible by some new prime not in the list.

Therefore, the assumption of finitely many primes is false. Hence, there are infinitely many primes.

What is the proper definition of a prime number?

Let a, b ∈ Z. We say that a is a factor of b if there exists z ∈ Z such that b = az.

We write a | b to mean that a is a factor of b, and a -| b to mean that a is not factor of b.

What is a theorem regarding Mersenne and composite numbers?

Let n ∈ N. Suppose that n is composite. Then 2ⁿ − 1 is composite.