Primality

Primality #

Programming Environment #

import math
from   numba  import jit, njit, prange
import numpy  as np
from   typing import Iterator

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 2
      1 import math
----> 2 from   numba  import jit, njit, prange
      3 import numpy  as np
      4 from   typing import Iterator

ModuleNotFoundError: No module named 'numba'

Questions

Given a composite integer, how do we find a decomposition into a product of integers larger than 1?
How do we recognize a prime integer?

Euclid’s Lemma #

$T h e o r e m$ [Bressoud 1.1 pp. 1-2]

If a prime divides the product of two integers then it must divide at least one of those integers.

\forall p \in P [P r i m e (p) ⟹ \forall a, b \in Z [(p ∣ a b) ⟹ ((p ∣ a) \lor (p ∣ b))]]

Note that the following cases hold as a consequence.

If a prime $p$ divides $a^{2}$ , then it must divide $a$ .

\forall p \in P [P r i m e (p) ⟹ \forall a \in Z [(p ∣ a^{2}) ⟹ (p ∣ a)]]

Therefore, if $p$ divides $a^{2}$ , then $p^{2}$ divides $a^{2}$ .

\forall p \in P [P r i m e (p) ⟹ \forall a \in Z [(p ∣ a^{2}) ⟹ (p^{2} ∣ a^{2})]]

The following theorem is a property which is characteristic of primes and is sometimes used to define them.

$T h e o r e m$ [Humphreys & Prest 1.3.1 pp. 26]

Let $p$ be a prime and let $a$ and $b$ be integers s.t. $p$ divides $a b$ .
$p$ divides either $a$ or $b$ .

\forall p \in P [P r i m e (p) ⟹ \forall a, b \in Z [(p ∣ a b) ⟹ ((p ∣ a) \lor (p ∣ b))]]

$P r o o f$ [Humphreys & Prest pp. 26]

The only positive divisors of $p$ are $1$ and $p$ since $p$ is prime.
Then either $g c d (p, a) = p$ or $g c d (p, a) = 1$ .

If $g c d (p, a) = p$ then $p ∣ a$ .

[Humphreys & Prest 1.1.6]

If $g c d (p, a) = 1$ then $p$ and $a$ are relatively prime.
Then there are integers $r$ and $s$ s.t. $1 = p r + a s ⟺ b = p b r + a b s = p (b r) + a b (s)$ .
Since $p$ divides $p (b r)$ and $p$ divides $a b (s)$ , $p$ divides their sum $b$ .

$∴$ if a prime divides a product then it divides one or the other factor.

$◼$

The following lemma is an extension of the previous theorem.

$L e m m a$ [Humphreys & Prest pp. 27]

Let $p$ be prime and let $p$ divide the product $a_{1} a_{2} \dots a_{r}$ .
Then $p$ divides at least one of $a_{1}, a_{2}, \dots, a_{r}$ .

$P r o o f b y i n d u c t i o n o n t h e n u m b e r r o f f a c t o r s a_{i}$ [Humphreys & Prest pp. 27]

Base Case

If $p ∣ a_{1}$ then $p ∣ a_{1}$ .

Induction Step

Induction Hypothesis: Let $p ∣ b_{1} b_{2} \dots b_{r - 1}$ so that $p$ divides at least one of $b_{1}, b_{2}, \dots, b_{r - 1}$ .
Let $p$ divide the product $a_{1} \dots a_{r}$ which we want to write as a product $b_{1} \dots b_{r - 1}$ of $r - 1$ integers.
Define $b_{i} = a_{i}$ for $i \leq r - 2$ and let $b_{r - 1}$ be the product $a_{r - 1} a_{r}$ .
Then $a_{1} a_{2} \dots a_{r - 2} (a_{r - 1} a_{r})$ is a product of $r - 1$ integers.
Either $p$ divides one of $a_{1}, a_{2}, \dots, a_{r - 2}$ or $p$ divides $a_{r - 1} a_{r}$ .
If the latter, then either $p$ divides $a_{r - 1}$ or $p$ divides $a_{r}$ .

Therefore $p$ divides one of $a_{1}, a_{2}, \dots, a_{r}$ .

$◼$

Prime Factorization #

$D e f i n i t i o n$ [Bressoud]

The decomposition of a positive integer into primes is called its factorization, which is expressed by

n = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times \dots \times p_{r}^{a_{r}}

where $p_{1}, p_{2}, \dots, p_{r}$ are distinct primes.

Relative Primality #

or coprimality

$D e f i n i t i o n$ [Bressoud pp. 3]

If integers $m$ and $n$ have no common primes in their respective factorizations then $m$ and $n$ are said to be relatively prime.

$E x a m p l e$ [Bressoud pp. 3]

