Number Theory
===
###### tags: `215` `discrete`

# Divisibility and modular arithmetic
**Definition**: For $n$ and $m$ integers, *$n$ divides $b$*, written $n|b$, means $b=q\cdot n$ for some integer $q$.

**Euclidean Algorithm**: For integers $n$ and $m\ge 2$, there are unique integers $q$ and $r$ with $0\le r< m$ satisfying
$$
n=q\cdot m+r\quad\text{ or }\quad \frac{n}{m}=q+\frac{r}{m}
$$
We write $q=n \mathop{\text{div}} m$ and $r=n\bmod m$.

**Proof**

**Uniqueness** Suppose $n=q_1\cdot m+r_1=q_2\cdot m+r_2$ with $0\le r_1,r_2<m$. Suppose $r_1 \neq r_2$. WLOG assume $r_1<r_2$. Then $n-n=(q_2-q_1)\cdot m+(r_2-r_1)$, so $0<r_2-r_1=(q_1-q_2)\cdot m<m$, but then $q_1-q_2=0$ and thus $r_2-r_1=0$. Contradiction!

So $r_1=r_2$, then $n-n=(q_1-q_2)\cdot m=0$ so $q_1=q_2$. Thus $(q_1,r_1)=(q_2,r_2)$.

**Existence** Suppose $n\ge 0$ is such that $n\neq q\cdot m+r$ for some $0\le r<m$. We see that $m\le n$ as otherwise $n=0\cdot m+n$ and $0\le n<m$. Suppose $n-m=q\cdot m+r$, then $n=(q+1)\cdot m+r$. Thus $n-m$ also has no representation ans we get a descending sequence $n>n-m>n-2m\cdots$ all satisfying $n-k\cdot m\ge 0$ and $n\neq q\cdot m+r$. This can't happen. (You could use induction, well-ordering, etc.)

**Examples**:
* $119 = 13\cdot 9+2$ so $119 \mathop{\text{div}} 9=13$ and $119 \bmod 9 = 2$.
* $-119 = -14\cdot 9 + 7$ so so $-119 \mathop{\text{div}} 9=-14$ and $-119 \bmod 9 = 7$.

Note: $-119=-13\cdot 9-2=\boxed{-14\cdot 9+7}$, but the remainder must be non-negative, so the 2^nd^ form is the one used. Without this condition, the quotient and remainder are not unique.

Define an *equivalence relation* on $\mathbb Z$ by
$$
a\equiv b \pmod n\iff a\bmod n=b\bmod n
$$
This is more than an equivalence relation, it is a *congruence relation* since algebraic operations are preserved. In particular for $a\equiv a'\pmod n$ and $b\equiv b'\pmod n$ we have:
$$
\begin{align}
a+b &\equiv a'+b' \pmod n\\
a\cdot b &\equiv a'\cdot b'\pmod n\\
-a &\equiv -a'\pmod n
\end{align}
$$
The equivalence clases are $\bar m=m+n\mathbb Z$ for $0\le m<n$. We write
$$
\mathbb Z_n=\{\bar 0,\bar 1,\ldots,\overline{n-1} \}
$$
and consider $+_n$, $\cdot_n$, and $-_n$ defined on this set defined by
$$
\begin{align}
\bar i +_n\bar j&=\overline{(i+j)\bmod n}\\
\bar i \cdot_n\bar j&=\overline{(i\cdot j)\bmod n}\\
-_ni &= \overline{(-i) \bmod n}=\overline{n-i}
\end{align}
$$
When the context make it clear, the subscript will be omitted.

**Exercise**: Make the multiplication and addition tables for $\mathbb Z_7$, notice additional patterns.

The structure $\langle \mathbb Z_n,+_n,\cdot_n,-_n,\bar 0, \bar 1\rangle$ satisfies the following axioms of a *commutative ring with unity*:

**Additive Axioms**
* $+_n$ is associative: $(\bar a+_n \bar b)+_n\bar c=\bar a+_n(\bar b+_n\bar c)$.
* $+_n$ is commutative: $\bar a+_n\bar b=\bar b+_n\bar a$.
* $\bar 0$ is the additive identity: $\bar 0+_n\bar a=\bar a=\bar a+_n \bar 0$.
* $-_n\bar a$ is the aditive inverse of $\bar a$: $\bar a+_n(-_n\bar a)=\bar 0=(-_n\bar a)+_n\bar a$.

