# 6.1200 Lecture 9 Notes

For a more readable version of this note, please see https://hackmd.io/@vinodnathan/ryRXPtby3

****Finishing up Euclid's Algorithm****

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

*The Algorithm*

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$.

1. **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.

2. **Can get much more: 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.

========================================================

Moving on...

****Modular Arithmetic****

* What is even + odd? (odd --- mod $2$ arithmetic)
* What is the last digit of $324\cdot 512$? ($8 = 4\cdot 2$ --- mod $10$ arithmetic)
* It is currently $3$pm. What time will it be in 50 hours? (5pm because 50 is two days + two hours --- mod $24$ arithmetic)
* Today is Tuesday. What day of the week will it be 100 days from now? (Thursday because $10\ \mathsf{rem}\ 7 = 2$ and Tue + 2 = Thu --- mod $7$ arithmetic)

These are all examples of modular arithmetic in action. The motto is *ignore multiples of $n$, focus on remainders*.

**Definition 1** We say that $a \equiv b \bmod n$ ("a is congruent to b modulo n") if and only if $n | (a-b)$.

We think of $a$ and $b$ as the same when their difference is a multiple of $n$.

For example, there are only three different values when looking mod $3$:
$$\{ \ldots, -6, -3, 0, 3, 6, 9, \ldots\}$$ $$\{ \ldots, -5, -2, 1, 4, 7, 10, \ldots\}$$ $$\{ \ldots, -4, -1, 2, 5, 8, 11, \ldots\}$$
For a general number $k$, which group does it belong to? Just look at $k\ \mathsf{rem}\ 3$. If we write $k = 3q+r$, then $k \equiv r \bmod 3$ because $k-r = 3q$, which is a multiple of $3$.

Recall the division theorem.

**Theorem 1** For all pairs of integers $k$, $n$ with $n > 0$, there exists a unique pair of integers $q,r$ where $k = qn+r$ and $0 \leq r < d$. The number $q = k \ \mathsf{div}\ n$ is the quotient, and $r = k\ \mathsf{rem}\ n$ is the remainder.

When working modulo $n$, a number $k$ is always congruent to its remainder: if $k = nq + r$, then $n|nq=k−r$,so $k\equiv r \bmod n$. Claim: the $n$ remainders $0,1,\ldots,n−1$ represent all the possible "groupings" (aka "equivalence classes") mod $n$.

**Theorem 2**. $a \equiv b \bmod n$ if and only if $a\ \mathsf{rem}\ n = b\ \mathsf{rem}\ n$.

*Proof* If $a\ \mathsf{rem}\ n = b\ \mathsf{rem}\ n = r$, then $a = nq + r$ and $b = nq'+r$ for integers $q$ and $q'$. So, $a-b = n(q-q')$ which is a multiple of $n$. Therefore, $a \equiv b \bmod n$.

Conversely, suppose $a \equiv b \bmod n$. Then, $a-b = nq$ for some integer $q$. Write $b = nq'+r$ by the division theorem, where $0 \leq r < n$, so that $r = b\ \mathsf{rem}\ n$. Then, $a = b + nq = n(q+q') + r$. By the uniqueness guaranteed by the division theorem, $r = a\ \mathsf{rem}\ n$. Thus, $a\ \mathsf{rem}\ n = b\ \mathsf{rem}\ n$.

QED.

So the $n$ different remainders when dividing by $n$ divide the integers $\mathbb{N}$ into $n$ different groups, identified by their remainders. Can think of $0, 1,\ldots, n−1$ as the only possible values mod $n$, and all other numbers are congruent to one of these.

****Putting the Arithmetic in Modular Arithmetic: Addition, Subtraction, Multiplication****

The simple statement even+odd=odd says something profound: "no matter which even number and odd number we add, the result is always odd". This generalizes: "if we pick any number $a \equiv 2 \bmod 5$ and any number $b \equiv 4 \bmod 5$, adding them will always produce a number $a+b \equiv 6 \equiv 1 \bmod 5$.

**Theorem 3**. If $a \equiv a' \bmod n$, then for any $b$,
* $a + b \equiv a' + b \bmod n$
* $a-b \equiv a'-b\bmod n$
* $ab \equiv a'b \bmod n$.

*Proof*
$a' = a+sn$. Then $(a'+b)−(a+b) = sn$, a multiple of $n$. So, $a'+b \equiv a+b \bmod n$. Similarly for subtraction.