$45 = 3 \times 3 \times 5$ and $98 = 2 \times 7 \times 7$ are relatively prime.

$D e f i n i t i o n$ [Humphreys & Prest pp. 12]

Let $a$ and $b$ be positive integers.
If $g c d (a, b) = 1$ then $a$ and $b$ are said to be relatively prime.

Does this hold for all integers?

$T h e o r e m$ [Humphreys & Prest 1.1.6 pp. 13]

Let $a$ , $b$ , and $c$ be positive integers with $a$ and $b$ relatively prime.
Then

if $a$ divides $b c$ then $a$ divides $c$

\forall a, b, c \in P [(R e l a t i v e P r i m e s (a, b) \land (a ∣ b c)) ⟹ (a ∣ c)]

if $a$ divides $c$ and $b$ divides $c$ then $a b$ divides $c$

\forall a, b, c \in P [(R e l a t i v e P r i m e s (a, b) \land (a ∣ c) \land (b ∣ c)) ⟹ (a b ∣ c)]

A generalization of Euclid's lemma?

$P r o o f$ [Humphreys & Prest 1.1.6 pp. 13]

Since $a$ and $b$ are relatively prime there are integers $s$ and $t$ st $1 = a s + b t$ by Bézout’s identity.
$1 = a s + b t ⟺ c = c a s + c b t = a (c s) + b c (t)$ .

Let $a ∣ b c$ .
Since $a ∣ a$ and $a ∣ b c$ it is the case that $a ∣ a (c s) + b c (t) = c$ .
$∴ a ∣ c$ .

Let $a ∣ c$
Then there is an integer $m$ such that $a m = c$ .
Let $b ∣ c$
Then there is an integer $n$ such that $b n = c$ .
$c = c a s + c b t = (b n) a s + (a m) b t = a b (n s) + a b (m t) = a b (n s + m t) ⟹ a b ∣ c$ .
$∴ a b ∣ c$ .

Alternatively

Let $a ∣ c$ .
$a ∣ c ⟹ a b ∣ c b ⟹ a b ∣ c b t$ .
Let $b ∣ c$ .
$b ∣ c ⟹ a b ∣ a c ⟹ a b ∣ c a s$ .
$∴ a b ∣ c a s + c b t = c$ .

$◼$

$C l a i m$

$m$ and $n$ are relatively prime iff $m^{2}$ and $n^{2}$ are relatively prime.
Let

$\begin{aligned} m & = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times \dots \times p_{r}^{a_{r}} \\ n & = p_{1}^{b_{1}} \times p_{2}^{b_{2}} \times \dots \times p_{r}^{b_{r}} \end{aligned}$

$g c d (m, n) = 1$ implies that $b_{i} = 0$ whenever $a_{i} > 0$ and vice versa.

$\begin{aligned} m^{2} & = p_{1}^{2 a_{1}} \times p_{2}^{2 a_{2}} \times \dots \times p_{r}^{2 a_{r}} \\ n^{2} & = p_{1}^{2 b_{1}} \times p_{2}^{2 b_{2}} \times \dots \times p_{r}^{2 b_{r}} \end{aligned}$

Pythagorean Triples #

[DEFINITION - (fundamental) Pythagorean triples]

Three integers $(x, y, z)$ which satisfy $x^{2} + y^{2} = z^{2}$ are called a Pythagorean triple. If they are all positive and have no common factors, then they are called a fundamental triple.

$\begin{aligned} \forall x, y, z \in P (P y t h a g o r e a n T r i p l e (x, y, z) ⟺ (x^{2} + y^{2} = z^{2})) \\ \forall x, y, z \in P (F u n d a m e n t a l T r i p l e (x, y, z) ⟺ (P y t h a g o r e a n T r i p l e (x, y, z) \land R e l a t i v e P r i m e s (x, y, z) \land (x, y, z > 0))) \\ R e l a t i v e P r i m e s (x, y, z) ⟺ (R e l a t i v e P r i m e s (x, y) \land R e l a t i v e P r i m e s (y, z) \land R e l a t i v e P r i m e s (x, z)) \\ (x, y, z > 0) ⟺ ((x > 0) \land (y > 0) \land (z > 0)) \end{aligned}$

Because of the symmetry in $x$ and $y$ , $(x, y, z)$ and $(y, x, z)$ are considered to be the same triple.

$\begin{aligned} (3, 4, 5) & fundamental \\ (5, 12, 13) & fundamental \\ (6, 8, 10) = 2 \times (3, 4, 5) & Pythagorean \end{aligned}$

[PROBLEM]

If we want to find all Pythagorean triples, it is sufficient to first find all fundamental triples and then take multiples of the fundamental triples.

Euclid’s Formula #

[THEOREM 1.3 - Euclid’s Formula]