**Multiplicative Axioms**
* $\cdot_n$ is associative:$(\bar a\cdot_n \bar b)\cdot_n\bar c=\bar a\cdot_n(\bar b\cdot_n\bar c)$.
* $\cdot_n$ is commutative: $\bar a\cdot_n\bar b=\bar b\cdot_n\bar a$.
* $\bar 1$ is the multiplicative identity: $\bar 1\cdot_n\bar a=\bar a=\bar a\cdot_n\bar 1$.

**Mixed Axioms**
* $\cdot_n$ distributes over $+_n$: $\bar a\cdot_n(\bar b+_n\bar c)=(\bar a\cdot_n \bar b)+_n(\bar a\cdot_n\bar c)$.

We will see later that for $p$ a prime, $\mathbb Z_p$ also has multiplicative inverses, and is called a *(number) field*. Look at the exercise above, note how you can see commutativity as symmetry, you can see the identities and inverses.

**Exercise**: Prove distributivity.

# Integer representations

I will let you read and ask questions about use of different bases to represent integers. There is nothing difficult here. I do want to comment on modular exponentiation.

## Modular Exponential

Given the way modular arithmetic works one might expect

$$
r^s \bmod n=(r\bmod n)^{(s\bmod n)} \bmod n
$$
But this it turns out is false, for example, $5^7\bmod 7=5$ while
$$
(5\bmod 7)^{(7\bmod 7)}\bmod 7=5^0 \bmod 7=1\bmod 7.
$$
Nevertheless, modular exponentiation is critical in cryptography. For example, we might want to compute, $191^{131} \bmod 1707$. What can we do? Here is a common way to do this that is fast an avoids overly large numbers, it is also reminiscent of how ancient Egyptians (~2000 B.C.E) did multiplication.

| $191^m \bmod 17$ | m | Explanation|
| :-----------------: | :-----:| ---------- |
| $191$ | $1$ | $191^1\bmod 1707=191$|
| $634$ | $2$ | $191^2\bmod 1707=634$|
| $811$ | $4$ | $191^4\bmod1707=\\(191^2\bmod 1707)(191^2\bmod 1707)\bmod1707=\\(634)(634)\bmod 17=811$|
|$526$|$8$|$191^8\bmod 1707=\\(191^4\bmod 1707)(191^4\bmod 1707)\bmod 1707=\\(811)(811)\bmod 1707=526$|
|$142$|$16$|$191^{16}\bmod 1707=\\(191^8\bmod 1707)(191^8\bmod 1707)\bmod 1707=\\(526)(526)\bmod 1707=142$|
|$1387$|$32$|$191^{32}\bmod 1707=\\(191^{16}\bmod 1707)(191^{16}\bmod 1707)\bmod 1707=\\(142)(142)\bmod 1707=1387$|
|$1687$|$64$|$191^{64}\bmod 1707=\\(191^{32}\bmod 1707)(191^{32}\bmod 1707)\bmod 1707=\\(1387)(1387)\bmod 1707=1687$|
|$400$|$128$|$191^{128}\bmod 1707=\\(191^{64}\bmod 1707)(191^{64}\bmod 1707)\bmod 1707=\\(1687)(1687)\bmod 1707=400$

Now $131=128+2+1=2^7+2^1+2^0=(1000\,0011)_2$ and so
$$
191^{131}\bmod 1707 =191^{128}\cdot 191^2\cdot 191^1\bmod 1707
$$
and we have:
$$
191^{131}\bmod 1707=400\cdot 634\cdot 191\bmod 1707=1475
$$

**Exercise**: Try doing this some other way.

# Primes, GCD, and Modular inverses

**Definition**: $p$ is *prime* iff whenever $p=ab$, then $a=1$ or $b=1$.

Actually, a better definition for prime would be: $p|ab\implies p|a\vee p|b$. We will prove this below.

When checking if a number is a prime note that you need only check factors up to $\lceil\sqrt{n}\rceil$.

