Exercises#
Contents#
1#
1
Let \(n\) and \(m\) be integers with \(0 \le m \le n\). The binomial coefficient
\( \begin{aligned} \binom{n}{m} \\ \end {aligned} \)
is defined inductively by
\( \begin{aligned} \binom{\phantom{-}n}{\phantom{-}n} &:= 1 \\ \binom{\phantom{-}n}{-1} &:= 0 \\ \binom{n+1}{m} &= \binom{n}{m-1} + \binom{n}{m} \iff \binom{n}{m} = \binom{n+1}{m} - \binom{n}{m-1} \\ \end {aligned} \)
Extending Pascal’s triangle, we have
\( \begin{array}{c|ccccc} n & \dots & \underset{1}{\binom{n}{n}} & \underset{0}{\binom{n }{n+1}} & \underset{ }{\binom{n }{n+2}} & \dots & \binom{n }{n+k-2} & \binom{n }{n+k-1} & \binom{n }{n+k} \\ n+1 & & \dots & \underset{1}{\binom{n+1}{n+1}} & \underset{0}{\binom{n+1}{n+2}} & \dots & \binom{n+1}{n+k-2} & \binom{n+1}{n+k-1} & \binom{n+1}{n+k} \\ n+2 & & & \dots & \underset{1}{\binom{n+2}{n+2}} & \dots & \binom{n+2}{n+k-2} & \binom{n+2}{n+k-1} & \binom{n+2}{n+k} \\ \vdots & & & & \vdots & & \vdots & \vdots & \vdots \\ \hline k= & \dots & n & n + 1 & n + 2 & \dots & n + k - 2 & n + k - 1 & n + k \\ \end {array} \)
The recurrence says that a given grid coefficient is the sum of its N and NW neighbors, or the difference of its S and W neighbors.
CLAIM
\( \begin{aligned} \boxed{ \boxed{ \forall k \ge 1 \quad \forall n \ge 0 \quad \binom{n}{n+k} = 0 } } \\ \end {aligned} \)
It suffices to show that
\( \boxed{ \begin{aligned} & P(1) \quad \land \quad \forall j \ge 2 \quad \left( \bigwedge_{i=1}^{j-1} P(i) \right) \implies P(j) \\ & \text{where} \quad P(i) : \quad \forall n \ge 0 \quad \binom{n}{n+i} = 0 \\ \end {aligned} } \)
Thus the claim is equivalent to
\( \begin{aligned} \bigwedge_{i=1}^\infty P(i) \end {aligned} \)
Base Case
\( \begin{aligned} P(1) : \quad \forall n \ge 0 \quad \binom{n}{n+1} &= \underset{1 \text{ by def}}{\binom{n+1}{n+1}} - \underset{1 \text{ by def}}{\binom{n}{n}} = 0 \\ \end {aligned} \)
Induction Step
We want to show that
\( \begin{aligned} \boxed{ \forall j \ge 2 \quad \left( \bigwedge_{i=1}^{j-1} P(i) \right) \implies P(j) } \\ \end {aligned} \)
Induction Hypothesis
\( \begin{aligned} \boxed{ \exists j \ge 2 \quad \bigwedge_{i=1}^{j-1} P(i) } \\ \end {aligned} \)
Then
\( \begin{aligned} P(j) : \quad \forall n \ge 0 \quad \binom{n}{n+j} = \underset{0 \text{ by IH}}{\binom{n+1}{n+1+j-1}} - \underset{0 \text{ by IH}}{\binom{n}{n+j-1}} = 0 \\ \end {aligned} \)
\(\blacksquare\)
CLAIM
\( \begin{aligned} \boxed{ \boxed{ \forall n \ge 0 \quad \binom{n}{0} = 1 } } \\ \end {aligned} \)
It suffices to show that
\( \boxed{ \begin{aligned} & P(0) \quad \land \quad \forall k \ge 1 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) \\ & \text{where} \quad P(i) : \quad \binom{i}{0} = 1 \\ \end {aligned} } \\ \)
Thus the claim is equivalent to
\( \begin{aligned} \bigwedge_{i=0}^\infty P(i) \end {aligned} \)
Base Case
\( \begin{aligned} P(0) : \quad \underset{1 \text{ by def}}{\binom{0}{0}} = 1 \\ \end {aligned} \)
Induction Step
We want to show that
\( \begin{aligned} \boxed{ \forall k \ge 1 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) } \end {aligned} \)
Induction Hypothesis
\( \begin{aligned} \boxed{ \exists k \ge 1 \quad \bigwedge_{i=0}^{k-1} P(i) } \end {aligned} \)
Then
\( \begin{aligned} P(k) : \quad \binom{k}{0} = \underset{0 \text{ by def}}{\binom{k-1}{-1}} + \underset{1 \text{ by IH}}{\binom{k-1}{0}} = 1 \\ \end {aligned} \)
\(\blacksquare\)
i
Prove that
\( \begin{aligned} \binom{n}{m} \in \mathbb{Z} \end {aligned} \)
https://math.stackexchange.com/questions/11601/proof-that-a-combination-is-an-integer
CLAIM
\( \begin{aligned} \boxed{ \boxed{ \forall n \ge 0 \quad \forall m \quad 0 \le m \le n \quad \binom{n}{m} \in \mathbb{Z} } } \\ \end {aligned} \)
It suffices to show that
\( \boxed{ \begin{aligned} & P(0) \quad \land \quad \forall k \ge 1 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) \\ & \text{where} \quad P(i) : \quad \forall m \quad 0 \le m \le i \quad \binom{i}{m} \in \mathbb{Z} \\ \end {aligned} } \)
Thus the claim is equivalent to
\( \begin{aligned} \bigwedge_{i=0}^\infty P(i) \end {aligned} \)
Base Case
\( \begin{aligned} & P(0) : \quad \forall m \quad 0 \le m \le 0 \quad \binom{0}{m} \in \mathbb{Z} \\ & \underset{1 \text{ by def}}{\binom{0}{0}} = 1 \\ \end {aligned} \)
Induction Step
We want to show that
\( \begin{aligned} \boxed{ \forall k \ge 1 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) } \\ \end {aligned} \)
Induction Hypothesis
\( \begin{aligned} \boxed{ \exists k \ge 1 \quad \bigwedge_{i=0}^{k-1} P(i) } \\ \end {aligned} \)
\( \begin{aligned} & P(k-1) : \quad \forall m \quad 0 \le m \le k-1 \quad \binom{k-1}{m} \in \mathbb{Z} \\ & \binom{k-1}{0}, \binom{k-1}{1}, \dotsc, \binom{k-1}{k-1} \in \mathbb{Z} \\ \end {aligned} \)
Then
\( \begin{aligned} & P(k) : \quad \forall m \quad 0 \le m \le k \quad \binom{k}{m} \in \mathbb{Z} \\ & \binom{k}{0} = \underset{0 \text{ by def}}{\binom{k-1}{ -1}} + \underset{\text{int by IH}}{\binom{k-1}{0}} \in \mathbb{Z} \\ & \binom{k}{1} = \underset{\text{int by IH}}{\binom{k-1}{ 0}} + \underset{\text{int by IH}}{\binom{k-1}{1}} \in \mathbb{Z} \\ & \quad \vdots \\ & \binom{k}{k} = \underset{\text{int by IH}}{\binom{k-1}{k-1}} + \underset{0 }{\binom{k-1}{k}} \in \mathbb{Z} \\ \end {aligned} \)
\(\blacksquare\)
ii
Prove that if \(p\) is prime and \(1 \le m \le p - 1\) then \(p \mid \binom{p}{m}\).
https://math.stackexchange.com/questions/328655/proving-prime-p-divides-binompk-for-k-in-1-ldots-p-1
https://math.stackexchange.com/questions/1118819/proof-if-p-is-prime-and-0kp-then-p-divides-binom-pk
Suppose that \(1 \le m \le p-1\) for some prime \(p\).
\((\forall m \quad 1 \le m \le p-1 \quad p \nmid m) \implies p \nmid m!\)
\( \begin{aligned} & \binom{p}{m} = \frac{p!}{m! (p-m)!} = \frac{p \times (p-1) \times \dotsb \times (p-m+1)}{m!} = n \in \mathbb{N} \\ & p \times (p-1) \times \dotsb \times (p-m+1) = nm! \\ & p \mid nm! \implies p \mid n \\ \end {aligned} \)
\(\blacksquare\)
from decimal import *
import math
for p in range(1, 25):
print(f"{p:>2} | {math.factorial(p-1)/Decimal(p):>40.10f}")
1 | 1.0000000000
2 | 0.5000000000
3 | 0.6666666667
4 | 1.5000000000
5 | 4.8000000000
6 | 20.0000000000
7 | 102.8571428571
8 | 630.0000000000
9 | 4480.0000000000
10 | 36288.0000000000
11 | 329890.9090909091
12 | 3326400.0000000000
13 | 36846276.9230769231
14 | 444787200.0000000000
15 | 5811886080.0000000000
16 | 81729648000.0000000000
17 | 1230752346352.9411764706
18 | 19760412672000.0000000000
19 | 336967037143578.9473684211
20 | 6082255020441600.0000000000
21 | 115852476579840000.0000000000
22 | 2322315553259520000.0000000000
23 | 48869596859895986086.9565217400
24 | 1077167364120207360000.0000000000
2
Prove that no polynomial \(f(x)\) of degree at least \(1\) with integral coefficients can be prime for every positive integer \(x\).
\( \lnot\exists f \quad \Big( \quad f \in \mathbb{Z}[x] \quad \land \quad \deg f \ge 1 \quad \land \quad \forall x \ge 1 \quad P(f(x)) \quad \Big) \)
3
If \(2^n + 1\) is an odd prime for some integer \(n\), prove that \(n\) is a power of \(2\).
4
Prove that every positive integer is uniquely expressible in the form
\(2^{j_0} + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m}\)
where \(m \ge 0\) and \(0 \le j_0 \lt j_1 \lt j_2 \lt \dotsb \lt j_m\)
https://math.stackexchange.com/questions/813195/positive-integers-expressable-as-sums-of-powers-of-2
5
Prove that there are no positive integers \(a, b, n\) with \(n \gt 1\) such that \((a^n - b^n) \mid (a^n + b^n)\).
6
Write a program to evaluate the expression \(a^m \mod m\) when \(a = 2\) or \(a = 3\) and
\(m = 2447952037112100847479213118326022843437705003126287\) or
\(m = 59545797598759584957498579859585984759457948579595794859456799501\)
2#
1
Let \(a, b, c \in \mathbb{Z}\).
i
\(a \mid a\)
See main.
ii
If \(a \mid b\) and \(b \mid a\) then \(a = \pm b\).
See main.
iii
If \(a \mid b\) and \(b \mid c\) then \(a \mid c\).
See main.
iv
If \(ac \mid bc\) with \(c \ne 0\) then \(a \mid b\).
See main.
v
If \(a \mid b\) then \(ac \mid bc\).
See main.
vi
If \(a \mid b\) and \(a \mid c\) then \(a \mid (bx + cy)\) for all \(x, y \in \mathbb{Z}\).
See main.
2
Prove that if \(n\) is odd then \(8 \mid (n^2 - 1)\).
See main.
3i
Show that if \(m\) and \(n\) are integers of the form \(4k + 1\) then so is \(mn\).
See main.
3ii
Show that if \(m\) and \(n\) are members of \(\mathbb{N}\) and \(mn\) is of the form \(4k - 1\) then so is one of \(m\) and \(n\).
See main.
3iii
Show that every member of \(\mathbb{N}\) of the form \(4k - 1\) has a prime factor of this form.
See main.
3iv
Show that there are infinitely many primes of the form \(4k - 1\).
See main.
4
Find all solutions \(x, y \in \mathbb{Z}\) to the equation \(x^2 - y^2 = 105\).
\( \begin{aligned} ds &= (x - y)(x + y) = x^2 - y^2 = 105 \\ d &= x - y \implies x = d + y = d + s - x \implies x = (s + d)/2 \\ s &= x + y \implies y = s - x = s - d - y \implies y = (s - d)/2 \\ \end {aligned} \)
\(105 = ds\) is odd and so both \(d\) and \(s\) are odd.
This gives a bijection between the solution set and the integer divisors of \(105\). Moreover, interchanging \(s\) and \(d\) keeps \(x\) fixed and replaces \(y\) by \(-y\), and replacing \(s\) and \(d\) by \(-s\) and \(-d\) changes the sign of both \(x\) and \(y\).
Thus it suffices to check the cases with \(s \gt d \gt 0\) (i.e., \((s, d)\)) one of the four ordered pairs
\((105, 1), (35, 3), (21, 5), (15, 7)\)
Let \(x\) and \(y\) be integers. Find all integral 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)\)
5
Show that if \(ad - bc = \pm 1\) then \(\gcd(a + b, c + d) = 1\).
\((a + b)d - (c + d)b = ad + bd - bc - bd = ad - bc\)
Thus \((a + b)d - (c + d)b = \pm 1\)
\( \gcd(a + b, c + d) \mid (a + b) \\ \gcd(a + b, c + d) \mid (c + d) \\ \gcd(a + b, c + d) \mid (a + b)d - (c + d)b \\ \)
Thus \(\gcd(a + b, c + d) \mid \pm 1 \implies \gcd(a + b, c + d) = | \pm 1 |\)
\(\blacksquare\)
3#
1
Write a program to find \(x\) and \(y\) such that \(mx + ny = \gcd(m, n)\) where
i
\(m = 8148657527, n = 8148653735\)
ii
\(m = 8418785375, n = 7849911069\)
iii
\(m = 4029583209458450398503, n = 3449459408504500003009\)
iv
\(m = 304250263527210, n = 230958203482321\)
2
Show that if \(\gcd(a, b) = 1\) then \(\gcd(a - b, a + b) = 1\) or \(2\). Exactly when is the value \(2\)?
3
The Fibonacci sequence (1202) is defined iteratively by \(F_1 = F_2 = 1\), \(F_{n + 1} = F_n + F_{n - 1} (n = 2, 3, \dotsc)\). Show that if \(m, n \in \mathbb{N}\) satisfy \(m \mid F_n\) and \(m \mid F_{n + 1}\) then \(m = 1\).
4
The squarefree numbers are the natural numbers which have no repeated prime factors, e.g \(6\), \(105\). Note that \(1\) is the only natural number which is both squarefree and a perfect square. Prove that every \(n \in \mathbb{N}\) with \(n \gt 1\) can be written uniquely as the product of a perfect square and a squarefree number.
5
Let \(a \in \mathbb{N}\) and \(b \in \mathbb{Z}\). Prove that the equations \(\gcd(x, y) = a\) and \(xy = b\) can be solved simultaneously in integers \(x\) and \(y\) iff \(a^2 \mid b\).
M1 Review#
1
Show that \(n \mid (n - 1)!\) for all composite \(n \gt 4\).
\(\text{Proof}\)
Composite \(n = lm\) with \(1 \lt l \le m \lt n\).
When \(l \ne m\) both \(l\) and \(m\) occur in \((n - 1)!\) and so \(lm = n \mid (n - 1)!\)
Since \(n \gt 4\), when \(l = m\) it must be the case that \(l = m \ge 3\) since \(l = m = 2 \implies n = 4\). On the other hand, \(n = l^2 \gt 2l \gt l \ge 3\) and so both \(l\) and \(2l\) occur in \((n - 1)!\). Thus \(n = l^2 \mid (n - 1)!\)
\(\blacksquare\)
2
Prove that if \(m, n \in \mathbb{N}\) then there are integers \(a, b\) s.t. \(\gcd(a, b) = m\) and \(\text{lcm}[a, b] = n\) iff \(m \mid n\).
\(\text{Proof}\)
First Direction
Suppose \(m \mid n\). Let \(m = a\) and \(n = b\).
Then \(m \mid a\) and \(m \mid b\) and so \(m \mid \gcd(a, b)\).
But \(\gcd(a, b)\) is just \(\gcd(m, n)\) and we know that \(\gcd(m, n) \mid m\).
Since \(m \mid \gcd(a, b)\) and \(\gcd(a, b) \mid m\) it is the case that \(m = \gcd(a, b)\).
\(\text{lcm}[a, b] = \frac{ab}{\gcd(a, b)} = \frac{mn}{m} = n\)
Second Direction
Suppose \(\gcd(a, b) = m\) and \(\text{lcm}[a, b] = n\).
\(n = \frac{ab}{\gcd(a, b)} = \frac{ab}{m} = (a/m)(b/m)m \iff m \mid n\)
\(\blacksquare\)
3
Factorize \(4087\).
\(\lfloor \sqrt{4087} \rfloor = 63\)
\(4087 = 4096 - 9 = 2^{12} - 3^2 = (2^6)^2 \textcolor{red}{+ 3 \cdot 2^6 - 3 \cdot 2^6} - 3^2 = (2^6 - 3)(2^6 + 3) = (64 - 3) \times (64 + 3) = 61 \times 67\)
import math
math.sqrt(4087)
63.92964883369844
4
Find \(x\) and \(y\) s.t. \(922x + 2163y = \gcd(922, 2163)\).
\( \begin{aligned} j && q_j && r_j && x_j && y_j \\ -1 && && 2163 && 0 && 1 \\ 0 && 2 && 922 && 1 && 0 \\ 1 && 2 && 319 && -2 && 1 \\ 2 && 1 && 284 && 5 && -2 \\ 3 && 8 && 35 && -7 && 3 \\ 4 && 8 && 4 && 61 && -26 \\ 5 && 1 && 3 && -495 && 211 \\ 6 && && 1 && 556 && -237 \\ \end {aligned} \)
\(\gcd(922, 2163) = 1 = 556 \times 922 + (-237) \times 2163\)
6#
1
Find all solutions (if there are any) to each of the following congruences.
i
\( x^2 \equiv -1 \mod 7 \)
\( x^2 \equiv -1 \equiv 6 \mod 7 \)
p = 7
[i**2%7 for i in range(1, p)]
[1, 4, 2, 2, 4, 1]
M2 Review#
1
Suppose that \(p\), \(q\), and \(r\) are distinct primes. Prove that
\(p^{(q - 1)(r - 1)} + q^{(r - 1)(p - 1)} + r^{(p - 1)(q - 1)} \equiv 2 \mod pqr\)
2
Solve the simultaneous congruences.
\( \begin{aligned} x \equiv 4 \mod 19 \\ x \equiv 5 \mod 31 \\ \end {aligned} \)
3
Show that \(2\) is a primitive root modulo \(11\) and draw up a table of discrete logarithms to this base modulo \(11\). Hence, or otherwise, find all solutions to the following congruences.
\( \begin{aligned} x^{ 6} \equiv 7 \mod 11 \\ x^{18} \equiv 9 \mod 11 \\ x^{ 7} \equiv 8 \mod 11 \\ \end {aligned} \)
4
Evaluate the following Legendre symbols.
\( \begin{aligned} \left( \frac{-1}{103} \right)_L \\ \left( \frac{ 2}{103} \right)_L \\ \left( \frac{ 7}{103} \right)_L \\ \end {aligned} \)