Division#
Summary#
Integer Division#
This is effectively equivalent to the requirement that \(b/a\) be an integer in which case \(a \ne 0\). This requirement is sometimes relaxed to allow for the possibility that \(0 \mid 0\). However, the number \(0/0\) remains undefined. More on this later.
We say that \(a\) is a divisor or factor of \(b\) and that \(b\) is a multiple of \(a\).
\( \underset{\text{divisor}}{\quad a \quad} \mid \underset{\text{multiple}}{\quad b \quad} \quad \quad \underset{\text{factors}}{\quad ac \quad} = \underset{\text{multiple}}{\quad b \quad} \)
\(\pm 1, \pm n\) are called the trivial divisors of \(n\). Otherwise a divisor \(d\) with \(1 \lt |d| \lt n\) is non-trivial or proper.
Although divisors may be negative, we usually only speak of positive divisors.
Claim (zero division): zero divides no non-zero integer#
How about \(0 \mid 0\)? See the next claim.
Claim: every integer “integer-divides” \(0\)#
https://math.stackexchange.com/questions/539174/is-zero-a-prime-number
https://math.stackexchange.com/questions/2174535/does-zero-divide-zero
The integer \(0\) modulo \(a\) is trivially congruent to \(0\).
\( a \mid 0 \iff a \times k = 0 - 0 \iff 0 \equiv 0 \mod a \)
Claim: every integer divides itself#
An integer \(a\) modulo \(a\) is always congruent to \(0\).
\( a \mid a \iff a \times k = a - 0 \iff a \equiv 0 \mod a \)
Claim: \(\pm 1\) divide every integer#
An integer \(a\) modulo \(1\) is always congruent to \(0\).
\( 1 \mid a \iff 1 \times k = a - 0 \iff a \equiv 0 \mod 1 \)
Claim: the product of two integers is one iff both are one or negative one#
Claim: two integers divide each other iff they are equal up to sign#
Claim: \(a \mid b \implies |a| \le |b|\)#
Claim: \(ac = bc \iff a = b\)#
Claim: \(ac \mid bc \iff a \mid b\)#
Claim: \((a \mid b) \land (b \mid c) \implies a \mid c\)#
Generalization to \(k \ge 2\) integers.
\( \begin{aligned} \forall a_i \in \mathbb{Z} \quad \bigwedge_{i=2}^k a_{i-1} \mid a_i \quad \implies \quad a_1 \mid a_k \end {aligned} \)
Claim: \(a \mid b \implies a \mid bc\)#
The converse statement does not hold. In other words, if \(a \mid bc\) then it may be the case that neither does \(a \mid b\) nor does \(a \mid c\). For example, if \(a = 4\), \(b = 6\), and \(c = 10\) then
\(4 \mid 6 \times 10 \iff 4 \times 15 = 6 \times 10\) but \(4 \nmid 6\) and \(4 \nmid 10\).
Claim
\(a \mid b \implies a \mid b^n\) for any \(n \ge 1\)
Proof
Suppose \(a \mid b\). Then
\(a \mid b \iff ak = b \iff (ak)^n = b^n \iff a(a^{n-1}k^n) = b^n \iff a \mid b^n\)
\(\blacksquare\)
The converse statement does not hold in general. For example
\(4 \mid 2^2\) but \(4 \nmid 2\)
Claim: \((a \mid b) \land (a \mid c) \implies a \mid (bx + cy)\)#
Generalization to \(k \ge 2\) integers.
\( \begin{aligned} \forall a, b_i, x_i \quad \bigwedge_{i=1}^k a \mid b_i \quad \implies \quad a \Bigm\vert \sum_{i=1}^k b_i x_i \end {aligned} \)
Even#
Odd#
Claim: an integer is even (odd) iff one more and one less than it is odd (even)#
Claim: the sum or difference of two even integers is even#
The converse statement is not encessarily true. For example
\(2 \mid (1 + 3)\) but \(2 \nmid 1\) and \(2 \nmid 3\)
Claim: the sum or difference of two odd integers is even#
The converse statement is not encessarily true. For example
\(2 \mid (4 + 6)\) but \(2 \nmid (4 \pm 1)\) and \(2 \nmid (6 \pm 1)\)
Claim: the sum or difference of an even integer and an odd integer is odd#
Claim
\(2k \pm (2k' \pm 1)\) for any integers \(k\) and \(k'\) is odd. In other words, \(2k\) plus or minus any odd integer is an odd integer.
\( \begin{aligned} 2p + (2r + 1) &= 2p + 2r + 1 & = 2(p + r) + 1 \\ 2p - (2r + 1) &= 2(q + 1) - 2r - 1 &= 2q + 2 - 2r - 1 = 2(q - r) + 1 \\ 2p + (2r - 1) &= 2(q + 1) + 2r - 1 &= 2q + 2 + 2r - 1 = 2(q + r) + 1 \\ 2p - (2r - 1) &= 2p - 2r + 1 & = 2(p - r) + 1 \\ \end {aligned} \)
\( \begin{aligned} 2k + 1 & \\ 2k - 1 &= 2(k' + 1) - 1 = 2k' + 2 - 1 = 2k' + 1 \\ 2k + 3 &= 2(k' - 1) + 3 = 2k' - 2 + 3 = 2k' + 1 \\ 2k - 3 &= 2(k' + 2) - 3 = 2k' + 4 - 3 = 2k' + 1 \\ 2k + 5 &= 2(k' - 2) + 5 = 2k' - 4 + 5 = 2k' + 1 \\ 2k - 5 &= 2(k' + 3) - 5 = 2k' + 6 - 5 = 2k' + 1 \\ \vdots \end {aligned} \)
Claim: the product of an even integer and any integer is even#
Claim: the product of two odd integers is odd#
Claim: an integer and its square (\(n\)-th power) have the same parity#
This result generalizes to any \(n\)-th power with \(n \ge 1\).
\( \boxed{ \begin{aligned} \forall a \in \mathbb{Z} \quad \forall n \ge 1 \quad \text{Even}(a) \quad & \iff \quad \text{Even}(a^n) \\ \lnot\text{Even}(a) \quad & \iff \quad \lnot\text{Even}(a^n) \\ \text{Odd}(a) \quad & \iff \quad \text{Odd}(a^n) \\ \end {aligned} } \)
Claim: \(n\) is odd iff \(8 \mid (n^2 - 1)\)#
Claim: every odd integer has the form \(4k \pm 1\)#
Claim: if \(m\) and \(n\) are integers of the form \(4k + 1\) then so is \(mn\)#
The converse of this statement is not true in general. For example
\(3 \times 3 = 9 = 4 \times 2 + 1\) but \(3 \ne 4 k + 1\) for any integer \(k\).
Claim: if \(mn\) is of the form \(4k - 1\) then so is one of \(m\) or \(n\)#
Claim: if \(m\) and \(n\) are integers of the form \(6k + 1\) then so is \(mn\)#
The converse of this statement is not true in general. For example
\(5 \times 5 = 25 = 6 \times 4 + 1\) but \(5 \ne 6k + 1\) for any integer \(k\).
Claim: if \(mn\) is of the form \(6k - 1\) then so is one of \(m\) or \(n\)#
Claim: if \(m\) and \(n\) are integers of the form \(8k + 1\) then so is \(mn\)#
The converse of this statement is not true in general. For example
\(7 \times 7 = 49 = 8 \times 6 + 1\) but \(7 \ne 8k + 1\) for any integer \(k\).
False Claim: if \(mn\) is of the form \(8k - 1\) then so is one of \(m\) or \(n\)#
For example
\(8.5 - 1 = 39 = 3 \times 13 = (8.0 + 3) \times (8.2 - 3)\)
Claim: \(n \mid (n - 1)!\) for \(n \gt 4\)#
Primality#
Prime#
\(1\) is not a prime because it has exactly one (positive) divisor, and a prime number has exactly two (positive) divisors. Thus the smallest prime is \(2\) which is the only even prime, since any other hypothetical even prime \(n\) would have at least three distinct (positive) divisors, namely \(1\), \(2\), and \(n\).
The units \(\pm 1\) and the primes have no proper divisors.
\( \begin{aligned} 1 && & \textcolor{red} {1 \mid 1} \\ 2 && & \textcolor{green}{1 \mid 2} && \textcolor{green}{2 \mid 2} \\ 3 && & \textcolor{green}{1 \mid 3} && 2 \nmid 3 && \textcolor{green}{3 \mid 3} \\ 4 && & \textcolor{red} {1 \mid 4} && \textcolor{red}{2 \mid 4} && 3 \nmid 4 && \textcolor{red}{4 \mid 4} \\ 5 && & \textcolor{green}{1 \mid 5} && 2 \nmid 5 && 3 \nmid 5 && 4 \nmid 5 && \textcolor{green}{5 \mid 5} \\ 6 && & \textcolor{red} {1 \mid 6} && \textcolor{red}{2 \mid 6} && \textcolor{red}{3 \mid 6} && 4 \nmid 6 && 5 \nmid 6 && \textcolor{red}{6 \mid 6} \\ 7 && & \textcolor{green}{1 \mid 7} && 2 \nmid 7 && 3 \nmid 7 && 4 \nmid 7 && 5 \nmid 7 && 6 \nmid 7 && \textcolor{green}{7 \mid 7} \\ 8 && & \textcolor{red} {1 \mid 8} && \textcolor{red}{2 \mid 8} && 3 \nmid 8 && \textcolor{red}{4 \mid 8} && 5 \nmid 8 && 6 \nmid 8 && 7 \nmid 8 && \textcolor{red}{8 \mid 8} \\ 9 && & \textcolor{red} {1 \mid 9} && 2 \nmid 9 && \textcolor{red}{3 \mid 9} && 4 \nmid 9 && 5 \nmid 9 && 6 \nmid 9 && 7 \nmid 9 && 8 \nmid 9 && \textcolor{red}{9 \mid 9} \\ 10 && & \textcolor{red}{1 \mid 10} && \textcolor{red}{2 \mid 10} && 3 \nmid 10 && 4 \nmid 10 && \textcolor{red}{5 \mid 10} && 6 \nmid 10 && 7 \nmid 10 && 8 \nmid 10 && 9 \nmid 10 && \textcolor{red}{10 \mid 10} \\ 11 && & \textcolor{green}{1 \mid 11} && 2 \nmid 11 && 3 \nmid 11 && 4 \nmid 11 && 5 \nmid 11 && 6 \nmid 11 && 7 \nmid 11 && 8 \nmid 11 && 9 \nmid 11 && 10 \nmid 11 && \textcolor{green}{11 \mid 11} \\ \vdots \\ \end{aligned} \)
for p in [2, 3, 5, 7]:
print(101 % p)
1
2
1
3
Composite#
The primes and composites form a partition of the set of positive integers greater than one.
Claim: every positive integer is a product of primes#
Euclid’s Theorem on the infinitude of primes#
Euler’s proof of the infinitude of primes#
Claim: every number of the form \(4k - 1\) has a prime factor of this form#
Claim: there are infinitely many primes of the form \(4k - 1\)#
Claim: every number of the form \(6k - 1\) has a prime factor of this form#
Claim: there are infinitely many primes of the form \(6k - 1\)#
Claim: \(p \mid a \iff p \mid a^n\)#
\( \begin{array}{rrcc} 1 & 2. 0 + 1 & 4. 0 + 1 & 6.0 + 1 & 8.0 + 1 & \\ & 2. 1 - 1 & & & & \\ 3 & 2. 1 + 1 & 4. 1 - 1 & & & \\ & 2. 2 - 1 & & & & \\ 5 & 2. 2 + 1 & 4. 1 + 1 & 6.1 - 1 & & \\ & 2. 3 - 1 & & & & \\ 7 & 2. 3 + 1 & 4. 2 - 1 & 6.1 + 1 & 8.1 - 1 & \\ & 2. 4 - 1 & & & & \\ 9 & 2. 4 + 1 & 4. 2 + 1 & & 8.1 + 1 & \\ & 2. 5 - 1 & & & & \\ 11 & 2. 5 + 1 & 4. 3 - 1 & 6.2 - 1 & & \\ & 2. 6 - 1 & & & & \\ 13 & 2. 6 + 1 & 4. 3 + 1 & 6.2 + 1 & & \\ & 2. 7 - 1 & & & & \\ 15 & 2. 7 + 1 & 4. 4 - 1 & & 8.2 - 1 & \\ & 2. 8 - 1 & & & & \\ 17 & 2. 8 + 1 & 4. 4 + 1 & 6.3 - 1 & 8.2 + 1 & \\ & 2. 9 - 1 & & & & \\ 19 & 2. 9 + 1 & 4. 5 - 1 & 6.3 + 1 & & \\ & 2.10 - 1 & & & & \\ 21 & 2.10 + 1 & 4. 5 + 1 & & & \\ & 2.11 - 1 & & & & \\ 23 & 2.11 + 1 & 4. 6 - 1 & 6.4 - 1 & 8.3 - 1 & \\ & 2.12 - 1 & & & & \\ 25 & 2.12 + 1 & 4. 6 + 1 & 6.4 + 1 & 8.3 + 1 & \\ & 2.13 - 1 & & & & \\ 27 & 2.13 + 1 & 4. 7 - 1 & & & \\ & 2.14 - 1 & & & & \\ 29 & 2.14 + 1 & 4. 7 + 1 & 6.5 - 1 & & \\ & 2.15 - 1 & & & & \\ 31 & 2.15 + 1 & 4. 8 - 1 & 6.5 + 1 & 8.4 - 1 & \\ & 2.16 - 1 & & & & \\ 33 & 2.16 + 1 & 4. 8 + 1 & & 8.4 + 1 & \\ & 2.17 - 1 & & & & \\ 35 & 2.17 + 1 & 4. 9 - 1 & 6.6 - 1 & & \\ & 2.18 - 1 & & & & \\ 37 & 2.18 + 1 & 4. 9 + 1 & 6.6 + 1 & & \\ & 2.19 - 1 & & & & \\ 39 & 2.19 + 1 & 4.10 - 1 & & 8.5 - 1 & \\ & 2.20 - 1 & & & & \\ 41 & 2.20 + 1 & 4.10 + 1 & 6.7 - 1 & 8.5 + 1 & \\ & 2.21 - 1 & & & & \\ 43 & 2.21 + 1 & 4.11 - 1 & 6.7 + 1 & & \\ & 2.22 - 1 & & & & \\ 45 & 2.22 + 1 & 4.11 + 1 & & & \\ & 2.23 - 1 & & & & \\ 47 & 2.23 + 1 & 4.12 - 1 & 6.8 - 1 & 8.6 - 1 & \\ & 2.24 - 1 & & & & \\ 49 & 2.24 + 1 & 4.12 + 1 & 6.8 + 1 & 8.6 + 1 & \\ & 2.25 - 1 & & & & \\ \end {array} \)
\( \begin{array}{l} 2k & \\ 2k + 1 &= 2(k + 1) - 1 \\ \end {array} \)
\( \begin{aligned} & 2 \mid n && \iff 2k = n - 0 \iff n \equiv \phantom{\pm}0 \mod 2 \\ & 2 \mid n \pm 1 && \iff 2k = n \pm 1 \iff n \equiv \mp 1 \mod 2 \\ \end {aligned} \)
An integer takes exactly one of the following forms.
multiple of \(2\)
\(2k \pm 1\) - an odd number is expressed as both \(2k + 1\) for some \(k\) and as \(2k' - 1\) with \(k' = k + 1\)
\( \begin{array}{llll} 4k &= 2(2k) & & \text{multiples of both } 2 \text{ and } 4 \\ 4k + 1 & &= 4(k + 1) - 3 & \text{} \\ 4k + 2 &= 2(2k + 1) &= 4(k + 1) - 2 & \text{multiples of } 2 \text{ but not } 4 \\ 4k + 3 & &= 4(k + 1) - 1 & \text{} \\ \end {array} \)
An integer takes exactly one of the following forms.
multiple of \(2\)
multiple of \(2, 4\)
multiple of \(2\) but not \(4\)
odd number of the form \(4k \pm 1\)
both \(4k + 1\) for some \(k\) and \(4k' - 3\) with \(k' = k + 1\)
both \(4k - 1\) for some \(k\) and \(4k' + 3\) with \(k' = k - 1\)
\( \begin{aligned} & 4 \mid n && \iff 4k = n - 0 \iff n \equiv \phantom{-1 \equiv \pm} 0 \mod 4 \\ & 4 \mid n + 1 && \iff 4k = n + 1 \iff n \equiv -1 \equiv \phantom{\pm} 3 \mod 4 && \iff 4 \mid n - 3 \\ & 4 \mid n \pm 2 && \iff 4k = n \pm 2 \iff n \equiv \phantom{-1 \equiv} \mp 2 \mod 4 \\ & 4 \mid n + 3 && \iff 4k = n + 3 \iff n \equiv -3 \equiv \phantom{\pm} 1 \mod 4 && \iff 4 \mid n - 1 \\ \end {aligned} \)
\( \begin{aligned} (4k)^2 &&&= 4(4k^2) &&= 4k' \\ (4k + 1)^2 &= 16k^2 + 8k + 1 &&= 4(2k(2k + 1) + 1 &&= 4k' + 1 \\ (4k + 2)^2 &= 16k^2 + 16k + 4 &&= 4(4k( k + 1) + 1) &&= 4k' \\ (4k + 3)^2 &= 16k^2 + 24k + 9 &&= 4(4k^2 + 6k + 2) + 1 &&= 4k' + 1 \\ \end {aligned} \)
\( \begin{aligned} n \equiv 0 \mod 4 \quad \iff \quad n^2 \equiv 0 \mod 4 \\ n \equiv 1 \mod 4 \quad \iff \quad n^2 \equiv 1 \mod 4 \\ n \equiv 2 \mod 4 \quad \iff \quad n^2 \equiv 0 \mod 4 \\ n \equiv 3 \mod 4 \quad \iff \quad n^2 \equiv 1 \mod 4 \\ \end {aligned} \)
\( \begin{array}{llll} 6k &= 2(3k) & & \text{multiples of } 2, 3, 6 \\ 6k + 1 & &= 6(k + 1) - 5 & \text{} \\ 6k + 2 &= 2(3k + 1) &= 6(k + 1) - 4 & \text{multiples of } 2 \text{ but not } 3, 6 \\ 6k + 3 &= 3(2k + 1) &= 6(k + 1) - 3 & \text{multiples of } 3 \text{ but not } 2, 6 \\ 6k + 4 &= 2(3k + 2) &= 6(k + 1) - 2 & \text{multiples of } 2 \text{ but not } 3, 6 \\ 6k + 5 & &= 6(k + 1) - 1 & \text{} \\ \end {array} \)
An integer takes exactly one of the following forms.
multiple of \(2\)
multiple of \(2, 3, 6\)
multiple of \(2\) but not \(3, 6\)
odd multiple of \(3\)
odd number of the form \(6k \pm 1\)
both \(6k + 1\) for some \(k\) and \(6k' - 5\) with \(k' = k + 1\)
both \(6k - 1\) for some \(k\) and \(6k' + 5\) with \(k' = k - 1\)
\( \begin{aligned} & 6 \mid n && \iff 6k = n - 0 \iff n \equiv \phantom{-1 \equiv \pm} 0 \mod 6 \\ & 6 \mid n + 1 && \iff 6k = n + 1 \iff n \equiv -1 \equiv \phantom{\pm} 5 \mod 6 & \iff 6 \mid n - 5 \\ & 6 \mid n + 2 && \iff 6k = n + 2 \iff n \equiv -2 \equiv \phantom{\pm} 4 \mod 6 & \iff 6 \mid n - 4 \\ & 6 \mid n \pm 3 && \iff 6k = n \pm 3 \iff n \equiv \phantom{-1 \equiv} \mp 3 \mod 6 \\ & 6 \mid n + 4 && \iff 6k = n + 4 \iff n \equiv -4 \equiv \phantom{\pm} 2 \mod 6 & \iff 6 \mid n - 2 \\ & 6 \mid n + 5 && \iff 6k = n + 5 \iff n \equiv -5 \equiv \phantom{\pm} 1 \mod 6 & \iff 6 \mid n - 1 \\ \end {aligned} \)
\( \begin{array}{llll} 8k &= 2(2(2k)) & & \text{multiples of } 2, 4, 8 \\ 8k + 1 & &= 8(k + 1) - 7 & \text{} \\ 8k + 2 &= 2(4k + 1) &= 8(k + 1) - 6 & \text{multiples of } 2 \text{ but not } 4, 8 \\ 8k + 3 & &= 8(k + 1) - 5 & \text{} \\ 8k + 4 &= 2(2(2k + 1)) &= 8(k + 1) - 4 & \text{multiples of } 2, 4 \text{ but not } 8 \\ 8k + 5 & &= 8(k + 1) - 3 & \text{} \\ 8k + 6 &= 2(4k + 3) &= 8(k + 1) - 2 & \text{multiples of } 2 \text{ but not } 4, 8 \\ 8k + 7 & &= 8(k + 1) - 1 & \text{} \\ \end {array} \)
An integer takes exactly one of the following forms.
multiple of \(2\)
multiple of \(2, 4, 8\)
multiple of \(2, 4\) but not \(8\)
multiple of \(2\), but not \(4, 8\)
odd number of the form \(8k \pm 1\)
both \(8k + 1\) for some \(k\) and \(8k' - 7\) with \(k' = k + 1\)
both \(8k - 1\) for some \(k\) and \(8k' + 7\) with \(k' = k - 1\)
odd number of the form \(8k \pm 3\)
both \(8k + 3\) for some \(k\) and \(8k' - 5\) with \(k' = k + 1\)
both \(8k - 3\) for some \(k\) and \(8k' + 5\) with \(k' = k - 1\)
\( \begin{aligned} & 8 \mid n && \iff 8k = n - 0 \iff n \equiv \phantom{-1 \equiv \pm} 0 \mod 8 \\ & 8 \mid n + 1 && \iff 8k = n + 1 \iff n \equiv -1 \equiv \phantom{\pm} 7 \mod 8 & \iff 8 \mid n - 7 \\ & 8 \mid n + 2 && \iff 8k = n + 2 \iff n \equiv -2 \equiv \phantom{\pm} 6 \mod 8 & \iff 8 \mid n - 6 \\ & 8 \mid n + 3 && \iff 8k = n + 3 \iff n \equiv -3 \equiv \phantom{\pm} 5 \mod 8 & \iff 8 \mid n - 5 \\ & 8 \mid n \pm 4 && \iff 8k = n \pm 4 \iff n \equiv \phantom{-1 \equiv} \mp 4 \mod 8 \\ & 8 \mid n + 5 && \iff 8k = n + 5 \iff n \equiv -5 \equiv \phantom{\pm} 3 \mod 8 & \iff 8 \mid n - 3 \\ & 8 \mid n + 6 && \iff 8k = n + 5 \iff n \equiv -6 \equiv \phantom{\pm} 2 \mod 8 & \iff 8 \mid n - 2 \\ & 8 \mid n + 7 && \iff 8k = n + 5 \iff n \equiv -7 \equiv \phantom{\pm} 1 \mod 8 & \iff 8 \mid n - 1 \\ \end {aligned} \)
\( \begin{array}{llll} 10k &= 2(5k) & & \text{multiples of } 2, 5, 10 \\ 10k + 1 & &= 10(k + 1) - 9 & \text{} \\ 10k + 2 &= 2(5k + 1) &= 10(k + 1) - 8 & \text{multiples of } 2 \text{ but not } 5, 10 \\ 10k + 3 & &= 10(k + 1) - 7 & \text{} \\ 10k + 4 &= 2(5k + 2) &= 10(k + 1) - 6 & \text{multiples of } 2 \text{ but not } 5, 10 \\ 10k + 5 &= 5(2k + 1) &= 10(k + 1) - 5 & \text{multiples of } 5 \text{ but not } 2, 10 \\ 10k + 6 &= 2(5k + 3) &= 10(k + 1) - 4 & \text{multiples of } 2 \text{ but not } 5, 10 \\ 10k + 7 & &= 10(k + 1) - 3 & \text{} \\ 10k + 8 &= 2(5k + 4) &= 10(k + 1) - 2 & \text{multiples of } 2 \text{ but not } 5, 10 \\ 10k + 9 & &= 10(k + 1) - 1 & \text{} \\ \end {array} \)
An integer takes exactly one of the following forms.
multiple of \(2\)
multiple of \(2, 5, 10\)
multiple of \(2\) but not \(5, 10\)
odd multiple of \(5\)
odd number of the form \(10k \pm 1\)
both \(10k + 1\) for some \(k\) and \(10k' - 9\) with \(k' = k + 1\)
both \(10k - 1\) for some \(k\) and \(10k' + 9\) with \(k' = k - 1\)
odd number of the form \(10k \pm 3\)
both \(10k + 3\) for some \(k\) and \(10k' - 7\) with \(k' = k + 1\)
both \(10k - 3\) for some \(k\) and \(10k' + 7\) with \(k' = k - 1\)
\( \begin{array}{llll} 12k &= 2(2(3k)) & & \text{multiples of } 2, 3, 4, 6, 12 \\ 12k + 1 & &= 12(k + 1) - 11 & \text{} \\ 12k + 2 &= 2(6k + 1) &= 12(k + 1) - 10 & \text{multiples of } 2 \text{ but not } 3, 4, 6, 12 \\ 12k + 3 &= 3(4k + 1) &= 12(k + 1) - 9 & \text{multiples of } 3 \text{ but not } 2, 4, 6, 12 \\ 12k + 4 &= 2(2(3k + 1)) &= 12(k + 1) - 8 & \text{multiples of } 2, 4 \text{ but not } 3, 6, 12 \\ 12k + 5 & &= 12(k + 1) - 7 & \text{} \\ 12k + 6 &= 2(3(2k + 1)) &= 12(k + 1) - 6 & \text{multiples of } 2, 3, 6 \text{ but not } 4, 12 \\ 12k + 7 & &= 12(k + 1) - 5 & \text{} \\ 12k + 8 &= 2(2(3k + 2)) &= 12(k + 1) - 4 & \text{multiples of } 2, 4 \text{ but not } 3, 6, 12 \\ 12k + 9 &= 3(4k + 3) &= 12(k + 1) - 3 & \text{multiples of } 3 \text{ but not } 2, 4, 6, 12 \\ 12k + 10 &= 2(6k + 5) &= 12(k + 1) - 2 & \text{multiples of } 2 \text{ but not } 3, 4, 6, 12 \\ 12k + 11 & &= 12(k + 1) - 1 & \text{} \\ \end {array} \)
An integer takes exactly one of the following forms.
multiple of \(2\)
multiple of \(2, 3, 4, 6, 12\)
multiple of \(2, 3, 6\) but not \(4, 12\)
multiple of \(2, 4\) but not \(3, 6, 12\)
multiple of \(2\) but not \(3, 4, 6, 12\)
odd multiple of \(3\)
odd number of the form \(12k \pm 1\)
both \(12k + 1\) for some \(k\) and \(12k' - 11\) with \(k' = k + 1\)
both \(12k - 1\) for some \(k\) and \(12k' + 11\) with \(k' = k - 1\)
odd number of the form \(12k \pm 5\)
both \(12k + 5\) for some \(k\) and \(12k' - 7\) with \(k' = k + 1\)
both \(12k - 5\) for some \(k\) and \(12k' + 7\) with \(k' = k - 1\)
Division Theorem#
Division of an integer by a positive integer produces a quotient and a remainder. (Operating on remainders will form the basis of modular arithmetic.)
[Bressoud pp. 7]
[Humphreys & Prest 1.1.1 pp. 3-4]
[Humphreys & Prest pp. 4, 14]
Note on notation and programming#
We can use the following notation to express the quotient and the remainder:
\( \begin{aligned} q &= a \textbf{ div } d \\ r &= a \textbf{ mod } d \\ \end {aligned} \)
When \(a\) is an integer and \(d\) is a positive integer:
\( \begin{aligned} q &= a \textbf{ div } d &&= \lfloor a/d \rfloor \\ r &= a \textbf{ mod } d &&= a - d \lfloor a/d \rfloor \\ \end {aligned} \)
If \(d\) is fixed then \(\textbf{div}\) and \(\textbf{mod}\) are functions on the set of integers:
\( \begin{aligned} \textbf{div}_d &: \mathbb{Z} \to \mathbb{Z} & \textbf{div}_d(a) \mapsto q \\ \textbf{mod}_d &: \mathbb{Z} \to \mathbb{N} & \textbf{mod}_d(a) \mapsto r \\ \end {aligned} \)
In programming languages, the modulo operator for \(a \lt 0\) may return \(a - d \lceil a/d \rceil\) instead of \(a \textbf{ mod } d = a - d \lfloor a/d \rfloor\). Also unlike \(a \textbf{ mod } d\) the modulo operator may be defined when \(d \lt 0\), and even when \(d = 0\).
\( \begin{aligned} 17 & \textbf{ mod } 3 = & 17 - 3 & \times \lfloor \underset{ 5.\bar{6}}{\phantom{-}17/3} \rfloor = 2 && & 17 &= 3 \times 5 + 2 \\ -17 & \textbf{ mod } 3 = & -17 - 3 & \times \lfloor \underset{-5.\bar{6}}{ -17/3} \rfloor = 1 && & -17 &= 3 \times (-6) + 1 \\ \end {aligned} \)
print(f'{ 17 % 3:>2}')
print(f'{-17 % 3:>2}')
print(f'{-17 % -3:>2}')
print(f'{ 17 % -3:>2}')
2
1
-2
-1
Division via repeated subtraction#
# division via repeated subtraction
# positive integers 1 <= d <= n
def udiv (n, d):
q, r = 0, n
while r >= d:
r -= d
q += 1
return q, r
def div (n, d):
assert(d != 0)
if d < 0:
q, r = udiv(n, -d)
return -q, r
if n < 0:
q, r = div(-n, d)
if r == 0:
return -q, 0
else:
return -q-1, d-r
return udiv(n, d)
n = -20
d = 3
q, r = div(n, d)
print(f'{n} = {d} x {q} + {r}')
-20 = 3 x -7 + 1
GCD#
\(Theorem\) [Humphreys & Prest 1.1.2 pp. 6]
Let \(a\) and \(b\) be positive integers. \(a, b \in \mathbb{P}\)
There is a positive integer \(d\) such that(i) \(d\) divides \(a\) and \(d\) divides \(b\), and
(ii) if \(c\) is a positive integer which divides both \(a\) and \(b\) then \(c\) divides \(d\) (i.e., any common divisor of \(a\) and \(b\) divides \(d\)).
\(Proof \,\, by \,\, contradiction\) [Humphreys & Prest pp. 6]
Let \(D\) be the set of all positive integers of the form \(as + bt\) where \(s\) and \(t\) vary over the set of all integers.
\(D\) is non-empty since \(a = a \cdot 1 + b \cdot 0\) is in \(D\).
\(D\) has a least element \(d\) by the well-ordering principle.
Since \(d\) is in \(D\), there are integers \(s\) and \(t\) such that \(d = as + bt\).
We must show that (ii) any common divisor \(c\) of \(a\) and \(b\) is a divisor of \(d\).Let \(c \mid a\) and \(c \mid b\).
Then there are integers \(g\) and \(h\) such that \(a = cg\) and \(b = ch\).
\(as + bt = (cg)s + (ch)t = c(gs + ht) \implies c \mid c(gs + ht) \implies c \mid as + bt \implies c \mid d\)
\(\therefore c \mid d\)We must show that (i) \(d \mid a\) and \(d \mid b\).
Showing that \(d \mid a\) is sufficient because \(a\) and \(b\) are interchangeable throughout the proof and so, by symmetry, \(d \mid b\).We may write \(a = dq + r \,\, , \,\, 0 \le r \lt d\) by the division theorem.
To show that \(d \mid a\) is to show that \(r = 0\).
\(a = dq + r \implies \textcolor{green}{r} = a - dq = a - (as + bt)q = \textcolor{green}{a(1 - sq) + b(-tq)}\)
If \(r\) were positive then it would meet the criteria of \(D\) and so would belong to \(D\).
But \(d\) was chosen to be minimal in \(D\) and \(r\) is strictly less than \(d\). \(Contradiction!\)
\(\therefore (r = 0) \land (d \mid a) \land (d \mid b)\)
\(\blacksquare\)
\(Definition\) [Humphreys & Prest pp. 7] [Bressoud pp. 6]
Let \(a\) and \(b\) be integers.
The integer \(d\) satisfying conditions (i) and (ii) of theorem 1.1.2 is called the greatest common divisor of \(a\) and \(b\) and is denoted \(gcd(a, b)\).
In other words, the greatest common divisor of \(a\) and \(b\) is the largest positive integer which divides both \(a\) and \(b\).
Note that \(gcd(a, b) = gcd(b, a)\).
Note that if \(a \mid b\) then \(a = gcd(a, b)\).
Claim: \(\gcd(a/d, b/d) = 1\) with \(d = \gcd(a, b)\)#
Claim: \(\gcd(a + by, b) = \gcd(a, b)\)#
Claim: \(\gcd(a, b) = 1 \implies \gcd(a^m, b^n) = 1\)#
UNDER CONSTRUCTION
Claim: if \(\gcd(a, b) = 1\) and \(ax = by\) then \(x = bz, y = az\)#
Bézout’s Identity#
[Bressoud Lemma 1.5 pp. 6]
[Vaughan Corollary 1.14]
[Bressoud pp. 6]
Claim: \(\gcd(a, b)\) is the smallest positive integral linear combination of \(a\) and \(b\)#
Claim: \(\gcd(am, bm) = m \gcd(a, b)\)#
Euclid’s Lemma#
The following theorem is a property which is characteristic of primes and is sometimes used to define them.
[Bressoud pp. 6]
[Humphreys & Prest Theorem 1.3.1 pp. 26]
[Vaughan Theorem 1.15]
Euclid’s Lemma is not obvious
Consider the set of integers \(\mathcal{A}\) of the form \(4k + 1\) which is closed under multiplication:
\((4k_1 + 1)(4k_2 + 1) = 4^2k_1k_2 + 4k_1 + 4k_2 + 1 = 4 (\underbrace{4k_1k_2 + k_1 + k_2}_{k_3}) + 1\)
Here are the first few members of this set:
\( \begin{aligned} 4(1) + 1 &= \phantom{1} 5 \\ 4(2) + 1 &= \phantom{1} 9 \\ 4(3) + 1 &= 13 \\ 4(4) + 1 &= 17 \\ 4(5) + 1 &= 21 \\ \color{red}{4(6) + 1} &\phantom{.} \color{red}{= 25} \\ 4(7) + 1 &= 29 \\ 4(8) + 1 &= 33 \\ 4(9) + 1 &= 37 \\ 4(10) + 1 &= 41 \\ \color{red}{4(11) + 1} &\phantom{.} \color{red}{= 45} \\ 4(12) + 1 &= 49 \\ \end {aligned} \)
A prime in this system is defined as a number which is only divisible by \(1\) and itself:
\(5, 9, 13, 17, 21, 29, 33, 37, 41, 49, \dotsc\)
The prime factorization of \(25\) in this system is \(5 \times 5\) and the prime factorization of \(45\) in this system is \(5 \times 9\).
In this system, prime factorization is not unique: \(441 = 9 \times 49 = 21^2\)
\(21 \mid 9 \times 49\) but \(21 \nmid 9\) and \(21 \nmid 49\)
\(\mathcal{A}\) is not closed under addition, but \(\mathbb{Z}\) is.
Extension of Euclid’s lemma#
The following lemma is an extension of the previous theorem.
[Humphreys & Prest Lemma pp. 27]
Claim: if \(p \mid p_1 \dots p_j \dots p_r\) then \(p = p_j\) for some \(1 \le j \le r\)#
Euclid’s Lemma can be used to establish the following.
[Vaughan Theorem 1.17]
Computing GCD#
[Humphreys & Prest Lemma 1.1.4 pp. 8] Euclid’s Elements Book VII Proposition 1
\(Proof\) [Humphreys & Prest pp. 8]
Let \(d = gcd(a, b)\).
\(b = aq + r \iff b - aq = r\)By definition, \(d \mid a\) and \(d \mid b\).
Then \(d \mid b - aq \iff d \mid r\) and so \(d\) is a common divisor of \(a\) and \(r\).
\(\therefore d \mid gcd(a, r)\) since a common divisor of two integers also divides their \(gcd\).By definition, \(gcd(a, r) \mid a\) and \(gcd(a, r) \mid r\).
\(gcd(a, r) \mid aq + r \iff gcd(a, r) \mid b\) and so \(gcd(a, r)\) is a common divisor of \(a\) and \(b\).
\(\therefore gcd(a, r) \mid d\) since a common divisor of two integers also divides their \(gcd\).\(\therefore d = gcd(a, r) = gcd(a, b)\) since \(d \mid gcd(a, r)\) and \(gcd(a, r) \mid d\).
\(\blacksquare\)
\(Example\) [Humphreys & Prest pp. 8-9]
Let \(a = 30\) and \(b = 171\).
Then we can write \(171 = 30q + r\) with \(q = 5\) and \(r = 21\) (or \(q = 3\) and \(r = 81\)).
Let \(d = gcd(30, 171)\).
\(171 = 30 \cdot 5 + 21 \iff 171 - 30 \cdot 5 = 21\)By definition, \(d \mid 30\) and \(d \mid 171\).
Then \(d \mid 171 - 30 \cdot 5 \iff d \mid 21\).
\(\therefore d \mid gcd(30, 21)\).By definition, \(gcd(30, 21) \mid 30\) and \(gcd(30, 21) \mid 21\).
\(gcd(30, 21) \mid 30 \cdot 5 + 21 \iff gcd(30, 21) \mid 171\).
\(gcd(30, 21) \mid d\).\(\therefore d = gcd(30, 21) = gcd(30, 171)\).
Prime Factorization#
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.
Claim:#
\(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: \(a\) and \(b\) are coprime iff \(a^2\) and \(b^2\) are coprime#
\(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\)
Fundamental Theorem of Arithmetic#
FUNDAMENTAL THEOREM OF ARITHMETIC [Vaughan Theorem 1.18]
Factorization into primes is unique up to ordering of the factors (i.e., regardless of the ordering of the multiplicands).
More precisely, if \(a\) is a nonzero integer and \(a \ne \pm 1\) then \(a = (\pm 1) p_1 p_2 \dots p_r\) for some \(r \ge 1\) and primes \(p_1, p_2, \dotsc, p_r\).
The choice of \(r\), the sign, and the factors \(p_j\) are unique.
We can write \(a = (\pm 1) p_1 p_2 \dots p_r\) even when \(a = \pm 1\) by interpreting the product over primes as an empty product.
Proof by induction on \(r\)
It is clear that we may suppose that \(a \gt 0\); thus that \(a \ge 2\).
Existence
We already know from [Vaughan Theorem 1.4] that \(a\) is a product of primes: \(a = p_1 p_2 \dots p_r\) with \(r \ge 1\).
Uniqueness
Base Case \(r = 1\)
Suppose \(r = 1\) so that \(a = p_1 = p_1' p_2' \dots p_s'\) where \(s \ge 1\).
Then \(p_1' \mid p_1 \implies p_1' = p_1 \iff p_1 = p_1 p_2' \dots p_s' \iff 1 = p_2' \dots p_s' \implies s = 1\)
Inductive Case
Suppose that \(r \ge 1\) and that uniqueness has been established for all products of \(r\) primes.
Suppose that \(a = p_1 p_2 \dots p_{r + 1} = p_1' p_2' \dots p_s'\) for some \(r \ge 1\)
Then by [Vaughan Theorem 1.17] \(p_1' = p_j\) for some \(j\) and then
\(p_2' \dots p_s' = p_1 p_2 \dots p_{r + 1} / p_j\)
and the inductive hypothesis can be applied to obtain the desired conclusion.
\(\blacksquare\)
Fundamental Theorem (alternative)
Every integer greater than \(1\) has a prime factor.
Inductive Hypothesis: Let \(1 \lt m \lt n\) have a prime factor.
Case: \(n\) is prime.
Case: \(n\) is not prime. Then it has a factorization \(n = ab\) where \(1 \lt a, b \lt n\). By the inductive hypothesis, \(a\) has a prime factor \(p\). Since \(p \mid a\) and \(a \mid n\) it is the case that \(p \mid n\).
\(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\)
\(Examples\) [Humphreys & Prest pp. 29-30]
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.
\(Proof \,\, of \,\, uniqueness\) [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 \ge 2\) then \(n\) would have distinct divisors \(1, q_1, q_1q_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 \iff 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.
\(\blacksquare\)
Claim: if \(n\) is a power of \(2\) then it has no odd divisors other than \(\pm 1\)#
CLAIM
If \(n\) is a power of \(2\) then \(n\) has no odd divisors other than \(\pm 1\).
\(\exists k \in \mathbb{N} \quad n = 2^k \quad \implies \quad \forall d \in \mathbb{Z} \quad d \ne \pm 1 \quad d \nmid n\)
PROOF
The fundamental theorem of arithmetic says that any positive integer \(n\) has a unique prime factorization
\( \begin{aligned} n = (\pm 1) \times 2^k \times \underbrace{p_1^{a_1} \times p_2^{a_2} \times \dotsb \times p_r^{a_r}}_{\text{odd prime factors}} = (\pm 1) \times 2^k \times \underset{\text{odd}}{m} \end {aligned} \)
where \(k \ge 0\) is the largest power of \(2\) that divides \(n\) and \(m = p_1^{a_1} p_2^{a_2} \dots p_r^{a_r}\) is an odd number
(all even factors are accounted for by \(2^k\), and a product of odd numbers is odd)
(and \(n = 1\) is the empty product of primes)
\(\blacksquare\)
Canonical representation of a positive integer#
Every positive integer \(n\) can be represented in exactly one way as a product of prime powers
\( \begin{aligned} n = p_1^{a_1} p_1^{a_2} \dots p_k^{a_k} = \prod_{i=1}^k p_i^{a_i} \end {aligned} \)
where \(2 \le p_1 \lt p_2 \lt \dots \lt p_k\) are primes and the \(a_i\) are positive integers.
\( \begin{aligned} k &&& n \\ 0 &&& 1 = \prod_{i=1}^0 p_i^{a_i} \\ 1 &&& 2 = p_1^{a_1} \\ \end {aligned} \)
\(\gcd(a, b) = \prod_{i=1}^k p_i^{\min(r_i, s_i)}\)#
Property of GCD
Suppose \(a\) and \(b\) are positive integers. Then by the fundamental theorem of arithmetic we can write
\(a = p_1^{r_1} \dots p_k^{r_k}\) and \(b = p_1^{s_1} \dots p_k^{s_k}\)
where \(p_1, \dotsc, p_k\) are the different primes in the factorization of \(a\) and \(b\) and we allow the possibility that the exponenets \(r_j, s_j\) may be zero. Then it is the case that
\(\gcd(a, b) = p_1^{\min(r_1, s_1)} \dots p_k^{\min(r_k, s_k)}\)
EXAMPLE
\( \begin{aligned} 20 &= p_1^2 p_2^0 p_3^1 = 2^2 \times 3^0 \times 5^1 \\ 75 &= p_1^0 p_2^1 p_3^2 = 2^0 \times 3^1 \times 5^2 \\ \gcd(20, 75) = 5 &= p_1^0 p_2^0 p_3^1 = 2^0 \times 3^0 \times 5^1 \\ \end {aligned} \)
\(\gcd(a^n, b^n) = \gcd(a, b)^n\)#
CLAIM
\(\gcd(a^n, b^n) = \gcd(a, b)^n\)
PROOF
Suppose \(a\) and \(b\) are positive integers with prime factorizations and GCD
\( \begin{array}{rcccc} a & = & (\pm 1) & \times & p_1^{r_1} & \times & p_2^{r_2} & \times & \dots & \times & p_k^{r_k} \\ b & = & (\pm 1) & \times & p_1^{s_1} & \times & p_2^{s_2} & \times & \dots & \times & p_k^{s_k} \\ \gcd(a, b) & = & & & p_1^{\min(r_1, s_1)} & \times & p_2^{\min(r_2, s_2)} & \times & \dots & \times & p_k^{\min(r_k, s_k)} \\ \end {array} \)
for some \(k \ge 1\).
Then for some \(n \ge 1\) we have
\( \begin{array}{rcccc} a^n & = & (\pm 1)^n & \times & p_1^{nr_1} & \times & p_2^{nr_2} & \times & \dots & \times & p_k^{nr_k} \\ b^n & = & (\pm 1)^n & \times & p_1^{ns_1} & \times & p_2^{ns_2} & \times & \dots & \times & p_k^{ns_k} \\ \gcd(a^n, b^n) & = & & & p_1^{\min(nr_1, ns_1)} & \times & p_2^{\min(nr_2, ns_2)} & \times & \dots & \times & p_k^{\min(nr_k, ns_k)} \\ \end {array} \)
\( \begin{aligned} \gcd(a^n, b^n) &= p_1^{\min(nr_1, ns_1)} p_2^{\min(nr_2, ns_2)} \dots p_k^{\min(nr_k, ns_k)} \\ &= p_1^{n \times \min(r_1, s_1)} p_2^{n \times \min(r_2, s_2)} \dots p_k^{n \times \min(r_k, s_k)} \\ &= \left( p_1^{\min(r_1, s_1)} p_2^{\min(r_2, s_2)} \dots p_k^{ \min(r_k, s_k)} \right)^n \\ &= \gcd(a, b)^n \end {aligned} \)
\(\blacksquare\)
Resources
LCM#
LEAST COMMON MULTIPLE
\( \begin{aligned} \text{lcm}[a, b] = \frac{ab}{\gcd(a, b)} = p_1^{\max(r_1, s_1)} \dots p_k^{\max(r_k, s_k)} \end {aligned} \)
Claim: \(\text{lcm}[a, b]\) is the smallest \(c\) with \(a \mid c\) and \(b \mid c\)#
Property of LCM
\(\text{lcm}[a, b]\) has the property that it is the smallest positive integer \(c\) so that \(a \mid c\) and \(b \mid c\).
GCD and LCM as prime factorizations#
\(Corollary\) [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\).
\(Examples\) [Humphreys & Prest pp. 31-32]
\(2\) and \(3\)
\(2\) and \(4\)
\(56\) and \(84\)
\(135\) and \(639\)
Fermat Primes#
\(Claim\)
If \(2^n + 1\) is prime where \(n \ge 1\) then \(n\) must be of the form \(2^k\) for some positive integer \(k\).
Mersenne Primes#
\(Claim\)
If \(2^n - 1\) is prime then \(n\) is prime.
Goldbach’s Conjecture#
\(Conjecture\)
Every even number greater than two can be expressed as the sum of two primes.
\(Examples\)
\(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).
Twin Primes Conjecture#
There are infinitely many pairs \((x, y)\) s.t. \(x\) and \(y\) are both prime and \(y = x + 2\).
Bounded Gap Theorem#
There are infinitely many pairs of primes that differ by at most \(70,000,000\).
Trial Division#
The simplest way to try to factorize a number \(n\) is by trial division.
TRIAL DIVISION
If \(n\) has a proper divisor \(m_1\) so that \(n = m_1 m_2\) with \(1 \lt m_1 \lt n\) whence \(1 \lt m_2 \lt n\) then it can be supposed that
\(m_1 \le m_2 \iff m_1 m_1 \le m_1 m_2 = n \iff m_1 \le \sqrt{n}\)
Thus each \(m_1 \le \sqrt{n}\) can be tried in turn. If no such factor is found then \(n\) is prime. Since the smallest proper divisor of \(n\) has to be the smallest prime factor of \(n\) we need only check the primes \(p\) with \(2 \le p \le \sqrt{n}\).
Even so, for large \(n\) this is hugely expensive in time. How to verify this?
Prime-Counting Function#
The number \(\pi(x)\) of primes \(p \le x\) is approximately
\( \begin{aligned} \pi(x) \sim \int_2^x \frac{d \alpha}{\ln \alpha} \sim \frac{x}{\ln x} \end {aligned} \)
Thus if \(n\) is about \(k\) bits in size and turns out to be prime or the product of two primes of about the same size, then the number of operations will be
\( \begin{aligned} \approx \frac{(2^{k/2})}{\ln (2^{k/2})} = \frac{2^{k/2}}{k/2 \ln 2} \end {aligned} \)
which is still exponential in the bit size.
Trial division is feasible for \(n\) out to about \(40\) bits on a modern computer; much beyond that it becomes hopeless. One area where trial division, or sophisticated variants thereor, are useful is in the production of tables of primes, or counts of primes such as the value of \(\pi(x)\).
Some values of the prime-counting function
\( \begin{aligned} \pi( 2) &=& 1 \\ \pi( 3) &=& 2 \\ \pi( 5) &=& 3 \\ \pi( 7) &=& 4 \\ \pi(10) &=& 4 \\ \pi(11) &=& 5 \\ \pi(13) &=& 6 \\ \pi(17) &=& 7 \\ \pi(19) &=& 8 \\ \pi(23) &=& 9 \\ \pi(29) &=& 10 \\ \pi(31) &=& 11 \\ \pi(37) &=& 12 \\ \pi(41) &=& 13 \\ \pi(43) &=& 14 \\ \pi(47) &=& 15 \\ \pi(53) &=& 16 \\ \pi(59) &=& 17 \\ \pi(61) &=& 18 \\ \pi(67) &=& 19 \\ \pi(71) &=& 20 \\ \pi(10^2) &=& \\ \pi(2^{16}) &=& 6542 \\ \end {aligned} \)
import math
print(f'x = 2^ 2 x/ln(x) = {2** 2/(math.log(2) * 2):>10.2f} {"π(2^ 2) = 2":>20}')
print(f'x = 2^ 3 x/ln(x) = {2** 3/(math.log(2) * 3):>10.2f} {"π(2^ 3) = 4":>20}')
print(f'x = 10 x/ln(x) = {10/(math.log(10)):>10.2f} {"π(10) = 4":>20}')
print(f'x = 2^ 4 x/ln(x) = {2** 4/(math.log(2) * 4):>10.2f} {"π(2^ 4) = 7":>20}')
print(f'x = 2^ 5 x/ln(x) = {2** 5/(math.log(2) * 5):>10.2f} {"π(2^ 5) = ":>20}')
print(f'x = 2^ 6 x/ln(x) = {2** 6/(math.log(2) * 6):>10.2f} {"π(2^ 6) = ":>20}')
print(f'x = 2^ 7 x/ln(x) = {2** 7/(math.log(2) * 7):>10.2f} {"π(2^ 7) = ":>20}')
print(f'x = 2^ 8 x/ln(x) = {2** 8/(math.log(2) * 8):>10.2f} {"π(2^ 8) = ":>20}')
print(f'x = 2^ 9 x/ln(x) = {2** 9/(math.log(2) * 9):>10.2f} {"π(2^ 9) = ":>20}')
print(f'x = 2^10 x/ln(x) = {2**10/(math.log(2) * 10):>10.2f} {"π(2^10) = ":>20}')
print(f'x = 2^11 x/ln(x) = {2**11/(math.log(2) * 11):>10.2f} {"π(2^11) = ":>20}')
print(f'x = 2^12 x/ln(x) = {2**12/(math.log(2) * 12):>10.2f} {"π(2^12) = ":>20}')
print(f'x = 2^13 x/ln(x) = {2**13/(math.log(2) * 13):>10.2f} {"π(2^13) = ":>20}')
print(f'x = 2^14 x/ln(x) = {2**14/(math.log(2) * 14):>10.2f} {"π(2^14) = ":>20}')
print(f'x = 2^15 x/ln(x) = {2**15/(math.log(2) * 15):>10.2f} {"π(2^15) = ":>20}')
print(f'x = 2^16 x/ln(x) = {2**16/(math.log(2) * 16):>10.2f} {"π(2^16) = 6542":>20}')
x = 2^ 2 x/ln(x) = 2.89 π(2^ 2) = 2
x = 2^ 3 x/ln(x) = 3.85 π(2^ 3) = 4
x = 10 x/ln(x) = 4.34 π(10) = 4
x = 2^ 4 x/ln(x) = 5.77 π(2^ 4) = 7
x = 2^ 5 x/ln(x) = 9.23 π(2^ 5) =
x = 2^ 6 x/ln(x) = 15.39 π(2^ 6) =
x = 2^ 7 x/ln(x) = 26.38 π(2^ 7) =
x = 2^ 8 x/ln(x) = 46.17 π(2^ 8) =
x = 2^ 9 x/ln(x) = 82.07 π(2^ 9) =
x = 2^10 x/ln(x) = 147.73 π(2^10) =
x = 2^11 x/ln(x) = 268.60 π(2^11) =
x = 2^12 x/ln(x) = 492.44 π(2^12) =
x = 2^13 x/ln(x) = 909.12 π(2^13) =
x = 2^14 x/ln(x) = 1688.37 π(2^14) =
x = 2^15 x/ln(x) = 3151.62 π(2^15) =
x = 2^16 x/ln(x) = 5909.28 π(2^16) = 6542
Sieve of Eratosthenes#
Trial division, or its sophisticated variants, is useful in the production of tables of primes or counts of primes (such as the value of the prime-counting function). The sieve of Eratosthenes is the simplest form of this.
[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.
Construct a \(\lfloor \sqrt{N} \rfloor \times \lfloor \sqrt{N} \rfloor\) array. Here \(N = 100\).
\( \begin{matrix*}[r] 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 \\ 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 \\ 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 \\ 50 & 51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 \\ 60 & 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 \\ 70 & 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 \\ 80 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 \\ 90 & 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 \\ \end {matrix*} \)
Forget about \(0\) and \(1\) and then for each successive element remaining remove the proper multiples.
For \(2\) we remove \(4, 6, \dotsc, 98\).
\( \begin{matrix*}[r] \phantom{00} & & 2 & 3 & \phantom{00} & 5 & \phantom{00} & 7 & \phantom{00} & 9 \\ & 11 & \phantom{00} & 13 & & 15 & & 17 & & 19 \\ & 21 & & 23 & & 25 & & 27 & & 29 \\ & 31 & & 33 & & 35 & & 37 & & 39 \\ & 41 & & 43 & & 45 & & 47 & & 49 \\ & 51 & & 53 & & 55 & & 57 & & 59 \\ & 61 & & 63 & & 65 & & 67 & & 69 \\ & 71 & & 73 & & 75 & & 77 & & 79 \\ & 81 & & 83 & & 85 & & 87 & & 89 \\ & 91 & & 93 & & 95 & & 97 & & 99 \\ \end {matrix*} \)
For the next remaining element \(3\) remove \(6, 9, \dotsc, 99\).
\( \begin{matrix*}[r] \phantom{00} & & 2 & 3 & \phantom{00} & 5 & \phantom{00} & 7 & \phantom{00} & \\ & 11 & \phantom{00} & 13 & & & & 17 & & 19 \\ & & & 23 & & 25 & & & & 29 \\ & 31 & & & & 35 & & 37 & & \\ & 41 & & 43 & & & & 47 & & 49 \\ & & & 53 & & 55 & & & & 59 \\ & 61 & & & & 65 & & 67 & & \\ & 71 & & 73 & & & & 77 & & 79 \\ & & & 83 & & 85 & & & & 89 \\ & 91 & & & & 95 & & 97 & & \\ \end {matrix*} \)
For the next remaining element \(5\) remove \(10, 15, \dotsc, 95\).
\( \begin{matrix*}[r] \phantom{00} & & 2 & 3 & \phantom{00} & 5 & \phantom{00} & 7 & \phantom{00} & \\ & 11 & \phantom{00} & 13 & & \phantom{00} & & 17 & & 19 \\ & & & 23 & & & & & & 29 \\ & 31 & & & & & & 37 & & \\ & 41 & & 43 & & & & 47 & & 49 \\ & & & 53 & & & & & & 59 \\ & 61 & & & & & & 67 & & \\ & 71 & & 73 & & & & 77 & & 79 \\ & & & 83 & & & & & & 89 \\ & 91 & & & & & & 97 & & \\ \end {matrix*} \)
For the next remaining element \(7\) remove \(14, 21, \dotsc, 98\).
\( \begin{matrix*}[r] \phantom{00} & & 2 & 3 & \phantom{00} & 5 & \phantom{00} & 7 & \phantom{00} & \\ & 11 & \phantom{00} & 13 & & \phantom{00} & & 17 & & 19 \\ & & & 23 & & & & & & 29 \\ & 31 & & & & & & 37 & & \\ & 41 & & 43 & & & & 47 & & \\ & & & 53 & & & & & & 59 \\ & 61 & & & & & & 67 & & \\ & 71 & & 73 & & & & & & 79 \\ & & & 83 & & & & & & 89 \\ & & & & & & & 97 & & \\ \end {matrix*} \)
After that the next remaining element is \(11\) and for that and its successors all the proper multiples have already been removed. Thus we now have a table of all the primes \(p \le 100\).
By counting the entries that remain one finds that \(\pi(100) = 25\).
The sieve of Eratosthenes produces approximately
\( \begin{aligned} \frac{n}{\log n} \end {aligned} \)
numbers in about
\( \begin{aligned} \sum_{p \le \sqrt{n}} \frac{n}{p} \sim n \log \log n \end {aligned} \)
operations.
Fermat Factorization#
Here is an idea that goes back to Fermat.
Given \(n\) suppose we can find \(x\) and \(y\) so that
\(n = x^2 - y^2\) with \(0 \le y \lt x\).
There may be a way of factoring \(n\) since the polynomial factorizes as \((x - y)(x + y)\).
We are only likely to try this if \(n\) is odd, say \(n = 2k + 1\), and then we might run into
\(n = 2k + 1 = \underbrace{(k + 1)^2}_{x^2} - \underbrace{\phantom{( + 1)}k^2}_{\, y^2 \,} = 1 \times (2k + 1)\)
which does not help much.
If \(n\) is prime then perforce \(x - y = 1\) and \(x + y = 2k + 1\) and this is the only solution.
If we can find a solution with \(x - y \gt 1\) then that would show that \(n\) is composite and would give a factorization.
If \(n = m_1 m_2\) with \(n\) odd and \(m_1 \le m_2\) then \(m_1\) and \(m_2\) are both odd and there is a solution with
\( \begin{aligned} x - y &= m_1 \\ x + y &= m_2 \\ \end {aligned} \)
\( \begin{aligned} x &= \frac{m_1 + m_2}{2} \\ y &= \frac{m_2 - m_1}{2} \\ \end {aligned} \)
Example
\( \begin{aligned} n & &&= x^2 - y^2 &&& x && y && m_1 && m_2 \\ 91 &= 100 - 9 &&= 10^2 - 3^2 &&& 10 && 3 && 7 && 13 & = 7 \times 13 \\ 1001 &= 2025 - 1024 &&= 45^2 - 32^2 &&& 45 && 32 && 13 && 77 & = 7 \times 11 \times 13 \\ \end {aligned} \)
This method has the downside that
\(x^2 = n + y^2\)
so already one is searching among \(x\) which are greater than \(\sqrt{n}\) and one could end up searching among that many possibilities. The chances of solving this easily for large \(n\) are quite small. Nevertheless, this is a fruitful idea. For example, suppose instead of \(n = x^2 - y^2\) we could solve
\(x^2 - y^2 = kn\)
for a relatively small value of \(k\). It is not very likely that \(x - y\) or \(x + y\) are factors of \(n\), but if we could compute
\(g = \gcd(x + y, n)\)
then we might find that \(g\) differs from \(1\) or \(n\) and so gives a factorization.
Moreover, there is a very fast way of computing GCD.
Example
\( \begin{aligned} n && k && kn & &&= x^2 - y^2 && x - y && x + y && \gcd(x + y, n) \\ 10001 && 8 && 80008 &= 80089 - 81 &&= 283^2 - 9^2 && 274 && 291 && \gcd(291, 10001) = 73 && 10001 = 73 \times 137 \\ \end {aligned} \)
Euclid’s Algorithm#
Given integers \(a\) and \(b\) not both zero there are integers \(x\) and \(y\) such that
\(\gcd(a, b) = ax + by\)
How do we find \(x\) and \(y\)?
Euclid’s algorithm gives a very efficient algorithm, and is still the basis for many numerical methods in arithmetical applications (e.g., factorization routines).
Extended Euclidean Algorithm#
Linear Diophantine Equations#
Linear Diophantine Equation
Euclid’s algorithm can be used to find the complete solution in integers to linear diophantine equations of the kind
\(ax + by = c\) where \(a\), \(b\), and \(c\) are integers, and \(x\) and \(y\) are all integers which satisfy this
\(\text{Case 1}\) Both \(a\) and \(b\) are zero. —– If \(a = b = 0\) then the linear diophantine equation is not soluble unless \(c = 0\); and then it is soluble by any \(x\) and \(y\), which is not very interesting.
\(\text{Case 2}\) One of \(a\) and \(b\) is non-zero.
\(\gcd(a, b) \mid (ax + by) \implies \gcd(a, b) \mid c\)
Choose \(x\) and \(y\) s.t. \(ax + by = \gcd(a, b)\). Then there is a solution
\( \begin{aligned} ax + by &= \gcd(a, b) \\ \frac{ax + by}{\gcd(a, b)} &= 1 \\ c \frac{ax + by}{\gcd(a, b)} &= c \\ a \left( \frac{xc}{\gcd(a, b)} \right) + b \left( \frac{yc}{\gcd(a, b)} \right) \end {aligned} \)
Let’s call this solution \(x_0, y_0\). Consider any other solution \(x, y\).
\( \begin{aligned} ax + by &= c \\ ax + by - ax_0 - by_0 &= c - c = 0 \\ ax - ax_0 &= by_0 - by \\ a(x - x_0) &= b(y_0 - y) \\ \frac{a}{\gcd(a, b)}(x - x_0) &= \frac{b}{\gcd(a, b)}(y_0 - y) \\ \end {aligned} \)
Recall that \(\gcd \left( \frac{a}{\gcd(a, b)}, \frac{b}{\gcd(a, b)} \right) = 1\)
\(y_0 - y = z \frac{a}{\gcd(a, b)}\) for some \(z\)
\(x - x_0 = z \frac{b}{\gcd(a, b)}\) for some \(z\)
Any \(x\) and \(y\) of this form give a solution, so we have found a complete solution set.
THEOREM
Suppose that \(a\) and \(b\) are not both zero, that \(\gcd(a, b) \mid c\), and that \(ax_0 + by_0 = c\). Then every solution of
\(ax + by = c\)
is given by
\(x = x_0 + z \frac{b}{\gcd(a, b)}, y = y_0 + z \frac{a}{\gcd(a, b)}\)
where \(z\) is any integer.
The solutions \(x\) all leave the same remainder on division by \(\frac{b}{\gcd(a, b)}\) and likewise for \(y\) on division by \(\frac{a}{\gcd(a, b)}\).
Lehman’s Method#
Lehman’s method is based on differences of squares and is a small improvement over trial division.
from decimal import *
getcontext().prec = 50
n = 10001
for t in [1,2]:
tn4 = 4*t*n
print(f"(4tn)^(1/2) {str(Decimal(tn4)**(Decimal(1)/Decimal(2)))}")
print(f"(4tn + n^(2/3))^(1/2) {str(Decimal(tn4 + n**(Decimal(2)/Decimal(3)))**(Decimal(1)/Decimal(2)))}")
print()
(4tn)^(1/2) 200.00999975001249921880468339875973944309979013137
(4tn + n^(2/3))^(1/2) 201.16706943923780820782055420590837397530737200471
(4tn)^(1/2) 282.85685425670702668230465161705172548037581530420
(4tn + n^(2/3))^(1/2) 283.67620595808018197598741952851738922420698676761
Dirichlet’s Theorem#
Proof of Lehman’s Method#
Misc Proofs#
Finding last \(n\) digits of large integer#
The last \(n\) digits of a large base-10 integer \(N\) is
\(\equiv N \textbf{ mod } 10^n\)
What are the last two digits of \(3^{431}\)?
\(3^{\phi(10^2)} = 3^{\phi(2^2)\phi(5^2)} = 3^{40} \equiv 1 \mod 10^2\)
\(3^{431} = (3^{40})^{10} \times 3^{31} \equiv 3^{31} \mod 10^2\)
\(3^{15} \equiv 7 \mod 10^2\)
\(3^{31} = (3^{15})^2 \times 3 \equiv \underbrace{7^2 \times 3}_{147} \equiv \boxed{47} \mod 10^2\)
What are the last three digits of \(3^{431}\)?
\( \begin{aligned} \phi(10^3) &= \phi(2^3)\phi(5^3) && \text{since } \gcd(2^3, 5^3) = 1 \\ &= \underbrace{(2^3 - 2^2)}_{4} \underbrace{(5^3 - 5^2)}_{100} \\ &= 400 \\ 3^{\phi(10^3)} &= 3^{400} \equiv 1 \mod 10^3 \\ 3^{341} &= 3^{400} \times 3^{31} \equiv 3^{31} \mod 10^3 \\ 3^{10} &\equiv 7^2 \mod 10^3 \\ 3^{31} &= (3^{10})^3 \times 3 \equiv 7^6 \times 3 \mod 10^3 \\ 7^6 &\equiv 649 \mod 10^3 \\ 7^6 \times 3 &\equiv \underbrace{649 \times 3}_{1947} \equiv \boxed{947} \mod 10^3 \end {aligned} \)
What are the last four digits of \(3^{431}\)?
\( \begin{aligned} 3^{431} = 3^{400} \times 3^{31} = (3^4)^{2^2 5^2} \times 3^{31} \equiv a \times b \mod 10^4 = 2^4 \times 5^4 \end {aligned} \)
\( \begin{aligned} 3^4 \equiv 1 \mod 2^4 \\ 3^{400} = (3^4)^{2^2 5^2} \equiv 1 \mod 2^4 \\ 3^{431} \equiv 3^{31} \equiv 11 \mod 2^4 \end {aligned} \)
print(f'{len(str(3**431))}')
print(f'{3** 4%10}')
print(f'{3** 40%100}')
print(f'{3** 400%1000}')
print(f'{3**4000%10000}')
print(f'{3**431%10}')
print(f'{3**431%100}')
print(f'{3**431%1000}')
print(f'{3**431%10000}')
206
1
1
1
1
7
47
947
9947
Divisor Function#
Claim
Let \(d(n)\) be the number of divisors of the integer \(n\) with prime factorization \(p^a q^b r^c \dots\)
Then \(d(n) = (a + 1)(b + 1)(c + 1) \dots\)
How many divisors does a perfect square have? An odd number since the exponents in their prime factorizations are all even.
\( \begin{aligned} 4 &= 2^2 &&& 3 &&& 2^0 \times 2^2, 2^1 \times 2^1 \\ 9 &= 3^2 &&& 3 &&& 3^0 \times 3^2, 3^1 \times 3^1 \\ 16 &= 2^4 &&& 5 &&& 2^0 \times 2^4, 2^1 \times 2^3, 2^2 \times 2^2 \\ 25 &= 5^2 &&& 3 &&& 5^0 \times 5^2, 5^1 \times 5^1 \\ 36 &= 2^2 3^2 &&& 9 &&& 2^0 3^0 \times 2^2 3^2, 2^1 3^0 \times 2^1 3^2, 2^0 3^1 \times 2^2 3^1, 2^2 3^0 \times 2^0 3^2, 2^1 3^1 \times 2^1 3^1 \\ 49 &= 7^2 &&& 3 &&& 7^0 \times 7^2, 7^1 \times 7^1 \\ 64 &= 2^6 &&& 7 &&& 1, 2, 4, 8, 16, 32, 64 \\ 81 &= 3^4 &&& 5 &&& 1, 3, 9, 27, 81 \\ 100 &= 2^2 5^2 &&& 9 &&& 1, 2, 4, 5, 10, 20, 25, 50, 100 \\ 121 &= 11^2 &&& 3 &&& 1, 11, 121 \\ 144 &= 2^4 3^2 &&& 15 &&& 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144 \\ 169 &= 13^2 &&& 3 &&& 1, 13, 169 \\ 196 &= 2^2 7^2 &&& 9 &&& \\ 225 &= 3^2 5^2 &&& 9 &&& \\ 256 &= 2^8 &&& 9 &&& \\ 289 &= 17^2 &&& 3 &&& 1, 17, 189 \\ 324 &= 2^2 3^4 &&& 15 &&& \\ 361 &= 19^2 &&& 3 &&& 1, 19, 361 \\ 400 &= 2^4 5^2 &&& 15 &&& \\ 441 &= 3^2 7^2 &&& 9 &&& \\ 484 &= 2^2 11^2 &&& 9 &&& \\ 529 &= 23^2 &&& 3 &&& 1, 23, 529 \\ 576 &= 2^6 3^2 &&& 21 &&& \\ 625 &= 5^4 &&& 5 &&& 1, 5, 25, 125, 625 \\ 676 &= 2^2 13^2 &&& 9 &&& \\ 729 &= 3^6 &&& 7 &&& \\ 784 &= 2^4 7^2 &&& 15 &&& \\ 841 &= 29^2 &&& 3 &&& 1, 29, 841 \\ 900 &= 2^2 3^2 5^2 &&& 27 &&& \\ 961 &= 31^2 &&& 3 &&& 1, 31, 961 \\ 1024 &= 2^{10} &&& 11 &&& \\ \end {aligned} \)
Resources#
Acknowledgements#
SDCP 2006 Dasgupta, Sanjoy; Christos Papadimitriou; & Umesh Vazirani. Algorithms. McGraw-Hill.
KRDM 2018 Rosen, Kenneth. Discrete Mathematics and its Applications 8e. McGraw-Hill.
CENT 2023 [ h ] Vaughan, Robert. A Course of Elementary Number Theory. CMPSC/MATH 467 Factorization and Primality Testing. The Pennsylvania State University. [ book ]