Likewise, $a'b−ab = (a + sn)b − ab = bsn$, another multiple of $n$.

QED.

When adding, subtracting or multiplying, can replace $a$ by anything it is congruent to mod $n$, without changing the result mod $n$.

True for the **base** of exponents as well:

**Theorem 4**. If $a \equiv a' \bmod n$, then for any $k \geq 0$, $a^k \equiv (a')^k \bmod n$.

*Proof*
This is just repeated multiplication, so apply the previous lemma $k$ times: $a \cdot a \cdots a \equiv a' \cdot a' \cdots a' \bmod n$.

QED.

**Warning**: The same is not true for the exponent $k$. E.g., $1 \equiv 6 \bmod 5$, but $2^1 \neq 2^6 \bmod 5$ (they have remainders $2$ and $4$, respectively).

Let’s see an example: What are the last two digits of
$$x := 11335^{11111}(6 + 7799^{5000})?$$ That’s the same as asking for x rem 100.

**General strategy**: replace intermediate calculations with their remainders, as early and often as we can. This helps us work with smaller numbers.

So $x \equiv 35^{11111}(6 + 99^{5000}) \bmod 100$.

(Not allowed to just reduce the exponents mod 100, as we just saw.)

For the right exponent, $99 \equiv −1 \bmod{100}$, so

$$99^{5000} \equiv (−1)^{5000} \equiv 1 \bmod 100.$$

For the left term, look for a pattern:
$$35^1 \equiv 35 \bmod 100$$ $$35^2 \equiv 25 \bmod 100$$ $$35^3 \equiv 25·35 \equiv 75 \bmod 100$$ $$35^4 \equiv 75\cdot 35 \equiv 25 \bmod 100.$$

Will continue bouncing between $25$ and $75$. So $35^{11111} \equiv 75 \bmod 100$. We find
$$x \equiv 75 \cdot (6 + 1) \equiv 25 \bmod 100$$ so this must be the remainder.

****Important: Notation****

*Remainder.* Remainder can be notated as $a\ \mathsf{rem}\ n$ or $\mathsf{rem}(a, n)$ or $a \bmod n$. Recall that $n$ is always positive, but $a$ can be positive or negative.

Many languages have the modulo operator $a\%n$ which generally behaves like our rem, but not always! By our def, $a\ \mathsf{rem}\ n$ is always nonnegative, even when $a$ is negative: for example, $(−43\%10) = 7$.

* Python and Mathematica agree with us.
* But many other languages think negative $a$ values should have negative remainders: Javascript and C/C++, for example, will set $(−43\%10) = −3$.
* And some have both, with two different names, e.g., CoffeeScript (% vs %%), Lisp (mod vs rem), Fortran (mod vs modulo), Haskell (mod vs rem).

Oy vey!

*For this class, any version of remainder we use will always mean the nonnegative one.*

*$a \bmod n$.* What does $a = b \bmod n$ mean? Does it mean $a\equiv b \bmod n$? Or does it mean $a=(b \bmod n)$,i.e.,$a=b\ \mathsf{rem}\ n$? Due to this ambiguity, we will never use $a = b \bmod n$, but always $a \equiv b \bmod n$.

The difference is this: $a \bmod n$ is a function, with a single definite value, namely $a\ \mathsf{rem}\ n$. Always between $0$ and $n−1$.

But $a \equiv b \bmod n$ is a relationship between two quantities. Neither needs to be between $0$ and $n−1$. E.g., $12 \equiv 17 \bmod 5$ is a true statement. Their remainders are $(12 \bmod 10) = 2$ and $(17 \bmod 5) = 2$ which are equal (necessarily so, by Theorem 2 above.)

****Division****

Addition, Subtraction, Multiplication, and bases of exponents can be substituted mod $n$ (but not the exponents).

Can we divide mod $n$? Hmm... $3 \cdot 2 \equiv 3 \cdot 4 \bmod 6$. Can we "divide both sides by 3" and conclude that $2 \equiv 4 \bmod 6$? No!

A multiplicative inverse of $x$ is a number you can multiply $x$ by to get $1$. In $\mathbb{R}$, the multiplicative inverse of $3$ is $1/3$, because $3 \cdot 1/3 = 1$. If "1/3" made sense mod 6, then we could multiply both sides by 1/3 to conclude that $2 \equiv 4 \bmod 6$. So $3$ doesn't have a multiplicative inverse mod 6.

When do mod $n$ inverses exist for a number $a$?