Given any pair of relatively prime integers $(a, b)$ such that one of them is odd and the other even and $a > b > 0$ , then

$(a^{2} - b^{2}, 2 a b, a^{2} + b^{2})$

is a fundamental triple.

$\forall a, b \in P ((R e l a t i v e P r i m e s (a, b) \land E v e n O d d (a, b) \land (a > b > 0)) ⟹ F u n d a m e n t a l T r i p l e (a^{2} + b^{2}, 2 a b, a^{2} - b^{2}))$

$\begin{aligned} E v e n O d d (a, b) ⟺ ((E v e n (a) \land O d d (b)) \oplus (O d d (a) \land E v e n (b))) \\ (a > b > 0) ⟺ ((a > b) \land (b > 0)) \end{aligned}$

Furthermore, every fundamental triple is of this form.

$\forall x, y, z \in P (F u n d a m e n t a l T r i p l e (x, y, z) ⟹ \exists a, b \in P (R e l a t i v e P r i m e s (a, b) \land E v e n O d d (a, b) \land (a > b > 0) \land (x = a^{2} + b^{2}) \land (y = 2 a b) \land (z = a^{2} - b^{2})))$

Note that the first and third terms are odd and the second term is even.

\begin{array}{r} \begin{aligned} (E v e n (a) \land O d d (b)) & ⟹ (E v e n (a^{2}) \land O d d (b^{2}) \land E v e n (2 a b) \land O d d (a^{2} - b^{2}) \land O d d (a^{2} + b^{2})) \\ (O d d (a) \land E v e n (b)) & ⟹ (O d d (a^{2}) \land E v e n (b^{2}) \land E v e n (2 a b) \land O d d (a^{2} - b^{2}) \land O d d (a^{2} + b^{2})) \end{aligned} \end{array}

First few fundamental triples

$\begin{aligned} a = 2, b = 1 & (3, 4, 5) & (2^{2} - 1^{2}, 2 (2) (1), 2^{2} + 1^{2}) = (4 - 1, 2 \times 2, 4 + 1) \\ a = 3, b = 2 & (5, 12, 13) & (3^{2} - 2^{2}, 2 (3) (2), 3^{2} + 2^{2}) = (9 - 4, 2 \times 6, 9 + 4) \\ a = 4, b = 1 & (15, 8, 17) & (4^{2} - 1^{2}, 2 (4) (1), 4^{2} + 1^{2}) = (16 - 1, 2 \times 4, 16 + 1) \\ a = 4, b = 3 & (7, 24, 25) & (4^{2} - 3^{2}, 2 (4) (3), 4^{2} + 3^{2}) = (16 - 9, 2 \times 12, 16 + 9) \\ a = 5, b = 2 & (21, 20, 29) & (5^{2} - 2^{2}, 2 (5) (2), 5^{2} + 2^{2}) = (25 - 4, 2 \times 10, 25 + 4) \\ a = 5, b = 4 & (9, 40, 41) & (5^{2} - 4^{2}, 2 (5) (4), 5^{2} + 4^{2}) = (25 - 16, 2 \times 20, 25 + 16) \\ a = 6, b = 1 & (35, 12, 37) & (6^{2} - 1^{2}, 2 (6) (1), 6^{2} + 1^{2}) = (36 - 1, 2 \times 6, 36 + 1) \\ a = 6, b = 5 & (11, 60, 61) & (6^{2} - 5^{2}, 2 (6) (5), 6^{2} + 5^{2}) = (36 - 25, 2 \times 30, 36 + 25) \\ a = 7, b = 2 & (45, 28, 53) & (7^{2} - 2^{2}, 2 (7) (2), 7^{2} + 2^{2}) = (49 - 4, 2 \times 14, 49 + 4) \\ a = 7, b = 4 & (33, 56, 65) & (7^{2} - 4^{2}, 2 (7) (4), 7^{2} + 4^{2}) = (49 - 16, 2 \times 28, 49 + 16) \\ a = 7, b = 6 & (13, 84, 85) & (7^{2} - 6^{2}, 2 (7) (6), 7^{2} + 6^{2}) = (49 - 36, 2 \times 42, 49 + 36) \\ a = 8, b = 1 & (63, 16, 65) & (8^{2} - 1^{2}, 2 (8) (1), 8^{2} + 1^{2}) = (64 - 1, 2 \times 8, 64 + 1) \\ a = 8, b = 3 & (55, 48, 73) & (8^{2} - 3^{2}, 2 (8) (3), 8^{2} + 3^{2}) = (64 - 9, 2 \times 24, 64 + 9) \\ a = 8, b = 5 & (39, 80, 89) & (8^{2} - 5^{2}, 2 (8) (5), 8^{2} + 5^{2}) = (64 - 25, 2 \times 40, 64 + 25) \\ a = 8, b = 7 & (15, 112, 113) & (8^{2} - 7^{2}, 2 (8) (7), 8^{2} + 7^{2}) = (64 - 49, 2 \times 56, 64 + 49) \\ a = 9, b = 2 & (77, 36, 85) & (9^{2} - 2^{2}, 2 (9) (2), 9^{2} + 2^{2}) = (81 - 4, 2 \times 18, 81 + 4) \\ a = 9, b = 4 & (65, 72, 97) & (9^{2} - 4^{2}, 2 (9) (4), 9^{2} + 4^{2}) = (81 - 16, 2 \times 36, 81 + 16) \end{aligned}$

