Exercises#
Contents#
1#
Binomial Coefficient#
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\)
\(\tbinom{n}{m} \in \mathbb{Z}\)#
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\)
\(p \mid \tbinom{p}{m} \quad 1 \le m \le p-1\)#
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
Prime Polynomials#
Prove that
No polynomial \(f(x)\) of degree at least \(1\) with integral coefficients can be prime for every nonnegative integer \(x\).
\( \lnot\exists f(x) \quad \Big( \quad f(x) \in \mathbb{Z}[x] \quad \land \quad \deg f(x) \ge 1 \quad \land \quad \forall x \ge 0 \quad P(f(x)) \quad \Big) \)
PROOF by contradiction
Suppose that there is a polynomial \(f\) of degree at least \(1\) with integral coefficients that is prime for every nonnegative integer \(x\). In particular
\(\exists p \quad f(0) = p\)
Then \(f\) has the form
\( \begin{aligned} f(x) = p + \sum_{i=1}^n a_i x^i \quad \text{ where } \quad \exists j \ge 1 \quad a_j \ne 0 \end {aligned} \)
Consider \(f(kp)\) for some nonnegative integer \(k\).
\( \begin{aligned} f(kp) &= p + \sum_{i=1}^n a_i (kp)^i \\ &= p + pk \sum_{i=1}^n a_i (kp)^{i-1} \\ &= p(1 + k \sum_{i=1}^n a_i (kp)^{i-1}) \\ \end {aligned} \)
Thus \(p \mid f(kp)\). But \(f(kp)\) is prime. Thus
\(\forall k \ge 0 \quad p = f(kp)\)
In other words \(f\) takes the value \(p\) infinitely many times. Then the polynomial
\( \begin{aligned} g(x) &= f(xp) - p \\ &= \left( p + \sum_{i=1}^n a_i p^i x^i \right) - p \\ &= \sum_{i=1}^n a_i p^i x^i \\ \end {aligned} \)
takes the value \(0\) infinitely many times. This is to say that \(g(x)\) has infinitely many roots \(x = 0, 1, 2, \dotsc\) (this is not to say anything of whether negative numbers can be roots too).
The fundamental theorem of algebra says that a nonconstant polynomial of degree \(n\) has at most \(n\) real roots.
Thus \(g\) is identically \(0\) (i.e., \(g\) is the zero function). But then
\( \begin{aligned} g(x) &= 0 = \sum_{i=1}^n a_i p^i x^i \implies \forall i \ge 1 \quad a_i = 0 \\ f(x) &= p + \underbrace{\sum_{i=1}^n a_i x^i}_0 \\ \end {aligned} \)
Thus \(f(x) = p\) is a constant. Contradiction.
\(\blacksquare\)
2
We’ve shown that the result holds for the class of polynomials with positive integer inputs. Now we show that the result also holds for a larger class of polynomials with nonnegative integer inputs (which includes the class of polynomials with positive integer inputs).
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(x) \quad \Big( \quad f(x) \in \mathbb{Z}[x] \quad \land \quad \deg f(x) \ge 1 \quad \land \quad \forall x \ge 1 \quad P(f(x)) \quad \Big) \)
PROOF by contradiction
Let a polynomial of degree at least \(1\) with integral coefficients \(f\) be prime for every positive integer \(x\). In particular
\( \begin{aligned} \exists p \quad f(1) = a_0 + \sum_{i=1}^n a_i = p \end {aligned} \)
Consider \(f(kp + 1)\) for any nonnegative integer \(k\)
\( \begin{aligned} f(kp + 1) &= \sum_{i=0}^n a_i (kp + 1)^i = a_0 + \sum_{i=1}^n a_i (kp + 1)^i \\ &= a_0 + a_1 (kp + 1) + a_2 ((kp)^2 + 2kp + 1) + a_3 ((kp)^3 + 3(kp)^2 + 3kp + 1) + \dotsb + a_n ((kp)^n + \tbinom{n}{1} (kp)^{n-1} + \dotsb + \tbinom{n}{n-1} kp + 1) \\ &= a_0 + \left( \sum_{i=1}^n a_i \right) + a_1 (kp) + a_2 ((kp)^2 + 2kp) + a_3 ((kp)^3 + 3(kp)^2 + 3kp) + \dotsb + a_n ((kp)^n + \tbinom{n}{1} (kp)^{n-1} + \dotsb + \tbinom{n}{n-1} kp) \\ &= \underbrace{a_0 + \sum_{i=1}^n a_i }_{f(1)} + \left( \sum_{i=1}^n a_i ((kp + 1)^i - 1) \right) \\ &= p + p \times \frac{a_1 (kp) + a_2 ((kp)^2 + 2kp) + a_3 ((kp)^3 + 3(kp)^2 + 3kp) + \dotsb + a_n ((kp)^n + \tbinom{n}{1} (kp)^{n-1} + \dotsb + \tbinom{n}{n-1} kp)}{p} \\ \end {aligned} \)
Thus \(p \mid f(kp + 1)\). But \(f(kp + 1)\) is prime. Thus
\(\forall k \ge 0 \quad f(kp + 1) = p\)
In other words \(f\) takes the value \(p\) infinitely many times. Then the polynomial
\( \begin{aligned} g(x) &= f(xp + 1) - p \\ &= \left( \sum_{i=0}^n a_i (xp + 1)^i \right) - \left( a_0 + \sum_{i=1}^n a_i \right) \\ &= \left( a_0 + \sum_{i=1}^n a_i + \sum_{i=1}^n a_i ((px + 1)^i - 1) \right) - \left( a_0 + \sum_{i=1}^n a_i \right) \\ &= \sum_{i=1}^n a_i ((px + 1)^i - 1) \\ &= x \times \frac{a_1 (px) + a_2 ((px)^2 + 2px) + a_3 ((px)^3 + 3(px)^2 + 3px) + \dotsb + a_n ((px)^n + \tbinom{n}{1} (px)^{n-1} + \dotsb + \tbinom{n}{n-1} px)}{x} \end {aligned} \)
takes the value \(0\) infinitely many times. This is to say that \(g\) has infinitely many roots \(x = 0, 1, 2, \dotsc\) (this is not to say anything of whether negative numbers can be roots too).
The fundamental theorem of algebra says that a nonconstant polynomial of degree \(n\) has at most \(n\) real roots.
Thus \(g\) is identically \(0\) (i.e., \(g\) is the zero function). But then
\( \begin{aligned} g(x) &= 0 = \sum_{i=1}^n a_i ((px + 1)^i - 1) \implies \forall i \ge 1 \quad a_i = 0 \\ f(x) &= a_0 + \underbrace{\sum_{i=1}^n a_i x^i}_0 \\ \end {aligned} \)
Thus \(f(x) = a_0\) is a constant. Contradiction.
\(\blacksquare\)
Resources
Powers of \(2\)#
3
If \(2^n + 1\) is an odd prime for some nonnegative integer \(n\), prove that \(n\) is a power of \(2\).
\( \boxed{ \boxed{ \exists n \in \mathbb{N} \quad \exists k \in \mathbb{N} \quad \exists p \ge 3 \quad 2^n + 1 = 2k + 1 = p \quad \implies \quad \exists q \in \mathbb{N} \quad n = 2^q } } \)
PROOF by contradiction
Suppose \(2^n + 1\) is an odd prime but that \(n\) is not a power of \(2\).
Then by the fundamental theorem of arithmetic we have
\(n = 2^k \times m\)
for some \(k \ge 0\) and for some odd \(m \gt 1\).
\(2^n + 1 = 2^{2^k m} + 1 = x^m + 1\) where \(x = 2^{2^k}\)
is a sum of odd powers and so
\( \begin{aligned} x^m + 1 &= (x + 1)(x^{m-1} - x^{m-2} + x^{m-3} - \dotsb - x + 1) \\ 2^n + 1 &= (2^{2^k} + 1)(2^{2^k(m-1)} - 2^{2^k(m-2)} + 2^{2^k(m-3)} - \dotsb - 2^{2^k} + 1) \\ \end {aligned} \)
The first factor \(2^{2^k} + 1\) is greater than \(1\)
\(k \ge 0 \implies 2^k \ge 1 \implies 2^{2^k} \ge 2 \implies 2^{2^k} + 1 \ge 3\)
The second factor \(2^{2^k(m-1)} - 2^{2^k(m-2)} + 2^{2^k(m-3)} - \dotsb - 2^{2^k} + 1\) is greater than \(1\) since \(m \ge 3\).
For example when \(k = 0\) we have
\( \begin{aligned} m &&& \\ 3 &&& \underbrace{2^{2^k(2)} - 2^{2^k}}_{2} + 1 = 3 \\ 5 &&& \underbrace{2^{2^k(4)} - 2^{2^k(3)}}_{8} + \underbrace{2^{2^k(2)} - 2^{2^k}}_{2} + 1 = 11 \\ \end {aligned} \)
For example when \(k = 1\) we have
\( \begin{aligned} m &&& \\ 3 &&& \underbrace{2^{2^k(2)} - 2^{2^k}}_{12} + 1 = 13 \\ 5 &&& \underbrace{2^{2^k(4)} - 2^{2^k(3)}}_{192} + \underbrace{2^{2^k(2)} - 2^{2^k}}_{12} + 1 = 205 \\ \end {aligned} \)
Thus \(2^n + 1\) is not a prime. Contradiction.
\(\blacksquare\)
Another way to show this is as follows.
There is an odd prime \(p\) which divides \(n\) and so
\(pk = n\) for some \(k \ge 1\).
\( 2^n + 1 = (2^k)^p + 1^p = (2^k + 1)(2^{k(p-1)} - 2^{k(p-2)} + 2^{k(p-3)} - \dotsb - 2^k + 1) \)
The first factor \(2^k + 1\) is greater than \(1\)
\(k \ge 1 \implies 2^k \ge 2 \implies 2^k + 1 \ge 3\)
Resources
Every nonnegative integer is a sum of powers of \(2\)#
CLAIM
Any nonnegative integer \(n \le 2^\ell\) for any \(\ell \ge 0\) can be expressed as a sum of zero or more powers of \(2\).
PROOF by induction on \(\ell\)
It suffices to show that
\( \boxed{ \begin{aligned} & P(0) \quad \land \quad \forall \ell \ge 1 \quad \left( \bigwedge_{i=0}^{\ell - 1} P(i) \right) \implies P(\ell) \\ & \text{where} \quad P(i) : \quad \forall n \quad 1 \le n \le 2^i \quad \exists m \ge 0 \quad n = 2^{j_0} + 2^{j_1} + \dotsb + 2^{j_m} \quad \land \quad 0 \le j_0 \le j_1 \le \dotsb \le j_m \le i \end {aligned} } \)
BC
\( P(0) : \quad \forall n \quad 1 \le n \le 2^0 \quad \exists m \ge 0 \quad n = 2^{j_0} + 2^{j_1} + \dotsb + 2^{j_m} \quad \land \quad 0 \le j_0 \le j_1 \le \dotsb \le j_m \le 0 \)
\(1 = 2^0\)
IS
IH
\( P(k-1) : \quad \forall n \quad 1 \le n \le 2^{k-1} \quad \exists m \ge 0 \quad n = 2^{j_0} + 2^{j_1} + \dotsb + 2^{j_m} \quad \land \quad 0 \le j_0 \le j_1 \le \dotsb \le j_m \le k-1 \)
Then for any \(n \le 2^k\) it is either the case that
\(n \le 2^{k-1}\)
in which case \(n\) can be expressed as a sum of zero or more powers of \(2\) by the induction hypothesis, or
\(2^{k-1} \lt n \le 2^k\)
in which case
\( \begin{aligned} & n \le 2^k = 2(2^{k-1}) = (1 + 1)2^{k-1} = 2^{k-1} + 2^{k-1} \\ & n - 2^{k-1} \le 2^{k-1} \end {aligned} \)
and so
\(n = \underbrace{n - 2^{k-1}}_{\text{sum of powers of } 2} + \underbrace{\quad 2^{k-1} \quad}_{\text{sum of powers of } 2}\)
\(\blacksquare\)
CLAIM
Any nonnegative integer can be expressed as a sum of powers of \(2\).
PROOF by induction on \(n\)
It suffices to show that
\( \boxed{ \begin{aligned} & P(1) \quad \land \quad \forall k \ge 2 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) \\ & \text{where} \quad P(i) : \quad \exists m \ge 0 \quad i = 2^{j_0} + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m} \quad \land \quad 0 \le j_0 \le j_1 \le \dotsb \le j_m \end {aligned} } \)
BC
\( P(1) : \quad 1 = 2^0 \quad m = 0 \quad j_0 = 0 \)
IS
\(\blacksquare\)
Every positive integer has a unique binary expression#
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\)
PROOF by induction
\( \forall n \in \mathbb{N}^+ \quad \exists m \ge 0 \quad n = 2^{j_0} + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m} \quad \land \quad 0 \le j_0 \lt j_1 \lt j_2 \lt \dotsb \lt j_m \)
It suffices to show that
\( \boxed{ \begin{aligned} & P(1) \quad \land \quad \forall k \ge 2 \quad \left( \bigwedge_{i=1}^{k-1} P(i) \right) \implies P(k) \\ & \text{ where } \quad P(i) : \quad \exists m \ge 0 \quad i = 2^{j_0} + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m} \quad \land \quad 0 \le j_0 \lt j_1 \lt j_2 \lt \dotsb \lt j_m \end {aligned} } \)
Thus the claim is equivalent to
\( \begin{aligned} \bigwedge_{i=1}^\infty P(i) \end {aligned} \)
BC
\( \begin{aligned} P(1) : \quad m = 0 \quad 1 = 2^{j_0} \quad \land \quad 0 \le j_0 = 0 \end {aligned} \)
IS
We want to show that
\( \boxed{ \begin{aligned} \forall k \ge 2 \quad \left( \bigwedge_{i=1}^{k-1} P(i) \right) \implies P(k) \end {aligned} } \)
IH
\( \boxed{ \begin{aligned} \exists k \ge 2 \quad \bigwedge_{i=1}^{k-1} P(i) \end {aligned} } \)
From the induction hypothesis we know that
\( \begin{aligned} P(k-1) : \quad \exists m \ge 0 \quad k-1 = 2^{j_0} + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m} \quad \land \quad 0 \le j_0 \lt j_1 \lt j_2 \lt \dotsb \lt j_m \end {aligned} \)
Then
\(k = k - 1 + 1 = \underbrace{2^{j_0} + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m}}_{k-1} + 2^0\)
If \(k-1\) is even then \(j_0 \gt 0\) and we have
\( k = 2^0 + 2^{j_0} + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m} \quad \land \quad 0 \le 2^0 \lt j_0 \lt j_1 \lt j_2 \lt \dotsb \lt j_m \)
and we are done.
If \(k-1\) is odd then \(j_0 = 0\) and we have
\( \begin{aligned} k &= 2^0 + 2^0 + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m} \\ &= 2^1 + 2^{j_1} + 2^{j_2} + \dotsb + 2^{j_m} \\ \end {aligned} \)
\(1 \le j_1\) and so if \(j_1 \gt 1\) we are done but if \(j_1 = 1\) then \(2^1 + 2^{j_1} = 2^2\) and we will have to check \(j_2\), and we will have to continue in this way through \(2^{j_m}\). Let’s look at this another way.
\(k-1\) odd implies \(k\) even, which implies \(k/2\) is an integer with \(k/2 \lt k\) which, by the induction hypothesis, can be expressed as a sum of powers of \(2\).
\( \begin{aligned} \exists s \ge 0 \quad k/2 = 2^{t_0} + 2^{t_1} + 2^{t_2} + \dotsb + 2^{t_s} \quad \land \quad 0 \le t_0 \lt t_1 \lt t_2 \lt \dotsb \lt t_s \end {aligned} \)
\( k/2 = 2^{t_0} + 2^{t_1} + 2^{t_2} + \dotsb + 2^{t_s} \iff k = 2^{t_0+1} + 2^{t_1+1} + 2^{t_2+1} + \dotsb + 2^{t_s+1} \)
Thus it follows that \(k\) is expressible as a sum of powers of \(2\).
\(\blacksquare\)
Resources
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)\).
\( \lnot \quad \left( \quad \exists a, b \ge 1 \quad \exists n \ge 2 \quad (a^n - b^n) \mid (a^n + b^n) \quad \right) \)
\( \forall a, b \ge 1 \quad \forall n \ge 2 \quad (a^n - b^n) \nmid (a^n + b^n) \)
PROOF by contradiction
Suppose \((a^n - b^n) \mid (a^n + b^n)\) for some \(a, b \ge 1, n \ge 2\).
Then there is some integer \(k\) for which
\((a^n - b^n)k = (a^n + b^n)\)
Let \(d = \gcd(a, b)\) and define \(a_1 = a/d\) and \(b_1 = b/d\). We know that \(\gcd(a_1, b_1) = 1\).
\( \begin{aligned} (a^n - b^n)k &= (a^n + b^n) \\ \left( \frac{d^n}{d^n} a^n - \frac{d^n}{d^n} b^n \right) k &= \left( \frac{d^n}{d^n} a^n + \frac{d^n}{d^n} b^n \right) \\ d^n \left( \frac{a^n}{d^n} - \frac{b^n}{d^n} \right) k &= d^n \left( \frac{a^n}{d^n} + \frac{b^n}{d^n} \right) \\ (a_1^n - b_1^n) k &= (a_1^n + b_1^n) \\ \end {aligned} \)
We know that
\( \begin{aligned} & (a^n_1 - b^n_1) \mid [(a_1^n + b_1^n) + (a_1^n - b_1^n)] \\ & (a^n_1 - b^n_1) \mid 2a_1^n \\ & (a^n_1 - b^n_1) \mid (2a_1^n + (-2)(a_1^n - b_1^n)) \\ & (a^n_1 - b^n_1) \mid 2b_1^n \\ & (a^n_1 - b^n_1) \mid b_1^n \quad \oplus \quad (a^n_1 - b^n_1) \mid 2 \\ \end {aligned} \)
\(1 = \gcd(a_1, b_1) = \gcd(a_1^n, b_1^n) = \gcd(a_1^n - b_1^n, b_1^n)\)
Thus \((a^n_1 - b^n_1) \mid 2\)
But this is impossible for \(a, b \ge 1, n \ge 2\).
\(\blacksquare\)
If \(a = b\) then \(a^n - b^n = 0\). Thus \(a \ne b\).
WLOG \(a \gt b \iff a^n \gt b^n \iff a^n - b^n \gt 0\)
\( 0 \lt a^n - b^n \le 2b^n \iff b^n \lt a^n \le 3b^n \iff 1 \lt \left( \frac{a}{b} \right)^n \le 3 \)
We know that there is an integer \(k\) such that
\( \begin{aligned} (a^n - b^n)k &= (a^n + b^n) \\ ka^n - kb^n &= a^n + b^n \\ ka^n - a^n &= kb^n + b^n \\ a^n(k - 1) &= b^n(k + 1) \\ \frac{a^n}{b^n} &= \frac{k+1}{k-1} \\ \left( \frac{a}{b} \right)^n &= \frac{k+1}{k-1} \\ \end {aligned} \)
Thus \(k \ne 1\). Further
\( 1 \lt \frac{k+1}{k-1} \le 3 \implies 3k - 3 \ge k + 1 \iff k \ge 2 \)
Resources
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} \)