**Example**: Is $1709$ prime?

You just check, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 73, 41, since $\sqrt{1707}=41.34...$ you may stop at 41, since 42 is not a prime. This done, you know 1709 is prime.

**The Fundamental Theorem of Arithmetic**: Every positive integer can be written as the product of primes and this product is unique up to the order of factors.

**Example:** Write $61425$ as the product of primes.

The usual thing is to just go through the primes factoring along the way. Note that $2\!\not|\,61425$, but $3|61425$, since $6+1+4+2+5=18$ and $3|18$, so $61425=20475$. Again $2+0+4+7+5=18$ so $3|20475$ and $61425=3^2\cdot 6825$. Yet one more time this is true and $61425=3^3\cdot 2275$. Now we are done with 3, so go on to 5, etc. In the end we get $61425=3^3\cdot 5^2\cdot 7\cdot 13$. Now except for ordering of the factors, this is the unique prime factorization of $64125$.

**Definition**: The *greatest common divisor* of integers $a$ and $b$ is denoted $\gcd(a,b)$ (sometimes just $(a,b)$) and is defined as the greatest positive integer that divides both $a$ and $b$. The *least common multiple* or $\text{lcm}(a,b)$, is the least integer divisible by bot $a$ and $b$.

It is clear that if $d=\gcd(a,b)$, then $a=a'd$ and $b'=b'd$ and
$$
ab=(a'db')(d)=\text{lcm}(a,b)\cdot\gcd(a,b).
$$

Using the fundamental theorem of algebra it is easy to find $\gcd(a,b)$ and $\text{lcm}(a,b)$ if you have the prime factorizations of $a$ and $b$ in hand.

**Example**: Find $\gcd(61425, 83655)$.

So factor and get $61425=3^3\cdot 5^2\cdot 7\cdot13$ and $83655=3^2\cdot5\cdot11\cdot13^2$ so it is clear that
$$
\begin{align}
\gcd(61425,83655)&=3^2\cdot5\cdot13=3^{\min(3,2)}\cdot5^{\min(2,1)}\cdot7^{\min(1,0)}\cdot11^{\min(0,1)}\cdot13^{\min(1,2)}\\
\text{lcm}(61425,83655)&=3^3\cdot5^2\cdot7\cdot11\cdot13^2=3^{\max(3,2)}\cdot5^{\max(2,1)}\cdot7^{\max(1,0)}\cdot11^{\max(0,1)}\cdot13^{\max(1,2)}
\end{align}
$$
The problem with this is that factoring is **hard** and this is the basis of much cryptography. There is a better way to find the gcd of $a$ and $b$.

**Lemma**: Suppose $a\ge b\ge 0$, then $\gcd(a,b)=\gcd(b,a\bmod b)$.

**Proof**: Suppose $d|a\wedge d|b$, then if $a=q\cdot b+r$ where $r=a\bmod b$, then $d|a\implies d|(q\cdot b+r)$. But $d|b\implies d|(q\cdot b+r)\implies d|r$. So $d|a\wedge d|b\implies d|b\wedge d|(a\bmod b)$. The other direction is easier, namely $d|b\wedge d|(a\bmod b)\implies d|a\wedge d|b$, so we have in the end
$$
d|b\wedge d|(a\bmod b)\iff d|a\wedge d|b
$$
The lemma now clearly follows.

Notice that if we set $r_1=a>r_2=b>r_3=a\bmod b>\cdots$, then we get $r_1>r_2>r_3>\cdots\ge 0$ so eventually this must stop with
$$
\gcd(a,b)=\gcd(r_1,r_2)=\gcd(r_2,r_3)=\cdots=\gcd(r_{n-1},r_n)=r_n\text{, i.e., }r_{n-1}\bmod r_n=0
$$

**Example**: Find $\gcd(61425,83655)$ using this method.

