Exercises

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/2158/division-of-factorials-binomal-coefficients-are-integers

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

https://math.stackexchange.com/questions/2033748/for-any-prime-number-p-and-natural-number-i-p-prove-that-p-divides-p

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\).

\( \begin{aligned} & \forall \ell \ge 0 \quad \forall n \quad 1 \le n \le 2^\ell \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 \ell \\ & 0 \text{ is an empty sum of powers of } 2 \\ \end {aligned} \)

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\).

\( \begin{aligned} & \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 \le j_1 \le \dotsb \le j_m \\ & 0 \text{ is an empty sum of powers of } 2 \\ \end {aligned} \)

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

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\).

4 - Lehman’s Method#

The object is to use Lehman’s method to find factors. The first two problems could be done by hand, but it would be more convenient to use a good calculator, or Pari/gp. It is not claimed that for the numbers below Lehman’s method is necessarily faster than trial division, although it is a lot less tedious. More to the point, you can see the possibilities. Lehman’s method runs as follows.

Given \(n \in \mathbb{N}\) proceed as follows.

1. Try trial division \(d \mid n\) for \(d \le n^{\frac{1}{3}}\) for \(d\) in the range. It suffices to take prime values of \(d\) only and for the first number \(n\) below these are well known. If a factor is found, stop. Pari/gp has a list of primes built in.

2. For each \(t \in \mathbb{N}\) with \(1 \le t \le n^{\frac{1}{3}}\) and \(x \in \mathbb{N}\) with \((4tn)^{\frac{1}{2}} \le x \le (4tn + n^{\frac{2}{3}})^{\frac{1}{2}}\) (for the first number below the intervals that arise contain at most one integer) compute \(x^2 - 4tn\) and check to see if this is a perfect square \(y^2\). When it is, compute \(\gcd(x + y, n)\), and if this gives a proper factor of \(n\) then stop.

In the first two cases list the remainders on division by primes \(3, 7, 11, 13, 17, \dotsc\) up to \(n^{\frac{1}{3}}\) and for each \(t\) with \(1 \le t \le n^{\frac{1}{3}}\) list the possible values for \(x\), and if \(x^2 - 4tn\) is a perfect square \(y^2\) compute \(\gcd(x + y, n)\) and then stop. For the third number just give a value of \(t\), the corresponding values of \(x\) and \(y\) and the factor. Note that Pari/gp has the gcd function built in. If a different programming language is used you will probably need to construct the gcd algorithm from scratch.

Find a nontrivial factor of \(19109\).

Find a nontrivial factor of \(2048129\).

Find a nontrivial factor of \(9912409831\).

M1#

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\)

5#

1#

1

Let \(\{ F_n : n = 0, 1, \dotsc \}\) be the Fibonacci sequence defined by

\( \begin{aligned} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+1} &= F_n + F_{n-1} \\ \end {aligned} \)

and let

\( \begin{aligned} \theta = \frac{1 + \sqrt{5}}{2} = 1.6180339887498948482045868343656 \dots \end {aligned} \)

\(F_n = \frac{\theta^n - (-\theta)^{-n}}{\sqrt{5}}\)#

i

Prove that

\( \begin{aligned} F_n = \frac{\theta^n - (-\theta)^{-n}}{\sqrt{5}} \end {aligned} \)

Define \(\varphi = \theta\) and \(\psi = -\theta^{-1}\).

We know that

\( \begin{aligned} && \varphi &= \frac{1 + \sqrt{5}}{2} = \phantom{-} 1.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ -\varphi^{-1} &= -\frac{2}{1 + \sqrt{5}} = -\frac{2 (1 - \sqrt{5})}{(1 + \sqrt{5})(1 - \sqrt{5})} = & \psi &= \frac{1 - \sqrt{5}}{2} = -0.618 \, 033 \, 988 \, 749 \, 894 \, 848 \, 204 \, 586 \, 834 \, 365 \, 6 \dots \\ \end {aligned} \)

and that