$P r o o f$

1

That $(a^{2} - b^{2}, 2 a b, a^{2} + b^{2})$ is a fundamental triple for any pair of relatively prime integers $(a, b)$ such that one of them is odd and the other even and $a > b > 0$ .

Let $a > b$ be two positive integers.

Then $a^{2} - b^{2}$ , $2 a b$ , and $a^{2} + b^{2}$ are positive integers and

$\begin{aligned} (a^{2} - b^{2})^{2} + (2 a b)^{2} & = (a^{2} + b^{2})^{2} \\ a^{4} - 2 a^{2} b^{2} + b^{4} + 4 a^{2} b^{2} & = a^{4} + 2 a^{2} b^{2} + b^{4} \end{aligned}$

$P r o o f b y c o n t r a d i c t i o n$

2

That a triple is fundamental iff it has the form $(a^{2} - b^{2}, 2 a b, a^{2} + b^{2})$ for a pair of relatively prime integers $(a, b)$ such that one of them is odd and the other even and $a > b > 0$ .

Let $(x, y, z)$ be a fundamental triple. Then it follows from the definition of a fundamental triple that since $x$ , $y$ , and $z$ are not all even, at most one of them is even.

Assume $x$ and $y$ are both odd. Then $x^{2}$ and $y^{2}$ are each one more than a multiple of $4$ and so $z^{2}$ must be two more than a multiple of $4$ .

$\begin{aligned} x & = 2 k + 1 \\ x^{2} & = (2 k + 1)^{2} \\ = 4 (k^{2} + k) + 1 \\ = 4 ℓ + 1 & for integer ℓ = k^{2} + k \end{aligned}$

$\begin{aligned} z^{2} & = x^{2} + y^{2} \\ = (4 ℓ + 1) + (4 m + 1) \\ = 4 n + 2 & for integer n = ℓ + m \\ = 2 (2 n + 1) \\ 2 & ∣ z^{2} \\ 2 ∣ z^{2} & \to 4 ∣ z^{2} & Euclid's lemma \\ 4 & ∣ z^{2} & modus ponens \\ z^{2} & \neq 4 n & contradiction \end{aligned}$

Therefore, either $x$ or $y$ is even. By symmetry in $x$ and $y$ we can assume it is $y = 2 m$ that is even.

$\begin{aligned} y^{2} & = z^{2} - x^{2} \\ = (z - x) \times (z + x) \\ m^{2} & = \frac{z - x}{2} \times \frac{z + x}{2} \end{aligned}$

Since $x$ and $z$ are each odd, both $\frac{x - z}{2}$ and $\frac{x + z}{2}$ are integers and they are relatively prime because any common divisor would have to divide both their sum and their difference, but $x$ and $z$ have no common divisors from the definition of a fundamental triple.

$\begin{aligned} \frac{z - x}{2} + \frac{z + x}{2} & = z \\ \frac{z - x}{2} - \frac{z + x}{2} & = x \end{aligned}$

$\begin{aligned} p ∣ \frac{z - x}{2} & \to p ∣ m^{2} \\ p ∣ m^{2} & \to p^{2} ∣ m^{2} & Euclid's lemma \end{aligned}$

Since $p ∤ \frac{z + x}{2}$ it must be the case that $p^{2} ∣ \frac{z - x}{2}$ .

Thus the factorization will only have even exponents which is another way of saying that $\frac{z - x}{2}$ is a perfect square. Similarly, $\frac{z + x}{2}$ is a perfect square.

$\begin{aligned} \frac{z + x}{2} & = a^{2} \\ \frac{z - x}{2} & = b^{2} \end{aligned}$

$a$ and $b$ are relatively prime.

Since $a^{2} + b^{2} = z$ is odd, one of $a$ or $b$ is odd and the other is even.

$\begin{aligned} x & = a^{2} - b^{2} \\ y & = \sqrt{z^{2} - x^{2}} \\ = \sqrt{(a^{4} + 2 a^{2} b^{2} + b^{4}) - (a^{4} - 2 a^{2} b^{2} + b^{4})} \\ = 2 a b \\ z & = a^{2} + b^{2} \end{aligned}$