$$
\begin{align}
\gcd(83655, 61425)&=\gcd(61425,83655\bmod 61425)=\gcd(61425, 22230)\\
&=\gcd(22230, 61425\bmod 22230)=\gcd(22230,16965)\\
&=\gcd(16965,22230\bmod 16965)=\gcd(16965,5265)\\
&=\gcd(5265,16965\bmod 5265)=\gcd(5265,1170)\\
&=\gcd(1170, 5265\bmod 1170)=\gcd(1170,585)\\
&=\gcd(585,1170\bmod 585)=\gcd(585, 0)=585
\end{align}
$$

By analyzing the algorithm above we get a very useful fact and algorithm.

**Theorem** (Bezout): If $\gcd(a,b)=d$, then there are unique integers $s$ and $t$ so that $sa+tb=d$.

**Proof**: Assume WLOG that $a>b$ and call $a=r_0$ and $b=r_1$ as above. Define then $r_i$ as we did above so that $r_i=r_{i-2}\bmod r_{i-1}$. We shall construct $s_i$ and $t_i$ so that $r_i=s_ia+t_ib$. Since the eventual $d=r_{n-1}$ where $r_n=0$, this proves the lemma. Let $q_{i-1}=r_{i-2}\mathop{\text{div}}r_{i-1}$. Suppose we have $s_{j}$ and $t_j$ as desired for $j<i$, then we have:
$$
r_{i-2}=q_{i-1}\cdot r_{i-1}+r_i\text{ so }r_i=r_{i-2}-q_{i-1}r_{i-1}
$$
But we know $r_{i-2}=s_{i-2}a+t_{i-2}b$ and $r_{i-1}=s_{i-1}a+t_{i-1}b$ so
$$
r_i=(s_{i-2}a+t_{i-2}b)-q_{i-1}(s_{i-1}a+t_{i-1}b)=(s_{i-2}-q_{i-1}s{i-1})a+(t_{i-2}-q_{i-1}t_{i-1})b
$$
We have a recurrence:
$$
[s_1,t_1]=[1,0], [s_2,t_2]=[0,1], \text{ and }[s_i,t_i]=[s_{i-2},t_{i-2}]-q_{i-1}[s_{i-1},t_{i-1}]
$$
where $q_{i-1}=\lfloor r_{i-2}/r_{i-1}\rfloor$.

Let's run this on the preceding example:

|$i$ |$r_i$ |$q_i$ |$s_i$ |$t_i$ |Explanation |
|:--:|:-----:|:-----:|:-----------------|:------------------|:---------------------------|
|$1$ |83655 |NA |$1$ |$0$ | |
|$2$ |61425 |1 |$0$ |$1$ |$83655=1\cdot 61425 + 22230$|
|$3$ |22230 |2 |$1=1-1\cdot 0$ |$-1=0-1\cdot 1$ |$61425=2\cdot 22230 + 16965$|
|$4$ |16965 |1 |$-2=0-2\cdot 1$ |$3= 1-2\cdot(-1)$ |$22230=1\cdot 16965+5265$ |
|$5$ |5265 |3 |$3=1-1\cdot(-2)$ |$-4=-1-1\cdot(3)$ |$16965=3\cdot5265+1170$ |
|$6$ |1170 |4 |$-11=-2-3\cdot(3)$|$15=3-3\cdot(-4)$ |$5265=4\cdot 1170+585$ |
|$7$ |585 |2 |$47=3-4\cdot(-11)$|$-64=-4-4\cdot(15)$|$1170=2\cdot585+0$ |[]

You can check that $585=(47)\cdot (83655)+(-64)\cdot(61425)$.

**Definition**: Integers $a$ and $b$ are relatively prime iff $\gcd(a,b)=1$

If $\gcd(a,b)=1$, then we know $sa+tb=1$, so $sa=-tb+1$, this means $sa\equiv 1\pmod b$. Conversely, if $as=qb+1$, then $a$ and $b$ are relatively prime, for suppose $d|a$ and $d|b$, then $d|qa$ and hence $d|qb+1$, but then $q|1$, so $q=1$. We have shown that the following are equivalent:
* $a$ and $b$ are relatively prime.
* $\gcd(a,b)=1$.
* There is $s$ and $t$ so that $sa+tb=1$.
* $a$ is *invertible modulo b*, that is, there is a $c$ so that $ca\equiv 1\pmod b$.

