Divisibility#
Divisor and multiple#
\(Definition\)
Let \(a\) and \(b\) be integers.
It is said that \(a\) divides \(b\) if there is an integer \(k\) s.t. \(ak = b\).
In this case, we also say that \(a\) is a divisor of \(b\) or that \(b\) is a multiple of \(a\).
Otherwise, \(a\) does not divide \(b\).
One divides every integer#
\(Claim\)
One divides every integer.
\(Proof\)
Let \(a\) be an integer and let \(1\) divide \(a\).
Then there is an integer \(k = a\) s.t. \(1 \cdot k = 1 \cdot a = a\).
\(1 \cdot a = a\) for any integer \(a\).
\(\therefore 1 \mid a\) for any integer \(a\).
\(\blacksquare\)
Every integer divides zero#
\(Claim\)
Every integer divides zero.
\(Proof\)
Let \(a\) be an integer and let \(a\) divide \(0\).
Then there is an integer \(k = 0\) s.t. \(ak = a \cdot 0 = 0\).
\(a \cdot 0 = 0\) for any integer \(a\).
\(\therefore a \mid 0\) for any integer \(a\).
\(\blacksquare\)
Does this hold for \(a = 0\)?
Zero does not divide any integer#
\(Claim\)
Zero does not divide any integer.
\(Proof \,\, by \,\, contradiction\)
Let \(a\) be an integer and let \(0 \mid a\).
Case \(a \ne 0\)Then there is an integer \(k\) s.t. \(0 \cdot k = a\).
\(0 \cdot k = a \implies a = 0\).
But we said that \(a \ne 0\). \(Contradiction!\)
\(\therefore 0 \nmid a\).Case \(a = 0\)
Then there is an integer \(k\) s.t. \(0 \cdot k = 0\).
\(0 \cdot k = 0\) for any integer \(k\) \(\iff \frac{0}{0} = k\) for any integer \(k\).
Let’s say that \(k = 1\).
\(1 = \frac{0}{0} = \frac{0 + 0}{0} = \frac{0}{0} + \frac{0}{0} = 1 + 1 = 2\).
But \(1 \ne 2\). \(Contradiction!\)
\(\blacksquare\)
Every integer divides itself#
[ 1.i ]
\(Claim\)
Any integer divides itself.
\(Proof\)
For any integer \(a\) there is an integer \(k = 1\) such that \(ak = a\).
\(\blacksquare\)
Does this hold for \(a = 0\)?
If two integers divide each other then they are equal up to parity#
[ 1.ii ]
\(Claim\)
If \(a \mid b\) and \(b \mid a\), then \(a = \pm b\).
\(Proof\)
Let \(a \mid b\) and \(b \mid a\).
Then there are integers \(k\) and \(m\) such that \(ak = b\) and \(bm = a\).
\(ak = b \implies a = \frac{b}{k} \implies bm = \frac{b}{k} \implies mk = 1 \implies m = k = \pm 1 \implies a = \pm b\).
\(\therefore a = \pm b\)
\(\blacksquare\)
Does “up to parity” make sense here?
Transitivity of division#
[ 1.iii ]
\(Claim\)
If \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
\(Proof\)
Let \(a \mid b\) and \(b \mid c\).
Then there are integers \(k\) and \(m\) such that \(ak = b\) and \(bm = c\).
\(ak = b \implies (ak)m = c \implies a(km) = c\).
\(\therefore a \mid c\)
\(\blacksquare\)
\(Further\)
If an integer multiple of one integer divides that integer multiple of another integer then the first integer divides the second#
[ 1.iv ]
\(Claim\)
If \(ac \mid bc\) and \(c \ne 0\), then \(a \mid b\).
\(Proof\)
Let \(ac \mid bc\) and \(c \ne 0\).
Then there is an integer \(k\) such that \(ack = bc\).
\(ack = bc \implies ak = b\).
\(\therefore a \mid b\)
\(\blacksquare\)
If one integer divides another then an integer multiple of the first divides that integer multiple of the second#
[ 1.v ]
\(Claim\)
If \(a \mid b\), then \(ac \mid bc\).
\(Proof\)
Let \(a \mid b\).
Then there is an integer \(k\) such that \(ak = b\).
\(ak = b \implies ack = bc\).
\(\therefore ac \mid bc\)
\(\blacksquare\)
If one integer divides another integer then the first integer divides all integer multiples of the second#
\(Claim\)
If \(a \mid b\), then \(a \mid bc\) for all \(c \in \mathbb{Z}\).
\(Proof\)
Let \(a \mid b\).
Then there is an integer \(k\) such that \(ak = b\).
\(ak = b \implies a(ck) = bc\).
\(\therefore a \mid bc\)
\(\blacksquare\)
If an integer divides some set of other integers then it also divides an integral linear combination of those other integers#
[ 1.vi ]
\(Claim\)
If \(a \mid b \land a \mid c\), then \(a \mid bx + cy\) for all \(x, y \in \mathbb{Z}\).
\(Proof\)
Let \(a \mid b\) and \(a \mid c\).
Then there are integers \(k\) and \(m\) such that \(ak = b\) and \(am = c\).
\(b + c = ak + am = a(k + m)\)
\(a \mid a(k + m) \implies a \mid b + c\)
\(bx + cy = akx + amy = a(kx + my)\)
\(a \mid a(kx + my) \implies a \mid bx + cy\)
\(\therefore a \mid bx + cy\)
\(\blacksquare\)
\(Further\)
If one integer divides another then the absolute value of the first is no larger than the second#
\(Claim\)
If \(a\) divides \(b\), then \(|a|\) is no larger than \(|b|\).
\(Proof\)
Let \(a \mid b\).
Then there is an integer \(k\) such that \(ak = b\).
\(ak = b \implies |ak| = |b| \implies |a||k| = |b| \implies 1 \le |k| \implies |a| \le |a||k|\).
\(\therefore |a| \le |b|\)
\(\blacksquare\)
If a nonnegative integer divides adjacent terms in the Fibonacci sequence then the integer must be unity#
\( F := \begin{cases} F_1 &= 1 \\ F_2 &= 1 \\ F_{n + 1} &= F_n + F_{n - 1} && n \in \{ 2, 3, \dots \} \\ \end{cases} \)
\(Claim\)
Let \(m\) be a nonnegative integer.
If \(m\) divides both \(F_n\) and \(F_{n + 1}\), then \(m = 1\).
\(Proof\)
\(n = 2\)
Let \(m \mid F_2\) and \(m \mid F_3\).
Then \(ms = 1\) and \(mt = 2\)
\(ms = 1 \implies m = 1\)Let \(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}\).
\(mt = F_{n + 1} = F_n + F_{n - 1} = ms + F_{n - 1} \implies m(t - s) = F_{n - 1}\)
\(\therefore m \mid F_{n - 1}\)\(\therefore m = 1\)
\(\blacksquare\)
If an integer is odd then eight divides one less than its square#
[ 3 ]
\(Claim\)
If \(n\) is odd then \(8 \mid n^2 - 1\).
\(Proof\)
Let \(n\) be odd.
Then \(n\) is an integer of the form \(2k + 1\) for some integer \(k\).
\(n = 2k + 1 \implies n^2 = (2k + 1)^2 = 4k(k + 1) + 1 \implies n^2 - 1 = 4k(k + 1)\).
Then one of \(k\) and \(k + 1\) is even and the other is odd and so \(k(k + 1)\) is even.
Then \(k(k + 1)\) is an integer of the form \(2m\) for some integer \(m\).
\(k(k + 1) = 2m \implies n^2 - 1 = 4(2m) \implies n^2 - 1 = 8m \implies 8 \mid n^2 - 1\).
\(\therefore 8 \mid n^2 - 1\)
\(\blacksquare\)
Find all integral solutions to \(x^2 - y^2 = 105\)#
[ 4 ]
Let \(x\) and \(y\) be integers. Find all solutions to the equation \(x^2 - y^2 = 105\).
\(x^2 - y^2 = (x - y)(x + y) = 3 \cdot 5 \cdot 7 = 105\)
\(x - y = 1 \implies x + y = 3 \cdot 5 \cdot 7\)
\(x = y + 1 \implies y = \frac{3 \cdot 5 \cdot 7 - 1}{2} = 52 \implies x = 53\)
\((53 - 52)(53 + 52) = 1 \cdot 105\)\(x - y = 3 \implies x + y = 5 \cdot 7\)
\(x = y + 3 \implies y = \frac{5 \cdot 7 - 3}{2} = 16 \implies x = 19\)
\((19 - 16)(16 + 19) = 3 \cdot 35\)\(x - y = 5 \implies x + y = 3 \cdot 7\)
\(x = y + 5 \implies y = \frac{3 \cdot 7 - 5}{2} = 8 \implies x = 13\)
\((13 - 8)(13 + 8) \implies 5 \cdot 21\)\(x - y = 7 \implies x + y = 3 \cdot 5\)
\(x = y + 7 \implies y = \frac{3 \cdot 5 - 7}{2} = 4 \implies x = 11\)
\((11 - 4)(11 + 4) \implies 7 \cdot 15\)\((1, 105)\)
\((-1, 105)\)
\((1, -105)\)
\((-1, -105)\)
\((3, 35)\)
\((-3, 35)\)
\((3, -35)\)
\((-3, -35)\)
\((5, 21)\)
\((-5, 21)\)
\((5, -21)\)
\((-5, -21)\)
\((7, 15)\)
\((-7, 15)\)
\((7, -15)\)
\((-7, -15)\)
If two integers are odd then so is their product#
[ 5.i ]
\(Claim\)
If \(m\) and \(n\) are integers of the form \(4k + 1\) then so is \(mn\).
\(Proof\)
Let \(m\) be an integer of the form \(4s + 1\) for some integer \(s\) and let \(n\) be an integer of the form \(4t + 1\) for some integer \(t\).
\(mn = (4s + 1)(4t + 1) = 4^2st + 4s + 4t + 1 = 4(4st + s + t) + 1 = 4\ell + 1\) where \(\ell = 4st + s + t\).
\(\therefore \exists \ell \in \mathbb{Z} \,\, (mn = 4\ell + 1)\)
\(\blacksquare\)
[ 5.ii ]
\(Claim\)
Let \(m\) and \(n\) be nonnegative integers.
If \(mn\) is of the form \(4k - 1\) then so is one of \(m\) and \(n\).
\(Proof\)
Let \(mn = 4k - 1\) for some integer \(k\).
\(mn = 4k - 1 = 4(4st + s - t) - 1 = 4^2st + 4s - 4t - 1 = (4s - 1)(4t + 1)\) for some integers \(s\) and \(t\).
\(\blacksquare\)
\(Proof \,\, by \,\, contraposition\)
Let \(m\) be an even integer (of the form \(2s\) for some integer \(s\)) and let \(n\) be an even integer (of the form \(2t\) for some integer \(t\)).
Then \(mn = (2s)(2t) = 4(st) = 4k\) where \(k = st\).
\(\therefore\) one of \(m\) or \(n\) must be odd.
\(\blacksquare\)
[ 5.iii ]
\(Claim\)
Every number of the form \(4k - 1\) has a prime factor of this form.
[ 5.iv ]
\(Claim\)
There are infinitely many primes of the form \(4k - 1\).
Irrationality of \(\sqrt{2}\)#
[Theorem 1.2]
The square root of \(2\) cannot be expressed as a ratio of two integers.
\( \begin{aligned} & \forall a \forall b \left( \frac{a}{b} \ne \sqrt{2} \right) && \text{The square root of 2 cannot be expressed by any two integers a and b.} \\ \iff & \forall a \lnot \exists b \left( \frac{a}{b} = \sqrt{2} \right) && \text{For any integer a there is no integer b such that their ratio is the square root of 2.} \\ \iff & \lnot \exists a \exists b \left( \frac{a}{b} = \sqrt{2} \right) && \text{It is not the case that there are two integers a and b whose quotient is the square root of 2.} \\ \end{aligned} \)
\(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 && \text{Theorem 1.1} \\ 2 &\mid m && \text{modus ponens} \\ 2 \mid m^2 &\rightarrow 4 \mid m^2 && \text{Theorem 1.1} \\ 4 &\mid m^2 && \text{modus ponens} \\ 4 &\mid 2n^2 \\ 2 &\mid n^2 \\ 2 \mid n^2 &\rightarrow 2 \mid n && \text{Theorem 1.1} \\ 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} \\ \blacksquare \end{aligned} \)