$◼$

The Fundamental Theorem of Arithmetic #

or the Unique Factorization Theorem for Integers

$T h e o r e m$ [Bressoud 1.4 pp. 5]

Factorization into primes is unique up to order.

$E x a m p l e$ [Bressoud]

There may be several ways of ordering the primes that go into a factorization, but we cannot change the primes that go into the factorization.

$\begin{aligned} 30 & = 2 \times 3 \times 5 \\ = 3 \times 5 \times 2 \\ = 5 \times 2 \times 3 \end{aligned}$

This does not hold for the extended integers (of the form $m + n \sqrt{10}$ ).

$\begin{aligned} 6 & = 2 \times 3 \\ = (4 + \sqrt{10}) \times (4 - \sqrt{10}) \end{aligned}$

$P r o o f$ [Bressoud]

Sketch of the proof. It will be proved that every integer with non-unique factorization has a proper divisor with non-unique factorization. If there were integers with non-unique factorization, then there would eventually be a prime with non-unique factorization. This contradicts the definition of a prime, that a prime has no divisors other than itself and unity.

Let $n$ be an integer with non-unique (but distinct) factorization $n = p_{1} \times p_{2} \times \dots \times p_{r} = q_{1} \times q_{2} \times \dots \times q_{r}$ where the primes are not necessarily distinct, but where the second factorization is not simply a reordering of the first.
The prime $q_{1}$ divides $n$ and so it divides the product of the $p_{i}$ s.

$\begin{aligned} q_{1} & ∣ n \\ q_{1} & ∣ (p_{1} \times p_{2} \times \dots \times p_{r}) \\ q_{1} & ∣ p_{i} & p_{i} \in {p_{1}, p_{2}, \dots, p_{r}} by repeated application of Euclid's lemma \\ q_{1} & ∣ p_{1} & by reordering of the p_{i} s \\ q_{1} & = p_{1} & since P r i m e (p_{1}) \end{aligned}$

$\begin{aligned} \frac{n}{q_{1}} & = p_{2} \times p_{3} \times \dots \times p_{r} \\ = q_{2} \times q_{3} \times \dots \times q_{s} \end{aligned}$

Since the factorizations of $n$ are distinct, the factorizations of $\frac{n}{q_{1}}$ are distinct.

Therefore $\frac{n}{q_{1}}$ is a proper divisor of $n$ with non-unique factorization.

$◼$

The following theorem says that, in some sense, the primes are the multiplicative building blocks from which every (positive) integer may be produced in a unique way. Therefore positive integers, other than $1$ , which are not prime are referred to as composite.

$T h e o r e m$ [Humphreys & Prest pp. 28] Euclid’s Elements Book VII Proposition 31.

Every positive integer $n$ greater than or equal to $2$ may be written in the form $n = p_{1} p_{2} \dots p_{r}$ where the integers $n = p_{1}, p_{2}, \dots, p_{r}$ are prime numbers (which need not be distinct) and $r \geq 1$ . This factorization is unique in the sense that if also $n = q_{1} q_{2} \dots q_{s}$ where $q_{1}, q_{2}, \dots, q_{s}$ are primes, then $r = s$ and we can renumber the $q_{i}$ so that $q_{i} = p_{i}$ for $i = 1, 2, \dots, r$ . In other words, up to rearrangement, there is just one way of writing a positive integer as a product of primes.

The idea of the following proof is as follows. If $n$ is not prime then factor it as $a b$ . If $a$ is not prime then factor it and if $b$ is not prime then factor it. Continue splitting any factors which are not prime. This cannot go on forever because the integers we produce are decreasing and each factorization gives strictly smaller numbers: the process eventually stops with a product of primes.

$P r o o f o f t h e e x i s t e n c e o f t h e d e c o m p o s i t i o n$ [Humphreys & Prest pp. 28-29]

Show by strong induction that every positive integer greater than or equal to $2$ has a factorization as a product of primes.

Base Case

$n = 2$ is prime.

For $n > 2$ either $n$ is prime in which case $n$ has a factorization (with just one factor) of the required form or $n$ can be written as a product $a b$ where $1 < a < n$ and $1 < b < n$ .

Induction Step

Induction Hypothesis: Let $a$ and $b$ both have factorizations into primes.
We obtain a factorization of $n$ as a product of primes by juxtaposing the factorizations of $a$ and $b$ .

Therefore every positive integer greater than or equal to $2$ has a factorization as a product of primes.

$◼$

$E x a m p l e s$ [Humphreys & Prest pp. 29-30]

