# 6.1200 Lecture 8 Notes

(For a more readable version on the web, see https://hackmd.io/@vinodnathan/S1CvKw3Cj)

Lecture 8-10: Number Theory.

What is number theory? The study of the integers $$\mathbb{Z} = \{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$$

One of the oldest fields of mathematics.

A quote from "A Mathematician's Apology": "We can rejoice that number theory's very remoteness from ordinary human activities should keep it gentle and clean". Hardy, being a pacifist, probably meant warfare and such that many fields of mathematics found applications in.

The strange irony: number theory is the basis of cryptography, the science of encrypted communications, crucial in ... warfare!

Speaking of Hardy, the story with Ramanujan. When Hardy visited Ramanujan in the hospital, he casually remarked that his cab number was 1729, to which Ramanujan said it's a most interesting number as it's the smallest number that can be written as a sum of two cubes in two different ways. Indeed, $1729 = 10^3 + 9^3 = 12^3 + 1^3$.

Number theory is a rich source of questions that are easy to state and insanely hard to solve. Examples:

* Goldbach's conjecture: every even integer > 2 can be written as the sum of two prime numbers. Has been shown to be true for all integers $\leq 4 \times 10^8$, but as we know, that's not a proof.
* Another example is the "twin primes conjecture": a recent string of progress was made by Yitang Zhang, James Maynard and others who showed that there are infinitely many primes that differ by at most 246.
* Yet another example is the Collatz Conjecture: simple but notoriously open. Checked up to $2^{68} \approx 3 \times 10^{20}$.
https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/

These do not constitute proofs. For example, the "Euler's sum of powers conjecture" says that there are no solutions to $x^4 + y^4 + z^4 = w^4$ in positive integers. Smallest counterexample known is $$95800^4+217519^4+414560^4=422481^4 = 31858749840007945920321$$

Careful: Proof by lack of counter-example is not a proof!

***Divisibility***

**Def 1** [Divisibility] $a | b$ ("a divides b", "b is a multiple of a", "b is divisible by a") if and only if $\exists k \in \mathbb{Z} \mbox{ s.t. } ak = b$.

E.g. $3 | 12$, $-5 | 100$.

Note that:
* $\forall n \in \mathbb{Z}, n | n$ and $n | 0$. Also, $0|0$.
* $n$ is even if $2 | n$. $0$ is even, $-2$ is even, etc.

Two facts that will become super useful:
* If $a | b$, then $a | cb$ for all $c \in \mathbb{Z}$.
* If $a | b$ and $a | c$, then $a | (b+c)$. Proof: $b = au$ and $c = av$, so $b+c = au + av = a(u+v)$.

Combining together the two facts above, we get:

**Lemma 1**: If $k|a$ and $k | b$, then for all integers $s$ and $t$, $k | as+bt$. If $k$ divides $a$ and $k$ divides $b$, then $k$ divides any **integer linear combination** of $a$ and $b$.

***Die Hard 3***

<< play clip from Die Hard 3 >> Simon Gruber (Jeremy Irons) is forcing John (Bruce Willis) and Zeus (Samuel L. Jackson) to prevent bombs from going off.

The problem: 3g jug and 5g jug, want to get exactly 4 gallons, just by pouring and *not guessing*. Who wants to help John and Zeus?

$$
(0,0) \stackrel{fill}{\rightarrow}
(0,5) \stackrel{pour}{\rightarrow}
(3,2) \stackrel{empty}{\rightarrow}
(0,2) \stackrel{pour}{\rightarrow}
(2,0) \stackrel{fill}{\rightarrow}
(2,5) \stackrel{pour}{\rightarrow}
(3,4)
$$

Another solution:

$$
(0,0) \stackrel{fill}{\rightarrow}
(3,0) \stackrel{pour}{\rightarrow}
(0,3) \stackrel{fill}{\rightarrow}
(3,3) \stackrel{pour}{\rightarrow}
(1,5) \stackrel{empty}{\rightarrow}
(1,0) \stackrel{pour}{\rightarrow}
(0,1) \stackrel{fill}{\rightarrow}
(3,1) \stackrel{pour}{\rightarrow}
(0,4)
$$

<<question>> How about if the problem is to make 5 gallons from a 6g and a 9g jug?

Oh no! :( All amounts are multiples of 3. Divisibility!

**Claim 2**: starting with a gallons and b gallons, if you get to a state (x,y), then x and y are integer linear combinations of a and b. // This is the invariant.

*Proof*: States are $(x,y)$, $0 \leq x \leq a$, $0 \leq y \leq b$. Start state is $(0,0)$.

A state $(x,y)$ can transition to another via the following actions:

i. Empty: $(0,y)$ or $(x,0)$.
ii. Fill: $(a,y)$ or $(x,b)$.
iii. Pour L to R: $(0,x+y)$ if $x+y \leq b$ or $(x+y-b,b)$ if $x+y > b$.
iv. Pour R to L: $(x+y,0)$ if $x+y \leq a$ or $(a, x+y-a)$ if $x+y > a$.

Predicate $P(x,y)$ is true of $x$ and $y$ are integer linear combinations of $a$ and $b$.
Prove that $P$ is invariant. Apply the invariant principle.
1. Start state: $P(0,0)$ is true.
2. Preserved across transitions: assume $P(x,y)$ and that $(x,y) \rightarrow (x',y')$. Prove that $P(x',y')$.
Let $x = sa + tb$ and $y = ua + vb$. (i) Empty transition: check; (ii) Fill: check; (iii) Pour L to R: x+y is an integer linear combination of a and b. So is x+y-b; (iv) Pour R to L: same argument.

So, P is true at the start and preserved across transitions. QED.

Unfortunate consequence: Bruce dies with 6 and 9 gallon jugs! Explains why 6, 9 can’t get to 5: every reachable amount has form 6s + 9t, which must be divisible by 3.

<<question>> How about 13g and 11g jugs? Can Bruce get to 5 gallons?

***Greatest Common Divisors (GCD)***

**Def**: GCD(a,b) is the largest integer that divides a and b.

gcd(6,9) = 3
gcd(5,12) = 1 --- so, 5 and 12 are relatively prime
gcd(18,0) = 18
gcd(n,0) = n
gcd(0,0) = undefined

gcd(a,b) = gcd(b,a)

Mother of all algorithms: Euclid's algorithm 300 BC.

Here is a key lemma.

**Lemma 3**: gcd(a,b) = gcd(a,b-a)

An example:
gcd(12,41) = gcd(12,29) = gcd(12,17) = gcd(12,5) = gcd(5,12) = gcd(5,7) = gcd(5,2) = gcd(2,5) = gcd(2,3) = gcd(2,1) = gcd(1,2) = gcd(1,1) = gcd(1,0) = 1

*Proof*: We will show that the following two sets are the same.
Set (X) of common divisors of a and b = Set (Y) of common divisors of a and b-a

$X \subseteq Y$: That is, we will show that if $k \in X$, then $k \in Y$. If $k \in X$, then $k$ divides $a$ and $k$ divides $b$. So, by Lemma 1, $k$ divides $b-a$.

$Y \subseteq X$: That is, we will show that if $k \in Y$, then $k \in X$. If $k \in Y$, $k$ divides $a$ and $k$ divides $b-a$. So, again by Lemma 1, $k$ divides $a + (b-a)$ = $b$.

QED.

What if the numbers involved are HUGE? $\gcd(1000002,5) = \gcd(999997,5) = \gcd(999992,5) = \gcd(999987,5) = \ldots$

Is there a shortcut? See the pattern and jump to the end --- division with remainders!

**Division theorem**: for all integers $n$ and $d$ with $d>0$, there is a unique pair of integers $q$ and $r$ s.t. (1) $n = qd + r$ and (2) $0 \leq r \leq d-1$.

q: quotient: n div d
r: remainder: n rem d

**Lemma 4**: Let $a \geq b$. Then, $\gcd(a,b) = \gcd(a, b\ \mathsf{rem}\ a)$.

Pf: Let b = qa+r, so r = b rem a. Then, gcd(a,b) = gcd(a, qa+r) = gcd(a, r) = gcd(a, b rem a), where the second equality is by repeated applications [hidden induction!] of Lemma 3.

**Euclid's algorithm**

"the granddaddy of all algorithms" --- Donald Knuth, The Art of Computer Programming Vol. 2

Start state: $(a,b)$, $a \geq b \geq 0$, not both 0.
Transition: $(x,y) \rightarrow (y, x\ \mathsf{rem}\ y)$ if $y > 0$.
If $y = 0$, stop and output $x$ as the gcd of a and b.

Example:
gcd(1001,777)
= gcd(777,224) [q=1]
= gcd(224,105) [q=3]
= gcd(105,14) [q=2]
= gcd(14,7) [q=7]
= gcd(7,0) [q=2]
= 7.

Maintains the invariant $P(x,y)=$ "gcd(x,y) is the same as gcd(a,b)"

Partial Correctness: gcd never changes. On termination, gcd(x,0) = x = gcd(a,b), so the output is the correct gcd of a and b.

Termination: $x \geq y$ is an invariant. In fact, after the first step, $x > y$. x+y is strictly decreasing because $x\ \mathsf{rem}\ y < x$ when $x \geq y$. So, the number of steps is at most $a+b$.

**Can get much more: Euclid\'s algorithm is much faster!**

**Claim**: $x\ \mathsf{rem}\ y < x/2$.

*Proof*: Consider the following exhaustive cases. [Do you see why there are no other cases to consider?]
Case (1) $x \geq 2y$. Then, $x\ \mathsf{rem}\ y < y \leq x/2$. So, $x \ \mathsf{rem}\ y < x/2$ is true.
Case (2) $y \leq x < 2y$. Then, $x\ \mathsf{rem}\ y = x-y < x - x/2 = x/2$.
So the total number of bits decreases by at least 1 every step. The number of steps is therefore the number of bits of a + number of bits of b at the start.

**All numbers are linear combinations of a and b, and so is the gcd**! In the example above:

a = 1001
b = 777
224 = 1001 - 1*777 = a - b
105 = 777 - 3*224 = b - 3(a-b) = -3a + 4b
14 = 224 - 2*105 = a-b - 2(-3a+4b) = 7a - 9b
7 = 105 - 7*14 = -3a + 4b - 7(7a-9b) = -52a + 67b

**Theorem [Bezout Identity]** gcd(a,b) is an integer linear combination of a and b.

Extended Euclidean Algorithm (also known as the pulverizer). A version of this was called Kuttaka [Sanskrit for pulverization]. Attributed to Aryabhata, ~ 500 CE.

**Corollary**: A number can be written as an integer linear combination of a and b if and only if it is a multiple of gcd(a,b).

*Proof*: ("Only if") Every linear combination of a and b is divisible by any number that divides both a and b, and therefore by gcd(a,b). ("If") Conversely, since gcd(a,b) can be written as an integer linear combination of a and b, so can every multiple of gcd(a,b).

**Corollary**: gcd(a,b) is the smallest positive integer that can be written as an integer linear combination of a and b.

*Proof*: let g = gcd(a,b). The set of integers that can be written as an i.l.c. of a and b is {-3g, -2g, -g, 0, g, 2g, ...}. The least positive integer in this set is g.