Primality#
Table of Contents#
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'
Primes and Composites#
Definition of prime#
\(Definition\) [Humphreys & Prest pp. 25]
A positive integer \(p\) is prime if \(p\) has exactly two positive divisors, namely \(1\) and \(p\).
Note that \(1\) is not prime according to this definition since \(1\) has exactly one positive divisor, namely \(1\).
Note that therefore the smallest prime is \(2\) and that this is the only even prime since any other even prime \(n\) has at least three distinct divisors, namely \(1\), \(2\), and \(n\).
\(Definition\) [Bressoud]
An integer greater than \(1\) that cannot be written as the product of two integers greater than \(1\).
Composite#
\(Definition\)
An integer greater than \(1\) which can be written as the product of two integers greater than \(1\).
Sieve of Eratosthenes#
[Humphreys & Prest pp. 26]
To find the primes less than some number \(n\), prepare an array of the integers from \(2\) to \(n\). Save \(2\) and then delete all multiples of \(2\). Now look for the next undeleted integer (which will be \(3\)), save it and delete all its multiples. The smallest undeleted number will be the next prime, \(5\). Continue in this way to find all the primes up to \(n\). In fact, it will turn out that you can stop this process once you have reached the greatest integer which is less than or equal to the square root of \(n\), in the sense that any integers left undeleted at this stage will be prime.
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#
\(Theorem\) [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.
Note that the following cases hold as a consequence.
If a prime \(p\) divides \(a^2\), then it must divide \(a\).
Therefore, if \(p\) divides \(a^2\), then \(p^2\) divides \(a^2\).
The following theorem is a property which is characteristic of primes and is sometimes used to define them.
\(Theorem\) [Humphreys & Prest 1.3.1 pp. 26]
Let \(p\) be a prime and let \(a\) and \(b\) be integers s.t. \(p\) divides \(ab\).
\(p\) divides either \(a\) or \(b\).
\(Proof\) [Humphreys & Prest pp. 26]
The only positive divisors of \(p\) are \(1\) and \(p\) since \(p\) is prime.
Then either \(gcd(p, a) = p\) or \(gcd(p, a) = 1\).If \(gcd(p, a) = p\) then \(p \mid a\).
[Humphreys & Prest 1.1.6]
If \(gcd(p, a) = 1\) then \(p\) and \(a\) are relatively prime.
Then there are integers \(r\) and \(s\) s.t. \(1 = pr + as \iff b = pbr + abs = p(br) + ab(s)\).
Since \(p\) divides \(p(br)\) and \(p\) divides \(ab(s)\), \(p\) divides their sum \(b\).\(\therefore\) if a prime divides a product then it divides one or the other factor.
\(\blacksquare\)
The following lemma is an extension of the previous theorem.
\(Lemma\) [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\).
\(Proof \,\, by \,\, induction \,\, on \,\, the \,\, number \,\, r \,\, of \,\, factors \,\, a_i\) [Humphreys & Prest pp. 27]
Base Case
If \(p \mid a_1\) then \(p \mid a_1\).
Induction Step
Induction Hypothesis: Let \(p \mid 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 \le 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\).
\(\blacksquare\)
Prime Factorization#
\(Definition\) [Bressoud]
The decomposition of a positive integer into primes is called its factorization, which is expressed by
where \(p_1, p_2, \dots, p_r\) are distinct primes.
Relative Primality#
or coprimality
\(Definition\) [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.
\(Example\) [Bressoud pp. 3]
\(45 = 3 \times 3 \times 5\) and \(98 = 2 \times 7 \times 7\) are relatively prime.
\(Definition\) [Humphreys & Prest pp. 12]
Let \(a\) and \(b\) be positive integers.
If \(gcd(a, b) = 1\) then \(a\) and \(b\) are said to be relatively prime.
\(Theorem\) [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 \(bc\) then \(a\) divides \(c\)
if \(a\) divides \(c\) and \(b\) divides \(c\) then \(ab\) divides \(c\)
\(Proof\) [Humphreys & Prest 1.1.6 pp. 13]
Since \(a\) and \(b\) are relatively prime there are integers \(s\) and \(t\) st \(1 = as + bt\) by Bézout’s identity.
\(1 = as + bt \iff c = cas + cbt = a(cs) + bc(t)\).Let \(a \mid bc\).
Since \(a \mid a\) and \(a \mid bc\) it is the case that \(a \mid a(cs) + bc(t) = c\).
\(\therefore a \mid c\).Let \(a \mid c\)
Then there is an integer \(m\) such that \(am = c\).
Let \(b \mid c\)
Then there is an integer \(n\) such that \(bn = c\).
\(c = cas + cbt = (bn)as + (am)bt = ab(ns) + ab(mt) = ab(ns + mt) \implies ab \mid c\).
\(\therefore ab \mid c\).Alternatively
Let \(a \mid c\).
\(a \mid c \implies ab \mid cb \implies ab \mid cbt\).
Let \(b \mid c\).
\(b \mid c \implies ab \mid ac \implies ab \mid cas\).
\(\therefore ab \mid cas + cbt = c\).
\(\blacksquare\)
\(Claim\)
\(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} \)
\(gcd(m, n) = 1\) implies that \(b_i = 0\) whenever \(a_i \gt 0\) and vice versa.
\( \begin{aligned} m^2 &= p_1^{2a_1} \times p_2^{2a_2} \times \dots \times p_r^{2a_r} \\ n^2 &= p_1^{2b_1} \times p_2^{2b_2} \times \dots \times p_r^{2b_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.
\( \color{red}\boxed{ \begin{aligned} & \forall x, y, z \in \mathbb{P} \,\, (PythagoreanTriple(x, y, z) \iff (x^2 + y^2 = z^2)) \\ & \forall x, y, z \in \mathbb{P} \,\, (FundamentalTriple(x, y, z) \iff (PythagoreanTriple(x, y, z) \land RelativePrimes(x, y, z) \land (x, y, z \gt 0))) \\ & RelativePrimes(x, y, z) \iff (RelativePrimes(x, y) \land RelativePrimes(y, z) \land RelativePrimes(x, z)) \\ & (x, y, z \gt 0) \iff ((x \gt 0) \land (y \gt 0) \land (z \gt 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) && \text{fundamental} \\ & (5, 12, 13) && \text{fundamental} \\ & (6, 8, 10) = 2 \times (3, 4, 5) && \text{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 \gt b \gt 0\), then
\((a^2 - b^2, 2ab, a^2 + b^2)\)
is a fundamental triple.
\( \color{red}\boxed{ \forall a, b \in \mathbb{P} \,\, ((RelativePrimes(a, b) \land EvenOdd(a, b) \land (a \gt b \gt 0)) \implies FundamentalTriple(a^2 + b^2, 2ab, a^2 - b^2)) } \)
\( \boxed{ \begin{aligned} & EvenOdd(a, b) \iff ((Even(a) \land Odd(b)) \oplus (Odd(a) \land Even(b))) \\ & (a \gt b \gt 0) \iff ((a \gt b) \land (b \gt 0)) \\ \end{aligned} } \)
Furthermore, every fundamental triple is of this form.
\( \color{red}\boxed{ \forall x, y, z \in \mathbb{P} \,\, (FundamentalTriple(x, y, z) \implies \exists a, b \in \mathbb{P} \,\, (RelativePrimes(a, b) \land EvenOdd(a, b) \land (a \gt b \gt 0) \land (x = a^2 + b^2) \land (y = 2ab) \land (z = a^2 - b^2))) } \)
Note that the first and third terms are odd and the second term is even.
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} \)
\(Proof\)
1
That \((a^2 - b^2, 2ab, 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 \gt b \gt 0\).
Let \(a \gt b\) be two positive integers.
Then \(a^2 - b^2\), \(2ab\), and \(a^2 + b^2\) are positive integers and
\( \begin{aligned} (a^2 - b^2)^2 + (2ab)^2 &= (a^2 + b^2)^2 \\ a^4 - 2a^2b^2 + b^4 + 4a^2b^2 &= a^4 + 2a^2b^2 + b^4 \\ \end{aligned} \)
\(Proof \,\, by \,\, contradiction\)
2
That a triple is fundamental iff it has the form \((a^2 - b^2, 2ab, 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 \gt b \gt 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 &= 2k + 1 \\ x^2 &= (2k + 1)^2 \\ &= 4(k^2 + k) + 1 \\ &= 4\ell + 1 && \text{for integer} \, \ell = k^2 + k \\ \end{aligned} \)
\( \begin{aligned} z^2 &= x^2 + y^2 \\ &= (4\ell + 1) + (4\mathcal{m} + 1) \\ &= 4\mathcal{n} + 2 && \text{for integer} \, \mathcal{n} = \ell + \mathcal{m} \\ &= 2(2\mathcal{n} + 1) \\ 2 &\mid z^2 \\ 2 \mid z^2 &\rightarrow 4 \mid z^2 && \text{Euclid's lemma} \\ 4 &\mid z^2 && \text{modus ponens} \\ z^2 &\ne 4n && \text{contradiction} \\ \end{aligned} \)
Therefore, either \(x\) or \(y\) is even. By symmetry in \(x\) and \(y\) we can assume it is \(y = 2m\) 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 \mid \frac{z - x}{2} &\rightarrow p \mid m^2 \\ p \mid m^2 &\rightarrow p^2 \mid m^2 && \text{Euclid's lemma} \\ \end{aligned} \)
Since \(p \nmid \frac{z + x}{2}\) it must be the case that \(p^2 \mid \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 + 2a^2b^2 + b^4) - (a^4 - 2a^2b^2 + b^4)} \\ &= 2ab \\ z &= a^2 + b^2 \\ \end{aligned} \)
\(\blacksquare\)
The Fundamental Theorem of Arithmetic#
or the Unique Factorization Theorem for Integers
\(Theorem\) [Bressoud 1.4 pp. 5]
Factorization into primes is unique up to order.
\(Example\) [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} \)
\(Proof\) [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 &\mid n \\ q_1 &\mid (p_1 \times p_2 \times \dots \times p_r) \\ q_1 &\mid p_i && p_i \in \{ p_1, p_2, \dots, p_r \} \, \text{by repeated application of Euclid's lemma} \\ q_1 &\mid p_1 && \text{by reordering of the} \, p_i \, \text{s} \\ q_1 &= p_1 && \text{since} \, Prime(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.
\(\blacksquare\)
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.
\(Theorem\) [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 \ge 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 \(ab\). 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.
\(Proof \,\, of \,\, the \,\, existence \,\, of \,\, the \,\, decomposition\) [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 \gt 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 \(ab\) where \(1 \lt a \lt n\) and \(1 \lt b \lt 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.
\(\blacksquare\)