**Theorem 5**. $a$ has an inverse mod $n$ if and only if $\mathsf{gcd}(a, n) = 1$.

*Proof* $a$ has an inverse mod $n$ IFF there exists $b$ such that $ab\equiv 1 \bmod n$ IFF there exists $b$ and $q$ such that $ab−1 = nq$. i.e. $ab−nq = 1$ IFF $1$ is a linear combination of $a$ and $n$. By Bezout, this last part happens IFF $\mathsf{gcd}(a, n) = 1$. QED.

**Corollary 6**. If $p$ is prime and $a \not\equiv 0 \bmod p$, then $a$ has an inverse mod $p$.

*Proof* $\mathsf{gcd}(a,p)$ must be $p$ or $1$. Since $a \not\equiv 0 \bmod p$, $p$ does not divide $a$ and therefore the gcd is $1$. Now apply the previous result. QED.

Having a multiplicative inverse means we "can cancel from both sides" or "divide" by that amount. e.g. $7$ and $13$ are inverses of each other mod $30$. If we know $7x \equiv 14 \bmod 30$, can we conclude that $x \equiv 2 \bmod 30$? Instead of dividing, let's multiply both sides by 13:
$$ 7x \equiv 14 \bmod 30$$ $$13 \cdot 7x \equiv 13 \cdot 14 \bmod 30$$ $$(13\cdot 7)x \equiv (13 \cdot 7) \cdot 2 \bmod 30$$ $$ (1)x \equiv (1) \cdot 2 \bmod 30.$$

So, since $7$ has a multiplicative inverse, we can indeed "cancel it from both sides".

Important fact:

**Theorem 7 (Fermat's little theorem)**: If p is prime, and a is not a multiple of p, then
$$a^{p-1} \equiv 1 \bmod{p}.$$

(Not to be confused with Fermat’s **Last** Theorem. Very different, much harder to prove.)

Example 1: $p=7, a=4$, $a^{p-1} = 4^6 \equiv 2^3 \equiv 8 \equiv 1 \pmod 7$ as Fermat's little theorem predicts.

Example 2: It is crucial that $p$ is prime. For example, if $p=8$, $a=3$, we have $a^{p-1} = 3^7 \equiv 3*(3^2)^3 \equiv 3*1^3 \equiv 3 \pmod 8$. // Make sure you understand how each of these steps in this calculation is accomplished.

Example 3: It is also crucial that $a$ is not a multiple of $p$. For example, if $p=3$ and $a=3$, then $a^{p-1} = 3^{2} \equiv 0 \pmod 3$.

**Proof**: Look at $a, 2a, 3a,\ldots, (p-1)a$ all modulo $p$. In example 1 above, they are $[4, 1, 5, 2, 6, 3]$. All within $1$ and $p-1$ of course, but you see a curious pattern: these numbers are a permutation of $[1, 2, 3, 4, 5, 6]$. Hmm...

We will start by showing that the numbers $a, 2a, 3a,\ldots, (p-1)a$ are all different modulo $p$. Suppose that two of these multiples are the same modulo $p$. That is, $ia \equiv ja \bmod p$. Since $\mathsf{gcd}(a,p) = 1$, $a$ has a multiplicative inverse. Multiplying both sides by $a^{-1} \bmod p$, we have $i \equiv j \bmod p$. So, these two numbers weren't distinct multiples after all. So, all the distinct multiples of $a$ modulo $p$ are distinct.

In other words:
$$\{a, 2a, ..., (p-1)a\} = \{1, 2,..., p-1\}$$

Multiplying all the elements of each set together, we have
$$a^{p-1} (p-1)! \equiv (p-1)! \bmod p$$

Does $(p-1)!$ have an inverse mod $p$? Yes! [Prove it!] [Bonus points if you can guess what the inverse is!]

Multiplying both LHS and RHS by $((p-1)!)^{-1} \bmod p$ gives us the desired outcome:
$$a^{p-1} \equiv 1 \bmod p.$$

***Application:*** How to compute $2029^{2029} \bmod 2027$. You are told that $2027$ is a prime number.

First, reduce the base mod 2027. So,
$$ 2029^{2029} \equiv 2^{2029} \bmod 2027$$
Next, note that $2^{2029} \equiv 2^3 * 2^{2026} \bmod 2027$ and that $2^{2026} \equiv 1 \bmod 2027$, the latter using Fermat's little theorem. So,
$$ 2029^{2029} \equiv 2^{2029} \equiv 2^3 \equiv 8 \bmod 2027$$