Division#
Contents#
Summary of important results#
Division
\(a \mid b\) means there is an integer \(c\) such that \(ac = b\)
\(\pm a \mid a \quad\quad \forall a \in \mathbb{Z} \land a \ne 0\)
\(a \mid 0 \quad\quad \forall a \in \mathbb{Z} \land a \ne 0\)
\(\pm 1 \mid a \quad\quad \forall a \in \mathbb{Z}\)
\(a \mid b \land b \mid a \implies a = \pm b\)
Parity
\( \begin{aligned} \text{even} &\pm \text{even} &&= \text{even} \\ \text{odd} &\pm \text{odd} &&= \text{even} \\ \text{even} &\pm \text{odd} &&= \text{odd} \\ \text{even} &\times \text{even} &&= \text{even} \\ \text{even} &\times \text{odd} &&= \text{even} \\ \text{odd} &\times \text{odd} &&= \text{odd} \\ \end {aligned} \)
\( \begin{aligned} & \gcd(a, b) \mid a \\ & \gcd(a, b) \mid b \\ & c \mid a \land c \mid b \implies c \mid \gcd(a, b) \\ & \gcd \left( \frac{a}{\gcd(a, b)}, \frac{b}{\gcd(a, b)} \right) = 1 \\ & \gcd(a + by, b) = \gcd(a, b) \\ \end {aligned} \)
\(\gcd(a, b) = p_1^{\min(r_1, s_1)} \dots p_k^{\min(r_k, s_k)}\)
\( \text{lcm}[a, b] = \frac{ab}{\gcd(a, b)} = p_1^{\max(r_1, s_1)} \dots p_k^{\max(r_k, s_k)} \)
Division#
DIVISION
Let \(a\) and \(b\) be integers with \(a \ne 0\). We say that \(a\) divides \(b\) when there is an integer \(c\) such that \(ac = b\) (or equivalently if \(b/a\) is an integer) and we write \(a \mid b\).
We say that \(a\) is a divisor of \(b\) and that \(b\) is a multiple of \(a\).
\(a \mid b\) can be expressed as \(\exists c (ac = b)\) where the universe of discourse is the set of integers.
\(\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.
Example
List the divisors \(d\) of \(1\).
\( \begin{aligned} d \mid 1 && d & \times \phantom{-}k \\ \hline -1 \mid 1 && -1 & \times -1 \\ 1 \mid 1 && 1 & \times \phantom{-}1 \\ \end {aligned} \)
Example
List the divisors \(d\) of \(6\).
\( \begin{aligned} d \mid 6 && d & \times \phantom{-}k \\ \hline -6 \mid 6 && -6 & \times -1 \\ -3 \mid 6 && -3 & \times -2 \\ -2 \mid 6 && -2 & \times -3 \\ -1 \mid 6 && -1 & \times -6 \\ 1 \mid 6 && 1 & \times \phantom{-}6 \\ 2 \mid 6 && 2 & \times \phantom{-}3 \\ 3 \mid 6 && 3 & \times \phantom{-}2 \\ 6 \mid 6 && 6 & \times \phantom{-}1 \\ \end {aligned} \)
Claim
\(\pm1\) divide every integer.
Proof
Let \(a\) be any integer.
Suppose \(\phantom{-}1 \mid a\). Then there is an integer \(k\) such that \(\phantom{-}1 \times k = a\), namely \(\phantom{-}a\) itself.
Suppose \(-1 \mid a\). Then there is an integer \(k\) such that \(-1 \times k = a\), namely \(-a\).
\(\blacksquare\)
Claim
Every nonzero integer \(a\) and its negation \(-a\) divides itself.
Proof
Let \(a\) be a nonzero integer.
Suppose \(\phantom{-}a \mid a\). Then there is an integer \(k\) such that \(\phantom{-}ak = a\), namely \(\phantom{-}1\).
Suppose \(-a \mid a\). Then there is an integer \(k\) such that \(-ak = a\), namely \(-1\).
\(\blacksquare\)
Claim
Every nonzero integer divides zero.
Proof
Suppose \(a\) is a nonzero integer and \(a \mid 0\). Then there is an integer \(k\) such that \(ak = 0\), namely \(0\) itself.
\(\blacksquare\)
Claim
\(0a = 0\) for any \(a\).
Claim
Zero does not divide any integer.
Zero division is undefined.
Does it make sense to give a proof like the following?
Proof
Suppose \(0 \mid a\) with \(a \ne 0\). Then there exists an integer \(k\) such that \(0k = a\). This equation requires \(a\) be \(0\).
Suppose \(0 \mid a\) with \(a = 0\). Then there exists an integer \(k\) such that \(0k = 0\). This equation is true for any integer \(k\).
Suppose \(k = 1\). Then \(k = 1 = \frac{0}{0} = \frac{0 + 0}{0} = \frac{0}{0} + \frac{0}{0} = 1 + 1 = 2\)
\(\blacksquare\)
Claim
Let \(a\) and \(b\) be nonzero integers. If \(a \mid b\) and \(b \mid a\) then \(a = \pm b\).
“If two integers divide each other then they are equal up to parity.”
Proof
Suppose \(a \mid b\) and \(b \mid a\). Then there exist integers \(m\) and \(n\) such that \(b = am\) and
\(a = bn = (am)n = a(mn) \implies 1 = mn \implies m = n = \pm 1\)
Suppose \(m = n = \phantom{-}1\). Then \(a = \phantom{-}b\).
Suppose \(m = n = -1\). Then \(a = -b\).
\(\blacksquare\)
Claim
If \(ab = 1\) then \(a = b = \pm 1\).
Claim
Let \(a\), \(b\), and \(c\) be integers with \(c \ne 0\).
\(ac \mid bc\) iff \(a \mid b\).
Proof
Suppose \(ac \mid bc\). Then there is an integer \(k\) such that \(ack = bc \implies ak = b \implies a \mid b\).
Suppose \(a \mid b\). Then there is an integer \(k\) such that \(ak = b \implies ack = bc \implies ac \mid bc\).
\(\blacksquare\)
Claim
Let \(a\), \(b\), and \(c\) be integers.
If \(a \mid b\) then \(a \mid bc\).
Proof
Suppose \(a \mid b\). Then there is an integer \(k\) such that \(ak = b \implies a(ck) = bc \implies a \mid bc\).
\(\blacksquare\)
Claim
If \(ac = ad\) with \(a \ne 0\) then \(c = d\).
Claim
Let \(a\), \(b\), and \(c\) be integers. If \(a \mid b\) and \(b \mid c\) then \(a \mid c\).
Proof
Suppose \(a \mid b\) and \(b \mid c\). Then there are integers \(d\) and \(e\) such that \(b = ad\) and
\(c = be = (ad)e = a(de)\)
\(\blacksquare\)
Let \(a_1, a_2, \dotsc, a_n\) be integers. If \(a_1 \mid a_2, a_2 \mid a_3, \dotsc, a_{n - 1} \mid a_n\) then \(a_1 \mid a_n\).
Claim
Let \(a\), \(b\), \(c\), \(x\), \(y\) be integers with \(a \ne 0\).
If \(a \mid b\) and \(a \mid c\) then \(a \mid (bx + cy)\).
Proof
Suppose \(a \mid b\) and \(a \mid c\). Then there are integers \(m\) and \(n\) such that \(am = b\) and \(an = c\).
\( \begin{aligned} b + c &= am + an = a(m + n) &&\implies a \mid (b + c) \\ bx + cy &= amx + any = a(mx + ny) &&\implies a \mid (bx + cy) \\ \end {aligned} \)
\(\blacksquare\)
\(\forall a, b_i \in \mathbb{Z} \,\, , \,\, i \in \{ 1, \dots, n \} \,\, [ \,\, (a \mid b_1 \land \dots \land a \mid b_n) \implies a \mid \sum_{j = 1}^n b_jx_j \,\, ]\)
Claim
Let \(a\) and \(b\) be nonzero integers.
If \(a \mid b\) then \(|a| \le |b|\).
Proof
Suppose \(a \mid b\). Then there is an integer \(k\) such that \(ak = b\).
\(ak = b \implies |ak| = |b| = |a||k| = |b|\)
Since \(b\) is nonzero this excludes the possibility that \(|k| = 0\). Thus
\(1 \le |k| \implies |a| \le |a||k| = |b|\)
\(\blacksquare\)
Claim
The Fibonacci sequence is defined as follows.
\( F := \begin{cases} F_1 &= 1 \\ F_2 &= 1 \\ F_{n + 1} &= F_n + F_{n - 1} && n \in \{ 2, 3, \dots \} \\ \end{cases} \)
If \(m\) divides both \(F_n\) and \(F_{n + 1}\) then \(m = 1\).
Proof by induction
Suppose \(m \mid F_2\) and \(m \mid F_3\). Then there are integers \(s\) and \(t\) such that \(ms = F_2 = 1\) and \(mt = F_3 = 2\)
\(ms = 1 \implies m = 1\)
Suppose \(m \mid F_n\) and \(m \mid F_{n + 1}\). Then there are integers \(s\) and \(t\) such that \(ms = F_n\) and
\(mt = F_{n + 1} = F_n + F_{n - 1} = ms + F_{n - 1} \implies F_{n - 1} = mt - ms = m(t - s)\)
\(m \mid F_{n - 1} \implies m = 1\)
\(\blacksquare\)
Claim
If \(n\) is odd then \(8 \mid (n^2 - 1)\).
Proof
Suppose \(n\) is odd so that \(n = 2k + 1\) for some integer \(k\).
\( \begin{aligned} n &= 2k + 1 \\ n^2 &= (2k + 1)^2 = 4k^2 + 4k + 1 \\ n^2 - 1 &= 4k^2 + 4k = 4k(k + 1) = (n - 1)(n + 1) \end {aligned} \)
\(k\) is either even or odd. This is to say that one of \(k\) and \(k + 1\) is even and the other is odd and so their product is even so that \(k(k + 1) = 2m\) for some integer \(m\).
\(n^2 - 1 = 4k(k + 1) = 4(2m) = 8m\)
The other way to see this is that since \(n\) is odd both \(n - 1\) and \(n + 1\) are even so that \(n - 1 = 2s\) and \(n + 1 = 2s + 2\) for some integer \(s\) and so
\((n - 1)(n + 1) = 2s(2s + 2) = 4s^2 + 4s = 4s(s + 1)\)
\(\blacksquare\)
Proof by induction on \(n\)
Base Case \(n = 1\)
\(8 \mid 0\)
Inductive Case
Suppose it is the case that \(8 \mid (n^2 - 1)\). It must be shown that it holds for the next odd number \(n + 2\).
\((n + 2)^2 - 1 = n^2 + 4n + 4 - 1 = n^2 - 1 + 4(n + 1)\)
We know that \(8 \mid (n^2 - 1)\) so we only need to check that \(8 \mid 4(n + 1)\).
Since \(n\) is odd \(n + 1\) is even so that \(n + 1 = 2k\) for some integer \(k\).
Thus \(8 \mid 4(n + 1) = 4(2k) = 8k\).
\(\blacksquare\)
Alternative
\(n = 2k - 1\)
\(n^2 - 1 = (2k - 1)^2 - 1 = 4k^2 - 4k = 4k(k - 1)\)
If \(k\) is even then \(8 \mid 4k\)
If \(k\) is odd then \(k - 1\) is even and \(8 \mid 4(k - 1)\)
Example
\( \begin{aligned} n && n^2 - 1 \\ 1 && 0 = 8 & \times \phantom{1}0 \\ 3 && 8 = 8 & \times \phantom{1}1 \\ 5 && 24 = 8 & \times \phantom{1}3 \\ 7 && 48 = 8 & \times \phantom{1}6 \\ 9 && 80 = 8 & \times 10 \\ 11 && 120 = 8 & \times 15 \\ \end {aligned} \)
Claim
If \(m\) and \(n\) are integers of the form \(4k + 1\) then so is \(mn\).
Proof
Suppose \(m = 4s + 1\) and \(n = 4t + 1\) for some integers \(s\) and \(t\).
\(mn = (4s + 1)(4t + 1) = 16st + 4s + 4t + 1 = 4(4st + s + t) + 1\)
\(\blacksquare\)
Example
\( \begin{aligned} m && n & && & mn \\ 1 &= 0 \times 4 + 1 && & 1 = 0 \times 4 + 1 && & 1 = && 0 \times 4 + 1 \\ 1 &= 0 \times 4 + 1 && & 5 = 1 \times 4 + 1 && & 5 = && 1 \times 4 + 1 \\ 1 &= 0 \times 4 + 1 && & 9 = 2 \times 4 + 1 && & 9 = && 2 \times 4 + 1 \\ \vdots \\ 5 &= 1 \times 4 + 1 && & 5 = 1 \times 4 + 1 && & 25 = && 6 \times 4 + 1 \\ 5 &= 1 \times 4 + 1 && & 9 = 2 \times 4 + 1 && & 45 = && 11 \times 4 + 1 \\ 5 &= 1 \times 4 + 1 && &13 = 3 \times 4 + 1 && & 65 = && 16 \times 4 + 1 \\ 5 &= 1 \times 4 + 1 && &17 = 4 \times 4 + 1 && & 85 = && 21 \times 4 + 1 \\ \vdots \\ 9 &= 2 \times 4 + 1 && & 9 = 2 \times 4 + 1 && & 81 = && 20 \times 4 + 1 \\ \end {aligned} \)
Claim
If \(mn\) is of the form \(4k - 1\) then so is one of \(m\) or \(n\).
Proof
\(mn = 4k - 1\) is odd and so \(m\) and \(n\) are odd so that \(m = 2s + 1\) and \(n = 2t + 1\) for some integers \(s\) and \(t\).
\( \begin{aligned} mn = 4k - 1 &= (2s + 1)(2t + 1) \\ &= 4st + 2s + 2t + 1 \\ &= 2(2st + s + t) + 1 \\ 4k &= 2(2st + s + t) + 2 \\ 2k &= (2st + s + t) + 1 \\ 2k - 1 &= 2st + s + t \end {aligned} \)
Thus \(2st + s + t\) is odd.
Suppose either both \(s\) and \(t\) are even or both \(s\) and \(t\) are odd.
\( \begin{aligned} \text{even} &= 2 \times \text{even} \times \text{even} + \text{even} + \text{even} \\ \text{even} &= 2 \times \text{odd} \times \text{odd} + \text{odd} + \text{odd} \\ \end {aligned} \)
Then \(2st + s + t\) is even. But we supposed that \(2st + s + t\) is odd. Contradiction!
Thus one of \(s\) and \(t\) must be even and the other odd, say \(s\), so that \(s = 2u + 1\) for some integer \(u\). Then
\(m = 2s + 1 = 2(2u + 1) + 1 = 4u + 2 + 1 = 4u + 3 = \boxed{4(u + 1) - 1}\)
\(n = 2t + 1 = 2(2v) + 1 = 4v + 1\)
\(\blacksquare\)
Proof
\(m\) and \(n\) must be odd and so are of the form \(4k \pm 1\). If both are of the form \(4k + 1\) then their product cannot be of the form \(4k - 1\).
\(\blacksquare\)
Example
\( \begin{aligned} 4 \times 1 - 1 &= 3 \\ 4 \times 2 - 1 &= 7 \\ 4 \times 3 - 1 &= 11 \\ 4 \times 4 - 1 &= 15 = \boxed{3} \times 5 \\ 4 \times 5 - 1 &= 19 \\ 4 \times 6 - 1 &= 23 \\ 4 \times 7 - 1 &= 27 \\ 4 \times 8 - 1 &= 31 \\ 4 \times 9 - 1 &= 35 = 5 \times \boxed{7} \\ 4 \times 10 - 1 &= 39 = \boxed{3} \times 13 \\ 4 \times 11 - 1 &= 43 \\ 4 \times 12 - 1 &= 47 \\ 4 \times 13 - 1 &= 51 \\ 4 \times 14 - 1 &= 55 = 5 \times \boxed{11} \\ 4 \times 15 - 1 &= 59 \\ 4 \times 16 - 1 &= 63 = \boxed{3^2 \times 7} \\ 4 \times 17 - 1 &= 67 \\ 4 \times 18 - 1 &= 71 \\ 4 \times 19 - 1 &= 75 = \boxed{3} \times 5^2 \\ 4 \times 20 - 1 &= 79 \\ 4 \times 21 - 1 &= 83 \\ 4 \times 22 - 1 &= 87 = \boxed{3} \times 29 \\ 4 \times 23 - 1 &= 91 = \boxed{7} \times 13 \\ 4 \times 24 - 1 &= 95 = 5 \times \boxed{19} \\ 4 \times 25 - 1 &= 99 = \boxed{3^2 \times 11} \\ \vdots \end {aligned} \)
Claim
\(\sqrt{2}\) is irrational.
Proof by contradiction
Let \(\sqrt{2} = \frac{m}{n}\) where \(m\) and \(n\) are integers and the fraction is reduced (i.e., \(m\) and \(n\) have no common divisors larger than \(1\)).
\( \begin{aligned} \sqrt{2} &= \frac{m}{n} && \text{hypothesis} \\ 2 &= \frac{m^2}{n^2} \\ 2n^2 &= m^2 \\ 2 &\mid m^2 \\ 2 \mid m^2 &\rightarrow 2 \mid m \\ 2 &\mid m && \text{modus ponens} \\ 2 \mid m^2 &\rightarrow 4 \mid m^2 \\ 4 &\mid m^2 && \text{modus ponens} \\ 4 &\mid 2n^2 \\ 2 &\mid n^2 \\ 2 \mid n^2 &\rightarrow 2 \mid n \\ 2 &\mid n && \text{modus ponens} \\ 2 \mid m &\land 2 \mid n && \text{contradiction, m and n have no common divisors larger than 1} \\ \end{aligned} \)
\(\blacksquare\)
Parity#
EVEN
An integer \(x\) is even if there is an integer \(k\) such that \(x = 2k\). In other words \(x\) is even if \(2 \mid x\).
ODD
An integer \(x\) is odd if it is not even. In other words \(x = 2k + 1\).
Property
\(\text{even} \pm \text{even} = \text{even}\)
Proof
Suppose \(a\) and \(b\) are even integers. Then there are integers \(m\) and \(n\) such that \(a = 2m\) and \(b = 2n\).
\(a + b = 2m + 2n = 2(m + n)\)
\(\blacksquare\)
Property
\(\text{odd} \pm \text{odd} = \text{even}\)
Proof
Suppose \(a\) and \(b\) are odd integers. Then there are integers \(m\) and \(n\) such that \(a = 2m + 1\) and \(b = 2n + 1\).
\(a + b = 2m + 1 + 2n + 1 = 2(m + n + 1)\)
\(\blacksquare\)
Property
\(\text{even} \pm \text{odd} = \text{odd}\)
Proof
Suppose \(a\) is even and \(b\) is odd. Then there are integers \(m\) and \(n\) such that \(a = 2m\) and \(b = 2n + 1\).
\(a + b = 2m + 2n + 1 = 2(m + n) + 1\)
\(\blacksquare\)
Property
\(\text{even} \times \text{even} = \text{even}\)
Proof
Suppose \(a\) and \(b\) are even. Then there are integers \(m\) and \(n\) such that \(a = 2m\) and \(b = 2n\).
\(ab = 2m \times 2n = 2(2mn)\)
\(\blacksquare\)
Property
\(\text{even} \times \text{odd} = \text{even}\)
Proof
Suppose \(a\) is even and \(b\) is odd. Then there are integers \(m\) and \(n\) such that \(a = 2m\) and \(b = 2n + 1\).
\(ab = 2m(2n + 1) = 4mn + 2m = 2(2mn + m)\)
\(\blacksquare\)
Property
\(\text{odd} \times \text{odd} = \text{odd}\)
Proof
Suppose \(a\) and \(b\) are odd. Then there are integers \(m\) and \(n\) such that \(a = 2m + 1\) and \(b = 2n + 1\).
\(ab = (2m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1\)
\(\blacksquare\)
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} \)
Property
Every odd integer has the form \(4k \pm 1\).
Suppose \(n\) is odd so that \(n = 2k + 1\) for some integer \(k\).
If \(k\) is even then \(k = 2s\) for some integer \(s\) and \(n = 2(2s) + 1 = 4s + 1\).
If \(k\) is odd then \(k = 2t + 1\) for some integer \(t\) and \(n = 2(2t + 1) + 1 = 4t + 3 = 4(t + 1) - 1\).
Thus every odd integer has the form \(4k + 1\) or \(4k - 1\).
\(\blacksquare\)
Example
\( \begin{aligned} &\phantom{=} 4 \times k \pm 1 \\ 1 &= 4 \times 0 + 1 \\ 3 &= 4 \times 1 - 1 = 4 \times 0 + 3 \\ 5 &= 4 \times 1 + 1 \\ 7 &= 4 \times 2 - 1 = 4 \times 1 + 3 \\ 9 &= 4 \times 2 + 1 \\ 11 &= 4 \times 3 - 1 = 4 \times 2 + 3 \\ 13 &= 4 \times 3 + 1 \\ 15 &= 4 \times 4 - 1 = 4 \times 3 + 3 \\ 17 &= 4 \times 4 + 1 \\ \vdots \end {aligned} \)
Claim
An integer is even (odd) iff its square is even (odd).
Proof by contraposition
If \(x\) is even then \(x^2\) is even
Suppose \(x\) is even. Then \(x = 2k \implies x^2 = 2(2k^2)\)
If \(x^2\) is even then \(x\) is even (If \(x\) is odd then \(x^2\) is odd)
Suppose \(x\) is odd. Then \(x = 2k + 1 \implies x^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\)
\(\blacksquare\)
Claim
An integer is even iff one more (or less) than it is odd.
Proof by contraposition
If \(x\) is even then \(x + 1\) is odd
Suppose \(x\) is even. Then \(x = 2k \implies x + 1 = 2k + 1\)
If \(x + 1\) is odd then \(x\) is even (If \(x\) is odd then \(x + 1\) is even)
Suppose \(x\) is odd. Then \(x = 2k + 1 \implies x + 1 = 2k + 2 = 2(k + 1)\)
\(\blacksquare\)
Prime#
PRIME
Let \(p\) be a positive integer with \(p \gt 1\). \(p\) is called prime if it has exactly two (positive) divisors, \(1\) and \(p\).
(Another way to say this is as follows. A member of \(\mathbb{N}\) greater than \(1\) which is only divisible by \(1\) and itself is called a prime number \(p\).)
\(1\) is not a prime because it only has one (positive) divisor, and a prime number has exactly two (positive) divisors.
The units \(\pm 1\) and the primes have no proper divisors.
\(101\) is a prime number.
It must be shown that there are no divisors \(1 \lt d \lt 101\).
If \(d\) is a divisor then there is an integer \(e\) such that \(de = 101\).
Further, one of \(d, e \le \sqrt{101}\)
If both \(d \gt \sqrt{101}\) and \(e \gt \sqrt{101}\) then \(de \gt 101\)
If we can’t find any factors \(\le \sqrt{101}\) then \(101\) is prime
So, we only need to check \(1 \lt d \lt \sqrt{101}\) (up to \(10\))
So, we only need to check primes \(2, 3, 5, 7\)
\(2\) and \(5\) are not divisors
COMPOSITE
A positive integer greater than one that is not prime is called composite.
In particular let \(n\) be a positive integer with \(n \gt 1\). \(n\) is called composite if it can be written \(n = m_1 m_2\) with \(1 \lt m_1 \lt n\) and so \(1 \lt m_2 \lt n\) also.
The primes and composites form a partition of the set of positive integers greater than one.
THEOREM [Vaughan Theorem 1.4]
Every member \(n\) of \(\mathbb{N}^{+}\) (the positive integers) is a product of primes.
Proof by induction on \(n\)
Base Case \(n = 1\)
\(n = 1\) is an empty product of primes.
Inductive Case
Suppose any \(n \le a\) is a product of primes.
If \(n + 1\) is a prime then we are done.
If \(n + 1\) is not prime then it has a proper divisors \(d\) and \(\frac{n + 1}{d}\) with \(1 \lt d, \frac{n + 1}{d} \lt n + 1\).
But then on the inductive hypothesis both \(d\) and \(\frac{n + 1}{d}\) are primes and so \(n + 1\) is a product of primes.
\(\blacksquare\)
Euclid’s Theorem#
EUCLID’S THEOREM [Vaughan Theorem 1.5]
There are infinitely many primes.
To show that there are infinitely many primes, it must be shown that every finite list of primes is missing a prime and so the list of all primes cannot be finite.
Proof by contradiction
Suppose there are only a finite number of primes \(p_1, \dotsc, p_n\) and consider the number one more than their product \(m = p_1 p_2 \dots p_n + 1\).
Clearly \(m \gt 1\) since we already know the first few primes. Thus \(m\) is a product of primes by the fundamental theorem of arithmetic, and in particular there is a prime \(p\) which divides \(m\). \(p\) must be one of \(p_1, \dotsc, p_n\), and so \(p\) also divides \(p_1 p_2 \dots p_n\). Thus
\(p \mid m - p_1 p_2 \dots p_n = 1\). But no prime divides \(1\), so our assumption must have been false.
\(\blacksquare\)
Since \(m\) is greater than \(1\) it has a prime factor \(p\) which can’t be any of \(p_1, p_2, \dotsc, p_n\) since \(m\) has remainder \(1\) when divided by each \(p_i\).
Euclid’s proof tells us that we can always find a prime outside of a finite list of primes \(p_1, p_2, \dotsc, p_n\) by using a prime factor of \(p_1p_2 \dots p_n + 1\), not by using \(p_1p_2 \dots p_n + 1\) itself.
Euler’s Proof
\(S(x) = \sum_{n \le x} \frac{1}{n}\)
\(S(x) \ge \sum_{n \le x} \int_n^{n + 1} \frac{dt}{t} \ge \int_1^x \frac{dt}{t} = \log x\)
\(P(x) = \prod_{p \le x} (1 - 1/p)^{-1}\) where the product is over the primes not exceeding \(x\)
\( \begin{aligned} P(x) &= \prod_{p \le x} (1 - 1/p)^{-1} \\ &= \prod_{p \le x} \left(1 + \frac{1}{p} + \frac{1}{p^2} + \dotsb \right) \ge \sum_{n \le x} \frac{1}{n} = S(x) \ge \log x \end {aligned} \)
Since \(\log x \to \infty\) as \(x \to \infty\) there must be infinitely many primes.
We can be more precise. Take the \(\log\) of both sides of \(P(x) \ge \log x\)
\( \begin{aligned} \log P(x) &\ge \log \log x \\ \log \left( \prod_{p \le x} (1 - 1/p)^{-1} \right) &\ge \log \log x \\ -\sum_{p \le x} \log (1 - 1/p) &\ge \log \log x \\ \sum_{p \le x} \sum_{k = 1}^\infty \frac{1}{kp^k} \end {aligned} \)
Claim
Every number of the form \(4k - 1\) has a prime factor of this form.
Proof
A number of the form \(4k - 1\) is odd and so its prime factors are odd each of the form \(4k \pm 1\). If all prime factors were of the form \(4k + 1\) then so would be their product. Thus at least one must be of the form \(4k - 1\).
\(\blacksquare\)
Claim
There are infinitely many primes of the form \(4k - 1\).
Proof by contradiction
Suppose there are only a finite number of primes \(p_1, \dotsc, p_n\) of the form \(4k - 1\) and consider the number one less than four times their product \(m = 4p_1 p_2 \dots p_n - 1\).
Clearly \(m \gt 1\) since we already know the first few primes of this form. Thus \(m\) has at least one prime factor \(p\) of the form \(4k - 1\) and in particular there is a prime \(p\) which divides \(m\).
\(p\) must be one of \(p_1, \dotsc, p_n\), and so \(p\) also divides \(p_1 p_2 \dots p_n\). Thus
\(p \mid (4p_1 p_2 \dots p_n - m) = 1\). But no prime divides \(1\), so our assumption must have been false.
\(\blacksquare\)
Claim
\(p \mid x \iff p \mid x^k\) for any \(k \gt 0\)
\(p \nmid x \iff p \nmid x^k\) for any \(k \gt 0\)
first direction
\(p \nmid x \implies p \nmid x^k\)
\(p \nmid x \iff x \not\equiv 0 \mod p \implies x^k \not\equiv 0 \mod p \iff p \nmid x^k\)
second direction
\(p \nmid x^k \implies p \nmid x\)
suppose \(p \mid x \iff x \equiv 0 \mod p\) and then \(x^k \equiv 0^k \equiv 0 \mod p \iff p \mid x^k\). Contradiction.
\(\blacksquare\)
Division Algorithm#
Division of an integer by a positive integer produces a quotient and a remainder. (Operating on remainders will form the basis of modular arithmetic.)
THEOREM: DIVISION ALGORITHM
Let \(a\) be an integer and \(d\) a positive integer. Then there are unique integers \(q\) and \(r\) with \(0 \le r \lt d\) s.t.
\(a = dq + r\)
where \(d\) is called the divisor; \(a\) is called the dividend; \(q\) is called the quotient; and \(r\) is called the remainder.
Proof
Let \(D = \{ a - dx \mid x \in \mathbb{Z} \} = \{ a, a \pm d, a \pm 2d, a \pm 3d, \dotsc \}\).
No matter what \(a\) is, \(D\) has at least one non-negative element and so has a least non-negative element \(r\).
If \(a \ge 0\) then \(a \in D\).
If \(a \lt 0\) then \(a - d(a - 1) \gt 0\)
\( \begin{aligned} -1 - d(-1 - 1) = -1 + 2d \\ -2 - d(-2 - 1) = -2 + 3d \\ -3 - d(-3 - 1) = -3 + 4d \\ \end {aligned} \)
Let \(q = x\). Then \(a = dq + r\) where \(0 \le r\).
Suppose \(r \ge d\). Then \(a = dq + r = dq + (d + r - d) = d(q + 1) + (r - d)\) with \(0 \le r - d \lt r\). Contradiction! \(r\) is the least non-negative element of \(D\), not \(r - d\). Therefore, it must be the case that \(r \lt d\).
Uniqueness
Suppose there is a second solution \(a = dq' + r'\) with \(0 \le r' \lt d\).
Then \(0 = a - a = (dq' + r') - (dq + r) = d(q' - q) + (r' - r) \iff d|q' - q| = |r' - r|\).
\(d \le d|q' - q|\) and \(|r' - r| \lt d\)
Contradiction!
\(\blacksquare\)
The integer \(a\) is divisible by the integer \(d\) iff the remainder is \(0\) when \(a\) is divided by \(b\):
\(d \mid a \iff a = dq + 0\)
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
# 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
Given two integers \(a, b\) not both \(0\), define \(D(a, b) = \{ ax + by \mid x, y \in \mathbb{Z} \}\) Then \(D(a, b)\) has positive elements. Let \(\gcd(a, b)\) denote the least positive element. Then \(\gcd(a, b)\) has the following properties.
(i) \(\gcd(a, b) \mid a\)
(ii) \(\gcd(a, b) \mid b\)
(iii) if the integer \(c\) satisfies \(c \mid a\) and \(c \mid b\) then \(c \mid \gcd(a, b)\)
Note that \(\gcd(a, b)\) divides every member of \(D(a, b)\).
Proof
Existence
The following demonstrates that no matter which values we choose for \(a\) and \(b\) there are always values of \(x\) and \(y\) which make their linear combination positive. The case \(a = b = 0\) is excluded by the theorem.
\( \begin{aligned} a & \gt 0 && \implies a \times \phantom{(-}1\phantom{)} && + b \times \phantom{(-}0\phantom{)} = \phantom{-}a && \gt 0 \\ b & \gt 0 && \implies a \times \phantom{(-}0\phantom{)} && + b \times \phantom{(-}1\phantom{)} = \phantom{-}b && \gt 0 \\ a & \lt 0 && \implies a \times (-1) && + b \times \phantom{(-}0\phantom{)} = -a && \gt 0 \\ b & \lt 0 && \implies a \times \phantom{(-}0\phantom{)} && + b \times (-1) = -b && \gt 0 \\ \end {aligned} \)
Thus, the set \(D(a, b)\) has at least one positive element, and so there is a least positive element.
(i) and (ii)
Suppose \(\gcd(a, b) \nmid a\). From the division algorithm we have \(a = \gcd(a, b)q + r\) with \(0 \le r \lt \gcd(a, b)\) and \(\gcd(a, b) \nmid a\) implies \(0 \lt r\).
Why do we need to show the following two statements?
\(r = a - \gcd(a, b)q = a - (ax + by)q = a(1 - xq) + b(-yq)\) for some integers \(x, y\).
\(0 \lt \underbrace{a(1 - xq) + b(-yq)}_{r} \lt \underbrace{ax + by}_{\gcd(a, b)}\)
Contradiction! \(r\) can’t be less than \(\gcd(a, b)\) since \(\gcd(a, b)\) is the least element. Thus, \(\gcd(a, b) \mid a\) and by symmetry \(\gcd(a, b) \mid b\).
(iii)
Suppose there is an integer \(c\) such that \(c \mid a\) and \(c \mid b\). Then \(a = cu\) and \(b = cv\) for some integers \(u, v\).
\(\gcd(a, b) = ax + by = (cu)x + (cv)y = c(ux + vy) \iff c \mid \gcd(a, b)\)
\(\blacksquare\)
Property of GCD
\(\gcd \left( \frac{a}{\gcd(a, b)}, \frac{b}{\gcd(a, b)} \right) = 1\)
If this quantity is denoted \(d\) then the following hold
\(d \mid \frac{a}{\gcd(a, b)} \iff d \cdot \gcd(a, b) \mid a\)
\(d \mid \frac{b}{\gcd(a, b)} \iff d \cdot \gcd(a, b) \mid b\)
Whatever integer divides both of two integers divides their \(\gcd\) and so \(d \cdot \gcd(a, b) \mid \gcd(a, b) \iff d \mid 1 \iff d = 1\)
\(\blacksquare\)
Property of GCD
Suppose \(a\) and \(b\) are not both \(0\). Then for any integer \(y\) we have \(\gcd(a + by, b) = \gcd(a, b)\).
Proof
Since \(\gcd(a, b) \mid a\) and \(\gcd(a, b) \mid b\) we know that \(\gcd(a, b) \mid ax + by\) for any integers \(x, y\). Thus \(\gcd(a, b) \mid a + by\).
Since \(\gcd(a, b) \mid a + by\) and \(\gcd(a, b) \mid b\) we know that \(\gcd(a, b) \mid \gcd(a + by, b)\).
Since \(\gcd(a + by, b) \mid a + by\) and \(\gcd(a + by, b) \mid b\) we know that \(\gcd(a + by, b) \mid (a + by)s + bt\) for any integers \(s, t\). Thus \(\gcd(a + by, b) \mid a + by - by = a\).
Since \(\gcd(a + by, b) \mid a\) and \(\gcd(a + by, b) \mid b\) we know that \(\gcd(a + by, b) \mid \gcd(a, b)\).
Since \(\gcd(a, b) \mid \gcd(a + by, b)\) and \(\gcd(a + by, b) \mid \gcd(a, b)\) it is the case that \(\gcd(a, b) = \gcd(a + by, b)\).
\(\blacksquare\)
Example
\(\gcd(21, 49) = \gcd(21 + 49(3), 49)\)
Property of GCD
Suppose that \(\gcd(a, b) = 1\) and that \(ax = by\). Then there is a \(z\) such that \(x = bz\) and \(y = az\).
Proof
There are integers \(u, v\) such that
\(\gcd(a, b) = 1 = ua + vb \iff x = uax + vbx \iff x = u(by) + vbx = b\underbrace{(uy + vx)}_{z} \iff b \mid x\)
\(\gcd(a, b) = 1 = ua + vb \iff y = uay + vby \iff y = uay + v(ax) = a\underbrace{(uy + vx)}_{z} \iff a \mid y\)
\(\blacksquare\)
Example
\( \begin{aligned} \gcd(a, b) &= 1 &&& a \times x &= b \times y &&& x &= b \times z &&& y &= a \times z \\ \gcd(2, 3) &= 1 &&& 2 \times 3 &= 3 \times 2 &&& 3 &= 3 \times 1 &&& 2 &= 2 \times 1 \\ \gcd(3, 5) &= 1 &&& 3 \times 10 &= 5 \times 6 &&& 10 &= 5 \times 2 &&& 6 &= 3 \times 2 \\ \end {aligned} \)
COROLLARY [Vaughan Corollary 1.14]
Suppose that \(a\) and \(b\) are integers not both \(0\). Then there are integers \(x, y\) such that \(\gcd(a, b) = ax + by\).
Later we will look at a way of finding suitable x and y in examples. As it stands the theorem gives no constructive way of finding them. It is a pure existence proof.
Euclid’s Lemma#
EUCLID’S LEMMA [Vaughan Theorem 1.15]
Suppose that \(p\) is prime and that there are integers \(a\) and \(b\) such that \(p \mid ab\).
Then either \(p \mid a\) or \(p \mid b\) but not both.
Contrapositive: If \(p \nmid a\) and \(p \nmid b\) then \(p \nmid ab\).
\( \begin{aligned} p \mid ab \implies [(p \mid a \lor p \mid b) \land \lnot(p \mid a \land p \mid b)] \\ [ \lnot[(p \mid a \lor p \mid b) \land \lnot(p \mid a \land p \mid b)] ] \implies p \nmid ab \\ [ \lnot(p \mid a \lor p \mid b) \lor (p \mid a \land p \mid b) ] \implies p \nmid ab \\ [ p \nmid a \land p \nmid b \lor (p \mid a \land p \mid b) ] \implies p \nmid ab \\ \end {aligned} \)
Proof
If \(a = 0\) or \(b = 0\) then the result that \(p \mid 0\) is trivial. Thus we may suppose that \(ab \ne 0\).
Suppose \(p \nmid a\).
We know that there are integers \(x\) and \(y\) such that \(\gcd(a, p) = ax + py\) and that \(\gcd(a, p) \mid a\) and \(\gcd(a, p) \mid p\).
Since \(p\) is prime it is the case that either \(\gcd(a, p) = 1\) or \(\gcd(a, p) = p\).
If it were the case that \(\gcd(a, p) = p\) then \(p \mid a\). But we supposed that \(p \nmid a\).
So \(\gcd(a, p) = 1 = ax + py \iff b = abx + pby\).
\(p \mid ab \iff ab = pc\) for some integer \(c\). Then \(b = (pc)x + pby \iff b = p(cx + by) \iff p \mid b\)
\(\blacksquare\)
Example
\( \begin{array}{c|c|c|c} p & ab \\ \hline 3 & \phantom{1}6 = 3 \times 2 \\ \hline 3 & 15 = 3 \times 5 \\ \hline \end {array} \)
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.
Euclid’s Lemma can be used to establish the following.
THEOREM [Vaughan Theorem 1.17]
Suppose that
\(p, p_1, p_2, \dotsc, p_r\)
are primes and that
\(p \mid p_1 p_2 \dots p_r\)
Then \(p = p_j\) for some \(j\) with \(1 \le j \le r\).
Proof by induction on \(r\)
Base Case \(r = 1\)
\(p \mid p_1 \implies p = p_1\)
Inductive Case
Suppose the \(r\)-th case is established and that \(p \mid p_1 p_2 \dots p_r p_{r + 1}\).
Then either \(p \mid p_{r + 1}\) or \(p \mid p_1 p_2 \dots p_r\).
If \(p \mid p_{r + 1}\) then \(p = p_{r + 1}\). Otherwise it has been established that if \(p \mid p_1 p_2 \dots p_r\) then \(p = p_j\) for some \(j\) with \(1 \le j \le r\).
\(\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\).
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} \)
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} \)
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} \)
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\).
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.
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_1 - m_2}{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} \)
Acknowledgements#
2006 Dasgupta, Sanjoy; Christos Papadimitriou; & Umesh Vazirani. Algorithms. Chapter 1. McGraw-Hill.
2018 Rosen, Kenneth. Discrete Mathematics and its Applications 8e. McGraw-Hill.
2023 Vaughan, Robert. A Course of Elementary Number Theory.