\( \begin{aligned} \varphi + \psi = \varphi - \frac{1}{\varphi} &= \frac{1 \textcolor{#0096FF}{+ \sqrt{5}}}{2} + \frac{\phantom{-} 1 \textcolor{#0096FF}{- \sqrt{5}}}{2} =& 1 \\ \varphi - \psi = \varphi + \frac{1}{\varphi} &= \frac{\textcolor{#0096FF}{1} + \sqrt{5}}{2} + \frac{\textcolor{#0096FF}{-1} + \sqrt{5}}{2} =& \sqrt{5} \\ \end {aligned} \)

It suffices to show that

\( \begin{aligned} & P(0) \quad \land \quad 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 F_i = \frac{\theta^i - (-\theta)^{-i}}{\sqrt{5}} \end {aligned} \)

Proof by induction on \(n\)

Basis

\( \begin{aligned} & P(0) : \quad F_0 = \frac{\varphi^0 - \psi^0}{\sqrt{5}} &= 0 \\ & P(1) : \quad F_1 = \frac{\varphi - \psi}{\sqrt{5}} &= 1 \\ \end {aligned} \)

Induction Step

We must show that

\( \begin{aligned} \forall k \ge 2 \quad \left( \bigwedge_{i=0}^{k-1} P(i) \right) \implies P(k) \end {aligned} \)

Induction Hypothesis

Suppose that

\( \begin{aligned} \exists k \ge 2 \quad \bigwedge_{i=0}^{k-1} P(i) \end {aligned} \)

Then

\( \begin{aligned} F_{k-1} + F_{k-2} &= \frac{\varphi^{k-1} - \psi^{k-1}}{\sqrt{5}} + \frac{\varphi^{k-2} - \psi^{k-2}}{\sqrt{5}} \\ &= \frac{(\varphi^{k-1} + \varphi^{k-2}) - (\psi^{k-1} + \psi^{k-2})}{\sqrt{5}} \\ &= \frac{(\varphi + 1) \varphi^{k-2} - (\psi + 1) \psi^{k-2}}{\sqrt{5}} \\ &= \frac{\varphi^2 \varphi^{k-2} - \psi^2 \psi^{k-2}}{\sqrt{5}} \\ F_k &= \frac{\varphi^k - \psi^k}{\sqrt{5}} \\ \end {aligned} \)

\(\blacksquare\)

Euclid’s algorithm runs in time at most linear in the bit size of \(\min(a, b)\)#

ii

Suppose that \(a\) and \(b\) are positive integers with \(b \le a\) and we adopt the notation used in the description of Euclid’s algorithm.

Prove that for \(k = 0, 1, \dotsc, s - 1\) we have \(F_k \le r_{s-1-k}\) and

\( \begin{aligned} s \le 1 + \frac{\log 2b \sqrt{5}}{\log \theta} \end {aligned} \)

This shows that Euclid’s algorithm runs in time at most linear in the bit size of \(\min(a, b)\).

We want to show the following.

\( \begin{aligned} F_0 \le r_{s-1} \\ F_1 \le r_{s-2} \\ F_2 \le r_{s-3} \\ \vdots \\ F_{s-2} \le r_{1} \\ F_{s-1} \le r_{0} \\ \end {aligned} \)

It suffices to show that

\( \begin{aligned} & P(0) \quad \land \quad P(1) \quad \land \quad \forall \ell \ge 2 \quad \left( \bigwedge_{i=0}^{\ell-1} P(i) \right) \implies P(\ell) \\ & \text{where} \quad P(i) : \quad F_i \le r_{s-1-i} \end {aligned} \)

Proof by induction on \(k\)

Basis

\( \begin{aligned} & P(0) : \quad F_0 = 0 \le r_{s-1} \\ & P(1) : \quad F_1 = 1 \le r_{s-2} \\ \end {aligned} \)

\(P(0)\) is true because the division theorem stipulates that \(0 \le r\) for any \(r\) (i.e., remainders are non-negative).

\(P(1)\) is true because Euclid’s algorithm stipulates that \(r_j \lt r_{j-1}\).

\(0 \le r_{s-1} \lt r_{s-2} \implies 1 \le r_{s-2}\)

Induction Step

We must show that

\( \begin{aligned} \forall \ell \ge 2 \quad \left( \bigwedge_{i=0}^{\ell-1} P(i) \right) \implies P(\ell) \end {aligned} \)

Induction Hypothesis

Suppose that

\( \begin{aligned} \exists \ell \ge 2 \quad \bigwedge_{i=0}^{\ell-1} P(i) \end {aligned} \)

Then

\( \begin{aligned} F_{\ell - 2} & \le r_{s - 1 - (\ell - 2)} = r_{s - \ell + 1} \\ F_{\ell - 1} & \le r_{s - 1 - (\ell - 1)} = r_{s - \ell} \\ F_{\ell} & = F_{\ell - 1} + F_{\ell - 2} \\ F_{\ell} & \le r_{s - \ell} + r_{s - \ell + 1} \end {aligned} \)

Euclid’s algorithm says

\(r_{s - \ell - 1} = r_{s - \ell} q_{s - \ell + 1} + r_{s - \ell + 1} \quad 0 \lt r_{s - \ell + 1} \lt r_{s - \ell}\)

where we know that \(q_{s - \ell + 1} \ge 1\).

Thus

\(F_{\ell} \le r_{s - \ell - 1}\)

\(\blacksquare\)

Proof

\( \begin{aligned} F_{s-1} &= \frac{\varphi^{s-1} - \psi^{s-1}}{\sqrt{5}} \le r_{s-1-(s-1)} = r_0 \\ \varphi^{s-1} &\le r_0 \sqrt{5} + \psi^{s-1} \\ \log \varphi^{s-1} &\le \log (r_0 \sqrt{5} + \psi^{s-1}) \\ (s - 1) (\log \varphi) &\le \log (r_0 \sqrt{5} + \psi^{s-1}) \\ s - 1 &\le \frac{\log (r_0 \sqrt{5} + \psi^{s-1})}{\log \varphi} \\ s &\le 1 + \frac{\log (r_0 \sqrt{5} + \psi^{s-1})}{\log \varphi} \\ \end {aligned} \)

We know that

\( |\psi^{s-1}| \le 1 \)

and that

\( \begin{aligned} & & 1 & \le & r_0 \\ -1 & \lt & \sqrt{5} & \le & r_0 \sqrt{5} \\ r_0 \sqrt{5} - 1 & \lt & r_0 \sqrt{5} + \sqrt{5} & \le & 2 r_0 \sqrt{5} \\ 1 + \frac{\log (r_0 \sqrt{5} - 1)}{\log \varphi} & \lt & 1 + \frac{\log (r_0 \sqrt{5} + \sqrt{5})}{\log \varphi} & \le & 1 + \frac{\log (2 r_0 \sqrt{5})}{\log \varphi} \\ \end {aligned} \)

Thus

\( \begin{aligned} s &\le 1 + \frac{\log (r_0 \sqrt{5} + \psi^{s-1})}{\log \varphi} \lt 1 + \frac{\log (2 r_0 \sqrt{5})}{\log \varphi} \end {aligned} \)

\(\blacksquare\)

2 - Solving linear congruences#

2

Solve where possible.

i

\(91x \equiv 84 \mod 143\)

Compute \(\gcd(a, m)\).

\( \begin{array}{rrrr|r} q & r & x & y \\ \hline & 91 & 1 & 0 \\ 0 & 143 & 0 & 1 \\ \hline 1 & 91 & 1 & 0 & 91 = 91 \times \phantom{(-} 1 \phantom{)} + 143 \times \phantom{(-} 0 \phantom{)} \\ 1 & 52 & -1 & 1 & 52 = 91 \times (-1) + 143 \times \phantom{(-} 1 \phantom{)} \\ 1 & 39 & 2 & -1 & 39 = 91 \times \phantom{(-} 2 \phantom{)} + 143 \times (-1) \\ & 13 & -3 & 2 & 13 = 91 \times (-3) + 143 \times \phantom{(-} 2 \phantom{)} \\ \end {array} \)

\(\gcd(\overset{a}{91}, \overset{m}{143}) = 13 = \overset{a}{91} \times (\overset{x}{-3}) + \overset{m}{143} \times \overset{y}{2}\)

But \(\gcd(91, 143) = 13 \nmid 84 = 2^2 \times 3 \times 7\).

Thus the linear congruence is insoluble.

ii

\(91x \equiv 84 \mod 147\)

Determine whether \(\gcd(91, 147) \mid 84\).

\( \begin{array}{rrrr|r} q & r & x & y \\ \hline & 91 & 1 & 0 \\ 0 & 147 & 0 & 1 \\ \hline 1 & 91 & 1 & 0 & 91 = 91 \times \phantom{(-} 1 \phantom{)} + 147 \times \phantom{(-} 0 \phantom{)} \\ 1 & 56 & -1 & 1 & 56 = 91 \times (-1) + 147 \times \phantom{(-} 1 \phantom{)} \\ 1 & 35 & 2 & -1 & 35 = 91 \times \phantom{(-} 2 \phantom{)} + 147 \times (-1) \\ 1 & 21 & -3 & 2 & 21 = 91 \times (-3) + 147 \times \phantom{(-} 2 \phantom{)} \\ 1 & 14 & 5 & -3 & 14 = 91 \times \phantom{(-} 5 \phantom{)} + 147 \times (-3) \\ & 7 & -8 & 5 & 7 = 91 \times (-8) + 147 \times \phantom{(-} 5 \phantom{)} \\ \end {array} \)

\( \begin{aligned} \gcd(91, 147) = 7 \mid 84 = \underbrace{2^2 \times 3}_{12} \times 7 = 12 \times (91 \times (-8) + 147 \times 5) = 91 \times (-96) + 147 \times 60 \\ \end {aligned} \)

\( \begin{aligned} 91x \equiv 84 \mod 147 & \quad \iff \quad 7.13x \equiv 7.12 \mod 7.21 \\ & \quad \iff \quad \phantom{7.} 13x \equiv \phantom{7.} 12 \mod \phantom{7.} 21 \\ \end {aligned} \)

Thus the general solution to the linear congruence is

\( \begin{aligned} x \equiv -96 \mod 21 & \quad \iff \quad 21k = x - (-96) \\ & \quad \iff \quad x = 21k - 96 \\ & \quad \iff \quad x = 21(k - 5) + 9 \\ & \quad \iff \quad x \equiv 9 \mod 21 \\ & \quad \iff \quad x \equiv 9, 30, 51, 72, 93, 114, 135 \mod 147 \\ \end {aligned} \)

print(13 *   9 %  21)
print(91 *   9 % 147)
print(91 *  30 % 147)
print(91 *  51 % 147)
print(91 *  72 % 147)
print(91 *  93 % 147)
print(91 * 114 % 147)
print(91 * 135 % 147)

12
84
84
84
84
84
84
84

3 - \(7n^3 - 1\) is not a perfect square#

Prove that

\(7n^3 - 1\)

can never be a perfect square.

Proof by contradiction

Suppose \(7n^3 - 1\) is a perfect square for some integer \(n\). Then there is an integer \(x\) such that

\( 7n^3 - 1 = x^2 \quad \iff \quad 7n^3 = x^2 - (-1) \quad \iff \quad x^2 \equiv -1 \equiv 6 \mod 7 \)

\( \begin{aligned} & 0^2 \equiv 0 \mod 7 && \quad (7k \phantom{+1})^2 = 7(7k^2) \\ & 1^2 \equiv 1 \mod 7 && \quad (7k + 1)^2 = 7(7k^2 + \phantom{1} 2k \phantom{+0}) + 1 \\ & 2^2 \equiv 4 \mod 7 && \quad (7k + 2)^2 = 7(7k^2 + \phantom{1} 4k \phantom{+0}) + 4 \\ & 3^2 \equiv 2 \mod 7 && \quad (7k + 3)^2 = 7(7k^2 + \phantom{1} 6k + 1) + 2 \\ & 4^2 \equiv 2 \mod 7 && \quad (7k + 4)^2 = 7(7k^2 + \phantom{1} 8k + 2) + 2 \\ & 5^2 \equiv 4 \mod 7 && \quad (7k + 5)^2 = 7(7k^2 + 10k + 3) + 4 \\ & 6^2 \equiv 1 \mod 7 && \quad (7k + 6)^2 = 7(7k^2 + 12k + 5) + 1 \\ \end {aligned} \)

\(\blacksquare\)

4 - \(a \equiv b \mod m_1, m_2 \iff a \equiv b \mod m_1 m_2\)#

Suppose that \(m_1, m_2 \in \mathbb{N}\), that \(\gcd(m_1, m_2) = 1\), and that \(a, b \in \mathbb{Z}\).

Prove that

\(a \equiv b \mod m_1\)

and that

\(a \equiv b \mod m_2\)

iff

\(a \equiv b \mod m_1 m_2\)

Proof

First Direction

We must show that if \(a \equiv b \mod m_1\) and \(a \equiv b \mod m_2\) then \(a \equiv b \mod m_1 m_2\).

Suppose

\( a \equiv b \mod m_1 \quad \iff \quad m_1 k \phantom{'} = a - b \\ a \equiv b \mod m_2 \quad \iff \quad m_2 k' = a - b \\ \)

We know that

\( \begin{aligned} \gcd(m_1, m_2) = 1 \quad \iff \quad \exists s, t \in \mathbb{Z} \quad 1 &= sm_1 + tm_2 \quad \iff \quad a - b = sm_1(a - b) + tm_2(a - b) \\ \end {aligned} \)

Thus

\( \begin{aligned} a - b &= s m_1 (m_2 k') + t m_2 (m_1 k) \\ &= m_1 m_2 (sk') + m_1 m_2 (tk) \\ &= m_1 m_2 (sk' + tk) \\ \end {aligned} \)

Second Direction

We must show that if \(a \equiv b \mod m_1 m_2\) then \(a \equiv b \mod m_1\) and \(a \equiv b \mod m_2\).

Suppose

\( a \equiv b \mod m_1 m_2 \quad \iff \quad m_1 m_2 k = a - b \quad \iff \quad \Big( m_1 (m_2 k) = a - b \land m_2 (m_1 k) = a - b \Big) \)

\(\blacksquare\)

5 - Solving simultaneous congruences#

Solve the simultaneous congruences

\( \begin{aligned} x & \equiv \phantom{1} 3 \mod \phantom{11} 6 \\ x & \equiv \phantom{1} 5 \mod \phantom{1} 35 \\ x & \equiv \phantom{1} 7 \mod 143 \\ x & \equiv 11 \mod 323 \\ \end {aligned} \)

We have

\( \begin{aligned} && M = \phantom{11} 6 \times \phantom{1} 35 \times 143 \times 323 & = 9699690 \\ m_1 = \phantom{11} 6 && M_1 = \phantom{111 \times} \phantom{1} 35 \times 143 \times 323 & = 1616615 \\ m_2 = \phantom{1} 35 && M_2 = \phantom{11} 6 \times \phantom{135 \times} 143 \times 323 & = \phantom{1} 277134 \\ m_3 = 143 && M_3 = \phantom{11} 6 \times \phantom{1} 35 \times \phantom{143 \times} 323 & = \phantom{11} 67830 \\ m_4 = 323 && M_4 = \phantom{11} 6 \times \phantom{1} 35 \times 143 \phantom{\times 323} & = \phantom{11} 30030 \\ \end {aligned} \)

and we must first solve

\( \begin{aligned} 1616615 N_1 & \equiv & 5 N_1 \equiv \phantom{1} 3 \mod \phantom{11} 6 \\ \phantom{1} 277134 N_2 & \equiv & 4 N_2 \equiv \phantom{1} 5 \mod \phantom{1} 35 \\ \phantom{11} 67830 N_3 & \equiv & 48 N_3 \equiv \phantom{1} 7 \mod 143 \\ \phantom{11} 30030 N_4 & \equiv & -9 N_4 \equiv 11 \mod 323 \\ \end {aligned} \)

\( \begin{aligned} \phantom{-1} 5 \times \phantom{1} 5 = \phantom{1} 25 \equiv 1 \mod \phantom{11} 6 \\ \phantom{-1} 9 \times \phantom{1} 4 = \phantom{1} 36 \equiv 1 \mod \phantom{1} 35 \\ \phantom{-1} 3 \times 48 = 144 \equiv 1 \mod 143 \\ -36 \times -9 = 324 \equiv 1 \mod 323 \\ \end {aligned} \)

\( \begin{aligned} N_1 & \equiv \phantom{-1} 15 & \equiv \phantom{11} 3 \mod \phantom{11} 6 \\ N_2 & \equiv \phantom{-1} 45 & \equiv \phantom{1} 10 \mod \phantom{1} 35 \\ N_3 & \equiv \phantom{-1} 21 & \mod 143 \\ N_4 & \equiv -396 & \equiv 250 \mod 323 \\ \end {aligned} \)

\( \begin{aligned} x &\equiv N_1 M_1 + N_2 M_2 + N_3 M_3 + N_4 M_4 \mod M \\ &= 3 \times 1616615 + 10 \times 277134 + 21 \times 67830 + 250 \times 30030 \\ &= 16553115 \\ &= 6853425 \mod 9699690 \\ \end {aligned} \)

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} \)

Contents