Invertibility modulo some number will be important in applications. What we have done above shows how to find $a^{-1}\bmod n$ in the case that $a$ and $n$ are relatively prime.

A corrolary of Bezout's Theorem is another familiar property of primes: If $p$ is prime and $p|ab$, then $p|a$ or $p|b$. Your text offers a slightly more general result:

**Corollary**: If $a$ and $b$ are relatively prime and $a|bc$, then $a|c$.

**Proof**: We find $s$ and $t$ so that $sa+tb=1$, so $c=sac+tbc$. Since $a|sac$ and $a|tbc$, it follows that $a|c$.

This implies the fact about primes, since if $p$ is prime and $p\!\not|\,a$ we know $p$ and $a$ are relatively prime. If $p|ab$, then from the corollary, $p|b$. Thus if $p|ab$, then either $p|a$ or, if not, $p|b$.

Note that in general *cancellation* fails $\pmod n$. For example, $7\cdot 2\equiv 4\cdot 2\pmod 6$, yet $7\not\equiv 4\pmod 6$. However, as a corollary to the above

**Corollary**: If $\gcd(c,n)=1$ and $ca\equiv cb\pmod n$, then $a\equiv b\pmod n$.

**Proof**: We have $n|c\cdot (a-b)$, since $n|(ca-cb)$.

## Solving Congruences

A *linear congruence* is a linear equation in $\mathbb Z_n$ for some $n$. In general, a linear congruence looks like:
$$
ax\equiv b\pmod n
$$
If $\gcd(a,n)=1$, then we know that we can find $a^{-1}\bmod n$ and hence can solve this as:
$$
a^{-1}ax\equiv x \equiv a^{-1}b \pmod n.
$$
**Example**: Solve $83x\equiv 2\pmod {467}$.

**Check that $\gcd(467,83)=1$**:

$$
\gcd(467,83)=\gcd(83,52)=\gcd(52,31)=\gcd(31,21)=\gcd(21,10)=\gcd(10,1)=1
$$
You might have noticed from the start that 83 is prime, or that 31 is prime and stopped earlier.

**Find $s,t$ so that $s83+t467=1$**: We have $467=5\cdot 83+52$ so, in the previous notation,
* $r_1=467$, $s_1=1$, $t_1=0$
* $r_2=83$, $s_2=0$, $t_2=1$, $q_2=5$
* $r_3=52$, $s_3=1-5\cdot(0)=1$, $t_3=0-5\cdot(1)=-5$, $q_3=1$
* $r_4=31$, $s_4=0-1\cdot(1)=-1$, $t_4=1-1\cdot(-5)=6$, $q_4=1$
* $r_5=21$, $s_5=1-1\cdot(-1)=2$, $t_5=-5-1\cdot(6)=-11$, $q_5=1$
* $r_6=10$, $s_6=-1-1\cdot(2)=-3$, $t_6=6-1\cdot (-11)=17$, $q_6=2$
* $r_7=1$, $s_7=2-2\cdot(-3)=8$, $t_7=-11-2\cdot(17)=-45$, $q_7=10$
* $r_8=0$ **STOP**

So $-45\cdot 83\equiv -8\cdot 467+ 1\pmod {467}$, that is $-45\cdot 83\equiv 1\pmod {467}$. Thus
$$
-45\equiv 83^{-1}\pmod {467}.
$$
Recalling that $-45\equiv 467-45=422\pmod {467}$, so staying in $\mathbb Z_{467}$ we have
$$
83^{-1}\equiv 422\pmod {467}.
$$

So we can solve the equation: $83x\equiv 2\pmod {467}\iff x\equiv 422\cdot 2 \equiv 377 \pmod {467}$.

### Chinese Remainder Theorem