\begin{array}{r} \begin{aligned} 4 & = 2^{2} \\ 6 & = 2^{1} \times 3^{1} \\ 8 & = 2^{3} \\ = (2) \times (2 \times 2) = 2 \times 4 \\ 9 & = 2^{0} \times 3^{2} \\ 10 & = 2^{1} \times 3^{0} \times 5^{1} \\ 12 & = 2^{2} \times 3^{1} \\ = (2) \times (2 \times 3) = 2 \times 6 \\ = (2 \times 2) \times (3) = 4 \times 3 \\ 14 & = 2^{1} \times 3^{0} \times 5^{0} \times 7^{1} \\ 15 & = 2^{0} \times 3^{1} \times 5^{1} \\ 16 & = 2^{4} \\ = (2) \times (2 \times 2 \times 2) = 2 \times 8 \\ = (2 \times 2) \times (2 \times 2) = 4 \times 4 \\ 18 & = 2^{1} \times 3^{2} \\ = (2) \times (3 \times 3) = 2 \times 9 \\ = (2 \times 3) \times (3) = 6 \times 3 \\ 20 & = 2^{2} \times 3^{0} \times 5^{1} \\ = (2) \times (2 \times 5) = 2 \times 10 \\ = (2 \times 2) \times (5) = 4 \times 5 \\ 21 & = 2^{0} \times 3^{1} \times 5^{0} \times 7^{1} \\ 22 & = 2^{1} \times 3^{0} \times 5^{0} \times 7^{0} \times 11^{1} \\ 24 & = 2^{3} \times 3^{1} \\ = (2) \times (2 \times 2 \times 3) = 2 \times 12 \\ = (2 \times 2) \times (2 \times 3) = 4 \times 6 \\ = (2 \times 2 \times 2) \times (3) = 8 \times 3 \\ 25 & = 2^{0} \times 3^{0} \times 5^{2} \\ 26 & = 2^{1} \times 3^{0} \times 5^{0} \times 7^{0} \times 11^{0} \times 13^{1} \\ 28 & = 2^{2} \times 3^{0} \times 5^{0} \times 7^{1} \\ = (2) \times (2 \times 7) = 2 \times 14 \\ = (2 \times 2) \times (7) = 4 \times 7 \\ 30 & = 2^{1} \times 3^{1} \times 5^{1} \\ = (2) \times (3 \times 5) = 2 \times 15 \\ = (2 \times 3) \times (5) = 6 \times 5 \\ ⋮ \\ 72 & = 2^{3} \times 3^{2} \\ = (2) \times (2 \times 2 \times 3 \times 3) = 2 \times 36 \\ = (2 \times 2) \times (2 \times 3 \times 3) = 4 \times 18 \\ = (2 \times 2 \times 2) \times (3 \times 3) = 8 \times 9 \\ = (2 \times 2 \times 2 \times 3) \times (3) = 24 \times 3 \\ ⋮ \\ 588 & = 2^{2} \times 3^{1} \times 5^{0} \times 7^{2} \\ = (2) \times (2 \times 3 \times 7 \times 7) = 2 \times 294 \\ = (3) \times (2 \times 2 \times 7 \times 7) = 3 \times 196 \\ = (7) \times (2 \times 2 \times 3 \times 7) = 7 \times 84 \\ = (2 \times 2) \times (3 \times 7 \times 7) = 4 \times 147 \\ = (2 \times 3) \times (2 \times 7 \times 7) = 6 \times 98 \\ = (2 \times 7) \times (2 \times 3 \times 7) = 14 \times 42 \\ = (2 \times 2 \times 3) \times (7 \times 7) = 12 \times 49 \\ = (2 \times 2 \times 7) \times (3 \times 7) = 28 \times 21 \end{aligned} \end{array}

This proof is based on the observation that if a prime divides one side of the equation then it divides the other, so we can cancel it from each side. This process eventually stops with the equation $1 = 1$ . Therefore there must have been the same number of primes, and indeed the same primes, on each side of the original equation.

$P r o o f o f u n i q u e n e s s$ [Humphreys & Prest pp. 28-29]

Use the standard form of mathematical induction on the number $r$ of prime factors to show that any positive integer which has a factorization into a product of $r$ primes has a unique factorization up to rearrangement.

Base Case

Let $n = q_{1} q_{2} \dots q_{s}$ be a prime.
If we had $s \geq 2$ then $n$ would have distinct divisors $1, q_{1}, q_{1} q_{2}$ contradicting that it is prime.
Therefore $s = 1$ .

Induction Step