Here is a [nice paper](https://ketchers.github.io/Teaching/525/Kangsheng.pdf) with some good history of this topic. One problem goes as:

> *Sun Zi suanjiing* (Volume 3; Problem 26) (3^rd^ to 5^th^ century C.E.) A number is repeatedly divided by 3, the remainder is 2; divided by 5, the remainder is 3; divided by 7, the remainder 2. What is the number?

* Count by $35=5\cdot 7$ until a number is reached with remainder $1 \bmod 3$. The smallest such number is $G_3=70$.
* Count by $21=3\cdot 7$ until a number is reached that is $1 \bmod 5$ The smallest here is $G_5=21$ itself.
* Count by $15 = 3\cdot 5$ until a umber is reached that is $1\bmod 7$. Again $G_7=15$ works.

Now set $x=2\cdot G_3+3\cdot G_5+2\cdot G_7$, then
$$
\begin{align}
x\bmod 3&=2\cdot(G_3\bmod 3)+3\cdot(G_5\bmod 3)+2\cdot(G_7\bmod 3)=2\\
x\bmod 5&=2\cdot(G_3\bmod 5)+3\cdot(G_5\bmod 5)+2\cdot(G_7\bmod 5)=3\\
x\bmod 7&=2\cdot(G_3\bmod 7)+3\cdot(G_5\bmod 7)+2\cdot(G_7\bmod 7)=2\\
\end{align}
$$
This method clearly works for a system $x=n_i\bmod m_i$ so long as we can find $a_i=t_i\cdot M_i=sm_i+1$ where
$$
M_i=M/m_i\quad\text{and}\quad M= \prod_{j=1}^nm_j
$$
Notice $t_i=M_i^{-1} \pmod {m_i}$ so that $a_i=(M_i^{-1}\bmod {m_i})\cdot M_i$

Then the solution $x=\sum_{i=1}^n n_i\cdot a_i$ works. Actually, $x'=x\bmod M$ works, since if $x=a\cdot M+x'$, then
$$
n_i=x\bmod m_i=(a\cdot M+x')\bmod m_i=x'\bmod m_i
$$

**Note**: This provides a bijection between $\mathbb Z_M$ and $\mathbb Z_{m_1}\times \mathbb Z_{m_2}\times\cdots\times\mathbb Z_{m_n}.$

This general method was used by the Chinese and Hindu people in calculations involving the calendar, cycles of planets, moons, etc. Now this is used in coding and cryptography.

**Alternate Method**: Find $x<385$ so that $x\equiv 2\pmod 3$, $x\equiv 4\pmod 5$, and $x\equiv 6\pmod 7$.

We could use the method above let $m_1=3$, $m_2=5$, and $m_3=7$. Then $M_1=35$, $M_2=21$, and $M_3=15$. We have
* $35\equiv 2\pmod 3$ and $2^{-1}\bmod 3=2$, so $2\cdot 35\bmod 3=1$. So $a_1=2\cdot 35=70$.
* Similarly $21\equiv 1\pmod 5$ and $1^{-1}\bmod 5=1$, so $1\cdot 21\bmod 5=1$. So $a_2=1\cdot 21=21$.
* Finally, $15\equiv 1\pmod 7$ and $1^{-1}\bmod 7=1$, so $1\cdot 15\bmod 7=1$. So $a_3=1\cdot 15=15$.

We have
$$x=2\cdot 70 + 4\cdot 21+6\cdot 15=140+84+90=314\bmod 105= 104.
$$
We can compute $x$ another way using *back substitution*. We want
* $x\equiv 2\pmod 3$ or $x=3t+2$.
* Next, $x=4\pmod 5$, so $3t+2\equiv 4\pmod 5$, this becomes $3t\equiv 2\pmod 5$. Since $3^{-1}\!\mod 5=2$ we have $t=4\bmod 5$, so $t=5u+4$ and so $x=(3(5u+4))+2=15u+14$.

Notice that: $14\bmod 3 = 2$ and $14\bmod 5=4$. So the first two are satisfied.

* Next we want $15u+14\equiv 6\pmod 7$. So $u\equiv 6\pmod 7$ so $u=7v+6$. This means $x=15(7v+6)+14=105v+104$.

As above, $104$ satisfies all three congruences.

**Example**: Use the above two alternate methods to find $x<5\cdot6\cdot7$ satisfying
$$
x\equiv 2\pmod 5,\quad x\equiv 5\pmod 6,\quad x=3\pmod 7
$$

## Fermat's Little Theorem

**Theorem**: For $p$ a prime and integer $a$ with $\gcd(a,p)=1$, $a^{p-1}\equiv 1\pmod p$. Equivalently, $a^p\equiv a\pmod p$.

**Proof**: Notice that $\{a\cdot1\bmod p,a\cdot2\bmod p,\ldots,a\cdot(p-1)\bmod p\}=\{1,2,\ldots,p-1\}$. For suppose $a\cdot m=a\cdot n$ for some $1\le m<n<p$. Then $a\cdot(n-m)=0\bmod p$. this means that $p|a\cdot(n-m)$, but then $p|a$ or $p|(n-m)$. Both of these are impossible since $\gcd(a,p)=1$ and $p$ is prime. This means
$$
\begin{align}
a^{p-1}(1\cdot 2\cdot 3\cdots (p-1))
&\equiv(a\cdot 1)(a\cdot 2)\cdots(a\cdot (p-1))\pmod p\\
&\equiv (1\cdot 2\cdot 3\cdots (p-1))\pmod p\\
&\equiv 1\pmod p
\end{align}
$$
The last equivalence is true since for each $m$, $1<m<p$, there is $n=m^{-1}\bmod p$ and these pair up and cancel out when multiplying.

This can be used to compute $a^n\bmod p$. Write $n=q\cdot (p-1)+r$, then
$$
a^n=a^{q\cdot (p-1)+r}=(a^{p-1})^q\cdot a^r=a^r\bmod p.
$$
**Example**: $720^{335}\bmod 17 = 720^3\bmod 17=6^3\bmod 17=12$.

**Corollary**: If $a$ and $p$ are relatively prime, then $a^{-1}=a^{p-2}\bmod p$.

For example,
$$
\begin{align}
75^{-1}\bmod 83
&=75^{81}\bmod 83\\
&=(75^3)^{27}\bmod 83\\
&=69^{27}\bmod 83\\
&=(69^3)^9\bmod 83\\
&=78^9\bmod 83\\
&=(78^3)^3\bmod 83\\
&=41^3\bmod 83=31
\end{align}
$$

## Primitive roots and discrete logarithms
**Definition**: $r\in\mathbb Z_p$ is a *primitive root* (modulo $p$) iff $\mathbb Z_p^*=\{r^e\bmod p\mid e\in\mathbb Z^*_p\}$.

**Theorem**: For every prime $p$ there is a primitive root modulo $p$.

**Proof**: Take a course in abstract algebra!

**Definition**: For $r$ a primitive root mod $p$, *$e$ is the discrete logarithm base $r$ of $q$ modulo $p$*, denoted $\log_r(q)\bmod p=e$, provided $r^e=q\bmod p$.

## Cryptography (RSA)

Here we just map the letters of an alphabet to numbers modulo some $n$. For example the standard [ascii and extended ascii mapping](https://www.asciitable.com/), here the modulus is $256=2^8=16^2$, so each letter is represented as a pair of hex numbers (1 byte), for example Hello is "48 65 6c 6c 6f." For any $k\in\mathbb Z_{256}$ we can encode a message using the function $E_k(n)=(n+k)\bmod 256$. Here the number $k$ is the *key* and to decode a message use the inverse function, namely, $D_k(n)=(n-k)\bmod b$. This is a simple system and easy to crack. It is a *private key* system since the key $k$ must be shared.

A *public key* system is one where there is a publicly known, sharable key, $k_{pub}$ so that anyone can encode a message using this key, then there is a private key, $k_{priv}$ that is not shared and using $k_{priv}$ it is easy to decode a message encoded with $k_{pub}$. Here is one such system RSA:

* Start with two large prime numbers $p$ and $q$, let $n=pq$. These are so large ($p$ and $q$ have perhaps 300 digits, so that $n$ has 600 digits). Without knowing $p$ and $q$ it is essentially impossible to factor $n$.
* Fix a number $e$ relatively prime to $(p-1)(q-1)$.
* Fix $N$ so that $256^N=(2^8)^N<n$. We will chuck our text into $N$-byte chunks.
* Suppose the plain text is $m_1,m_2,\ldots,m_k$, then set $c_i=m_i^e \bmod n$. Then $c_1,c_2,\ldots,c_n$ is the cipher text.
* Let $d=e^{-1}\bmod (p-1)(q-1)$, that is, $ed=k(p-1)(q-1)+1$. So long as $\gcd(m_i,pq)=1$, Fermat's Little Theorem gives:
$$
\begin{align}
c_i^d\bmod p&=m_i^{e\cdot d}\bmod p=m_i^{k(p-1)(q-1)+1}\bmod p = m_i\cdot(m_i^{p-1})^{k(q-1)}\mod p=m_i\bmod p\\
c_i^d\bmod q&=m_i^{e\cdot d}\bmod q =m_i^{k(p-1)(q-1)+1}\bmod q = m_i\cdot(m_i^{q-1})^{k(p-1)}\mod q=m_i\bmod q\\
\end{align}
$$
By the Chinese remainder theorem, $c_i^d\bmod pq = m_i$

If $\gcd(m_i,pq)>1$, then either $p|m_i$ or $q|m_i$. Suppose $p|m_i$, then we still have

$$
\begin{align}
c_i^d\bmod p&=m_i^{e\cdot d}\bmod p=m_i^{k(p-1)(q-1)+1}\bmod p = 0 = m_i\bmod p\\
c_i^d\bmod q&=m_i^{e\cdot d}\bmod q =m_i^{k(p-1)(q-1)+1}\bmod q = m_i\cdot(m_i^{q-1})^{k(p-1)}\mod q=m_i\bmod q\\
\end{align}
$$
CRT still applies and we have $c_i^d\bmod{pq}=m_i$

So here the public key for encoding is $(n,e)$ while the private key for decoding is $(n,d)$.

Implemented in python [here](https://colab.research.google.com/drive/15qkZbhE1zxibm3g0X5l5LJlNg7yx8O4x?usp=sharing)

**Example**: Use $p=7867$ and $q=7873$, so $n=61936891$. An $e$ that is relatively prime to $(p-1)(q-1)$ is $e=57267623$ and the inverse of this is $d=4144919$ modulo $(p-1)(q-1)$. So ehe public key for encoding is $k_{pub}=(61936891, 57267623)$ and the private key for decoding is $k_{priv}=(61936891, 4144919)$.

The largest size chunks of text we can allow is 2 since $255\cdot256^3 > n > 255\cdot256^2 + 255\cdot256 + 256$. So if we code "Hello" we break it up into
* ["Hel", "lo"]
* [48 65 6c, 6c 6f]
= $[72\cdot256^2 + 101\cdot256+108,108\cdot256 + 111]$
= [4744556, 27759]
= $[m_1,m_2]$
* The cipher will be:
$$
[4744556^{57267623}\bmod 61936891, 27759^{57267623} \bmod 61936891] \\
= [56052657, 19609346]=[c_1,c_2]
$$
* To decode you compute:
$$
[56052657^{4144919}\bmod 61936891, 196093463^{4144919}\bmod 61936891]\\ = [4744556, 27759]
$$

<a id="practice">**Practice**</a>: Consider the very small alphabet consisting of a, b, c, +, (, ), = coded by $\{0,1,2,3,4,5,6\}=\mathbb Z_7$. That is use the following table:
|a|b|c|+|(|)|=|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|0|1|2|3|4|5|6|

Use $p=17$ and $q=19$ to code "$(a+b)+c=a+(b+c)$." Since $n=17\cdot19=323$ and $7^3>n>6\cdot7^2+6\cdot 7+ 6=(666)_{7}$ you can only chunk in groups of 3, so you will need to code: ["(a+", "b)+", "c=a", "+(b", "+c)"] which will be
$$
[(403)_7, (153)_7, \ldots]=[4\cdot7^2+3,1\cdot7^2+5\cdot 7+3,\ldots]=[199,87,\ldots] =[m_1,m_2,\ldots]
$$
In this [Google Form](https://forms.gle/HP7qz2L1mz3tq9V66) enter your value of $e$, value of $d$, and the values $c_1 = m_1^e\bmod n$, and $c_2=m_2^e\bmod n$. I will check by calculating $m_i=c_i^d\bmod n$ and translating back into the text. If I can make the sheet do this automatically, I will add it, else, I will do it by hand.