Induction Hypothesis: Any positive integer greater than $2$ which has a factorization into $r - 1$ primes has a unique factorization.
Let $n = p_{1} p_{2} \dots p_{r} = q_{1} q_{2} \dots q_{s}$ be two prime factorizations of $n$ .
$p_{1}$ divides $n$ implies that $p_{1}$ divides one of $q_{1}, q_{2}, \dots, q_{s}$ .
We can renumber the $q_{i}$ so that it is $q_{1}$ that $p_{1}$ divides.
It must be the case that $p_{1} = q_{1}$ since both $p_{1}$ and $q_{1}$ are prime.
Therefore $p_{2} p_{3} \dots p_{r} = q_{2} q_{3} \dots q_{s}$ .
The integer $p_{2} p_{3} \dots p_{r}$ is a product of $r - 1$ primes.
Therefore $r - 1 = s - 1 ⟺ r = s$ and after renumbering $p_{i} = q_{i}$ for $i = 2, \dots, r$ .
Since we already have $p_{1} = q_{1}$ we have $p_{i} = q_{i}$ for $i = 1, 2, \dots, r$ .

Therefore any positive integer has a unique factorization up to rearrangement.

$◼$

GCD and LCM as prime factorizations #

$C o r o l l a r y$ [Humphreys & Prest 1.3.5 pp. 30-31]

Let $a$ and $b$ be positive integers.
Let $a = p_{1}^{n_{1}} p_{2}^{n_{2}} \dots p_{r}^{n_{r}}$ and $b = p_{1}^{m_{1}} p_{2}^{m_{2}} \dots p_{r}^{m_{r}}$ be the prime factorizations of $a$ and $b$ where $p_{1}, p_{2}, \dots, p_{r}$ are distinct primes and $n_{1}, n_{2}, \dots, n_{r}, m_{1}, m_{2}, \dots, m_{r}$ are non-negative integers (some perhaps zero in order to allow a common list of primes to be used).
Then the greatest common divisor $d$ of $a$ and $b$ is given by $d = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}$ where for each $i$ , $k_{i}$ is the smaller of $n_{i}$ and $m_{i}$ , and the least common multiple $f$ of $a$ and $b$ is given by $f = p_{1}^{t_{1}} p_{2}^{t_{2}} \dots p_{r}^{t_{r}}$ where for each $i$ , $t_{i}$ is the larger of $n_{i}$ and $m_{i}$ .

$P r o o f$ [Humphreys & Prest pp. 31]

$◼$

$E x a m p l e s$ [Humphreys & Prest pp. 31-32]

$2$ and $3$

\begin{array}{r} \begin{aligned} a & = 2 & = 2^{1} \times 3^{0} \\ b & = 3 & = 2^{0} \times 3^{1} \\ g c d (a, b) & = 1 & = 2^{0} \times 3^{0} \\ l c m (a, b) & = 6 & = 2^{1} \times 3^{1} \end{aligned} \end{array}

$2$ and $4$

\begin{array}{r} \begin{aligned} a & = 2 & = 2^{1} \\ b & = 4 & = 2^{2} \\ g c d (a, b) & = 2 & = 2^{1} \\ l c m (a, b) & = 4 & = 2^{2} \end{aligned} \end{array}

$56$ and $84$

\begin{array}{r} \begin{aligned} a & = 56 & = 2^{3} \times 3^{0} \times 7^{1} \\ b & = 84 & = 2^{2} \times 3^{1} \times 7^{1} \\ g c d (a, b) & = 28 & = 2^{2} \times 3^{0} \times 7^{1} \\ l c m (a, b) & = 168 & = 2^{3} \times 3^{1} \times 7^{1} \end{aligned} \end{array}

$135$ and $639$

\begin{array}{r} \begin{aligned} a & = 135 & = 3^{3} \times 5^{1} \times 71^{0} \\ b & = 639 & = 3^{2} \times 5^{0} \times 71^{1} \\ g c d (a, b) & = 9 & = 3^{2} \times 5^{0} \times 71^{0} \\ l c m (a, b) & = 9585 & = 3^{3} \times 5^{1} \times 71^{1} \end{aligned} \end{array}

Fermat Primes #

$C l a i m$

If $2^{n} + 1$ is prime where $n \geq 1$ then $n$ must be of the form $2^{k}$ for some positive integer $k$ .

\begin{array}{r} \begin{aligned} F (k) & = 2^{2^{k}} + 1 \\ F (0) & = 2^{2^{0}} + 1 = 3 & prime \\ F (1) & = 2^{2^{1}} + 1 = 5 & prime \\ F (2) & = 2^{2^{2}} + 1 = 17 & prime \\ F (3) & = 2^{2^{3}} + 1 = 257 & prime \\ F (4) & = 2^{2^{4}} + 1 = 65, 537 & prime \\ F (5) & = 2^{2^{5}} + 1 = 4, 294, 967, 297 & composite \\ F (6) & = 2^{2^{6}} + 1 = 18, 446, 744, 073, 709, 551, 617 & composite \\ ⋮ \end{aligned} \end{array}

Mersenne Primes #

$C l a i m$

If $2^{n} - 1$ is prime then $n$ is prime.

\begin{array}{r} \begin{aligned} M (n) & = 2^{n} - 1 \\ M (2) & = 2^{2} - 1 = 3 & prime \\ M (3) & = 2^{3} - 1 = 7 & prime \\ M (5) & = 2^{5} - 1 = 31 & prime \\ M (7) & = 2^{7} - 1 = 127 & prime \\ M (11) & = 2^{11} - 1 = 2, 047 = 23 \times 89 & composite \\ M (13) & = 2^{13} - 1 = 8, 191 & prime \\ M (17) & = 2^{17} - 1 = 131, 071 & prime \\ M (19) & = 2^{19} - 1 = 524, 287 & prime \\ M (23) & = 2^{23} - 1 = 8, 388, 607 = 47 \times 178, 481 & composite \\ M (29) & = 2^{29} - 1 = 536, 870, 911 = 233 \times 1, 103 \times 2, 089 & composite \\ M (31) & = 2^{31} - 1 = 2, 147, 483, 647 & prime \\ M (37) & = 2^{37} - 1 = 137, 438, 953, 471 = ? \times ? & composite \\ M (41) & = \\ M (43) & = \\ M (47) & = \\ M (53) & = \\ M (59) & = \\ M (61) & = \\ M (71) & = \\ M (73) & = \\ M (79) & = \\ M (83) & = \\ M (89) & = \\ M (97) & = \\ ⋮ \\ M (13, 466, 917) & = 2^{13, 466, 917} - 1 = 4,000,000-digit integer (2001) \\ ⋮ \\ M (82, 589, 933) & = 2^{82, 589, 933} - 1 = 24,862,048-digit integer (2018) \end{aligned} \end{array}

Goldbach’s Conjecture #

$C o n j e c t u r e$

Every even number greater than two can be expressed as the sum of two primes.

\forall n \in P [(E v e n (n) \land (n > 2)) ⟹ \exists p, q \in P [P r i m e (p) \land P r i m e (q) \land (n = p + q)]]

$E x a m p l e s$

$4 = 2 + 2$ is the only even integer greater than $2$ which is the sum of the prime $2$ and another prime (in this case, $2$ too).

\begin{array}{r} \begin{array}{ccccccccccc} 6 = & 3 \\ 8 = & 3 & 5 \\ 10 = & 5 \\ 12 = & 5 & 7 \\ 14 = & 7 \\ 16 = & 3 & 13 \\ 5 & 11 \\ 18 = & 5 & 13 \\ 7 & 11 \\ 20 = & 3 & 17 \\ 7 & 13 \\ 22 = & 3 & 19 \\ 5 & 17 \\ 11 \\ 24 = & 5 & 19 \\ 7 & 17 \\ 11 & 13 \\ 26 = & 3 & 23 \\ 7 & 19 \\ 13 \\ 28 = & 5 & 23 \\ 11 & 17 \\ 30 = & 7 & 23 \\ 11 & 19 \\ 13 & 17 \end{array} \end{array}

Twin Primes Conjecture #

There are infinitely many pairs $(x, y)$ s.t. $x$ and $y$ are both prime and $y = x + 2$ .

\begin{array}{r} \begin{aligned} \forall x, y \in P (T w i n P r i m e s (x, y) ⟺ (P r i m e (x) \land P r i m e (y) \land (y = x + 2))) \\ \forall x, y \in P (T w i n P r i m e s (x, y) ⟹ \exists a, b \in P ((a > x) \land T w i n P r i m e s (a, b))) \end{aligned} \end{array}

Bounded Gap Theorem #

There are infinitely many pairs of primes that differ by at most $70, 000, 000$ .

\begin{array}{r} \begin{aligned} \forall x, y \in P (B o u n d e d G a p P r i m e s (x, y) ⟺ (P r i m e (x) \land P r i m e (y) \land (a b s (y - x) \leq 70, 000, 000))) \\ \forall x, y \in P (B o u n d e d G a p P r i m e s (x, y) ⟹ \exists a, b \in P ((a > x) \land B o u n d e d G a p P r i m e s (a, b))) \end{aligned} \end{array}

Primality

Contents

Primality #

Table of Contents #

Programming Environment #

Euclid’s Lemma #

Prime Factorization #

Relative Primality #

Pythagorean Triples #

Euclid’s Formula #

The Fundamental Theorem of Arithmetic #

GCD and LCM as prime factorizations #

Fermat Primes #

Mersenne Primes #

Goldbach’s Conjecture #

Twin Primes Conjecture #

Bounded Gap Theorem #