<!-- Source: https://web3-lab.annaburd.me/math-behind-key-pairs/ -->

# Math behind key pairs

The number theory behind public-key cryptography, from modular arithmetic, primes and gcds
to Fermat's and Euler's theorems, built up from scratch.

## Modular Arithmetic Foundations

Modular Arithmetic

The modulus m defines the wrap-around space. Every integer maps to one output from 0 to m-1.
These outputs are called residues.

mod 3 has exactly 3 possible residues

Residues set

mod 3 { 0, 1, 2 }

Modulus space

Integers space

Congruence check (mod 3)

=/=

A and B are not congruent modulo 3, because they map to different residues {0} and {2}.

In the modulus space, they are different numbers.

When divided by modulus 3, they have different remainders {0} and {2}.

n = q * m + r

Euclidean division breaks C into full groups of m plus the leftover residue.

The integer being converted (here: C).

The modulus (the group size).

Quotient: how many full groups of m fit into n.

r (Residue)

Remainder after removing q * m, with 0 <= r < m.

Quotient q

Full groups of size 3.

Residue r

Leftover after grouping, with 0 <= r < 3.

Visual equation

51=17 * 3+0

Step-by-step

1) 51 / 3 = 17 remainder 0

2) Largest multiple below C: 51 = 17 * 3

3) Residue: 51 - 51 = 0

4) Congruence: 51 === 0 (mod 3)

## Modular Operations

$$
(A + B) \bmod m = ((A \bmod m) + (B \bmod m)) \bmod m
$$

Path A: keep full wraps

A starts at 0, then B starts where A stopped.

A steps: 12B steps: 9

A: 12 = 4 * 3 + 0 (clockwise)

B: 9 = 3 * 3 + 0 (clockwise)

Path B: shortcut full wraps

Same chaining, but with full wraps removed first.

A mod 3: 0B mod 3: 0

A === 0 (mod 3)

B === 0 (mod 3)

Same final residue

(12 + 9) mod 3 = 0

((12 mod 3) + (9 mod 3)) mod 3 = (0 + 0) mod 3 = 0

Proof for modular addition

We prove:

(A + B) mod C = ((A mod C) + (B mod C)) mod C

Write:

A = C * Q1 + R1
B = C * Q2 + R2
with 0 <= R1, R2 < C.

Key fact: (C * t) mod C = 0
Multiples of C do not affect the remainder.

Add first

(A + B) mod C

= ((C * Q1 + R1) + (C * Q2 + R2)) mod C

= (C * (Q1 + Q2) + (R1 + R2)) mod C

= (R1 + R2) mod C

Reduce first

A mod C = R1
B mod C = R2

((A mod C) + (B mod C)) mod C

= (R1 + R2) mod C

Both sides equal (R1 + R2) mod C. Proof complete.

$$
(A \cdot B) \bmod m = ((A \bmod m) \cdot (B \bmod m)) \bmod m
$$

*

Same final residue

(8 * 11) mod 3 = 1

((8 mod 3) * (11 mod 3)) mod 3 = (2 * 2) mod 3 = 1

Proof for modular multiplication

We prove:

(A * B) mod C = ((A mod C) * (B mod C)) mod C

Write:

A = C * Q1 + R1
B = C * Q2 + R2
with 0 <= R1, R2 < C.

Key fact: (C * t) mod C = 0
Multiples of C do not affect the remainder.

Multiply first

(A * B) mod C

= ((C * Q1 + R1) * (C * Q2 + R2)) mod C

= (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R2) mod C

= (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R2) mod C

= (R1 * R2) mod C

Reduce first

A mod C = R1
B mod C = R2

((A mod C) * (B mod C)) mod C

= (R1 * R2) mod C

Both sides equal (R1 * R2) mod C. Proof complete.

$$
(A^B) \bmod m = ((A \bmod m)^B) \bmod m
$$

^

Same final residue

(5^13) mod 3 = 2

((5 mod 3)^13) mod 3 = (2^13) mod 3 = 2

Fast modular exponentiation (square-and-multiply)

A^B grows very fast, e.g. 2^90 = 1 237 940 039 285 380 274 899 124 224 - computational problem

Large exponent can be split into smaller: 2^90 mod C = (2^45 * 2^45) mod C = ((2^10 * 2^35) * (2^10 * 2^35)) mod C =...

Binary trick - split and substitute ^2 for fast calculation:

7^1 mod 13 = 7

7^2 mod 13 = (7^1 * 7^1) mod 13 = (7 * 7) mod 13 = 10

7^4 mod 13 = (7^2 * 7^2) mod 13 = (10 * 10) mod 13 = 9

7^8 mod 13 = (7^4 * 7^4) mod 13 = (9 * 9) mod 13 = 3

7^16 mod 13 = (7^8 * 7^8) mod 13 = (3 * 3) mod 13 = 9

7^32 mod 13 = (7^16 * 7^16) mod 13 = (9 * 9) mod 13 = 3

7^64 mod 13 = (7^32 * 7^32) mod 13 = (3 * 3) mod 13 = 9

7^128 mod 13 = (7^64 * 7^64) mod 13 = (9 * 9) mod 13 = 3

7^256 mod 13 = (7^128 * 7^128) mod 13 = (3 * 3) mod 13 = 9

Binary trick for any number:
2^90 mod 13 - 90 is not a power of 2, so we cannot apply fast calculation directly, but we can split 90 (and any number) into a sum of powers of 2, e.g.
90 = 64 + 16 + 8 + 2 = 2^5 + 2^4 + 2^3 + 2^1

And then use the fact that (A * B) mod C = ((A mod C) * (B mod C)) mod C:
2^90 mod 13 = ((2^64 mod 13) * (2^16 mod 13) * (2^8 mod 13) * (2^2 mod 13)) mod 13 = (3 * 3 * 9 * 4) mod 13 = 1296 mod 13 = 10
So, 1 237 940 039 285 380 274 899 124 224 mod 13 = 10.

To fast split any number into a sum of powers of 2, use binary representation of the number:
90 = 1011010 = 2^6 + 2^4 + 2^3 + 2^1 = 64 + 16 + 8 + 2

## Modular Arithmetic Examples

Calculation examples

Click on an example to expand it and see the steps.

Step 1 - reduce the base

$$
521 \equiv 11 \equiv -6 \pmod{17}
$$

$$
521^{637} \equiv (-6)^{637} \pmod{17}
$$

Step 2 - expose a square

$$
(-6)^{637} = -6 \cdot 6^{636} = -6 \cdot (6^2)^{318}
$$

$$
6^2 = 36 \equiv 2 \pmod{17}
$$

$$
\Rightarrow -6 \cdot (6^2)^{318} \equiv -6 \cdot 2^{318} \pmod{17}
$$

Step 3 - reduce the exponent, searching for a smaller residue, ideally 1 or -1

$$
318 = 2 + 4 \cdot 79 \Rightarrow 2^{318} = 2^2 \cdot (2^4)^{79}
$$

$$
2^4 = 16 \equiv -1 \pmod{17}
$$

Step 4 - evaluate the sign and reduce

$$
-6 \cdot 2^{318} = -6 \cdot 2^2 \cdot (2^4)^{79} \equiv -6 \cdot 4 \cdot (-1)^{79} = 24
$$

$$
24 \bmod 17 = 7
$$

Final residue

$$
\therefore\ 521^{637} \equiv 7 \pmod{17}
$$

Pattern to reuse: reduce to a small residue first, then look for a power that becomes 1 or -1 modulo m.

Step 1 - rewrite the big power

$$
7^{128} = (7^2)^{64}
$$

$$
(7^2)^{64} \equiv 49^{64} \equiv 16^{64} \pmod{33}
$$

Step 2 - convert to base 2

$$
16^{64} = (2^4)^{64} = 2^{256}
$$

$$
2^{256} = 2 \cdot 2^{255} = 2 \cdot (2^5)^{51}
$$

Step 3 - reduce by using -1

$$
2^5 = 32 \equiv -1 \pmod{33}
$$

$$
2 \cdot (2^5)^{51} \equiv 2 \cdot (-1)^{51} = -2 \pmod{33}
$$

Step 4 - normalize the residue

$$
-2 \equiv 31 \pmod{33}
$$

Final residue

$$
\therefore\ 7^{128} \equiv 31 \pmod{33}
$$

After reducing the base, split exponents to expose a known residue like -1 and collapse quickly.

Step 1 - find a useful power

$$
2^4 = 16 \equiv 1 \pmod{15}
$$

Step 2 - split the exponent

$$
2018 = 4 \cdot 504 + 2
$$

$$
2^{2018} = (2^4)^{504} \cdot 2^2
$$

Step 3 - reduce modulo 15

$$
(2^4)^{504} \cdot 2^2 \equiv 1^{504} \cdot 4 \equiv 4 \pmod{15}
$$

Final residue

$$
\therefore\ 2^{2018} \equiv 4 \pmod{15}
$$

When a^k is congruent to 1 (mod m), split the exponent as kq + r. The repeated k-block collapses to 1, so only the small remainder r matters.

Step 1 - find a helpful power

$$
2^4 = 16 \equiv -1 \pmod{17}
$$

Step 2 - split the exponent by that power

$$
2018 = 4 \cdot 504 + 2
$$

$$
2^{2018} = (2^4)^{504} \cdot 2^2
$$

Step 3 - reduce modulo 17

$$
(2^4)^{504} \cdot 2^2 \equiv (-1)^{504} \cdot 4 \equiv 1 \cdot 4 \equiv 4 \pmod{17}
$$

Final residue

$$
\therefore\ 2^{2018} \equiv 4 \pmod{17}
$$

When a^k is congruent to -1 (mod m), parity does the work: even powers become 1, odd powers stay -1.

Step 1 - reduce the base modulo 6

$$
7 \equiv 1 \pmod{6}
$$

Step 2 - raise both sides to the n-th power

$$
7^2 = 7 \cdot 7 \equiv 1 \cdot 1 \equiv 1 \pmod{6}
$$

$$
\Rightarrow 7^n \equiv 1^n \equiv 1 \pmod{6}
$$

Step 3 - subtract 1

$$
7^n - 1 \equiv 1 - 1 \equiv 0 \pmod{6}
$$

Final residue

$$
\therefore\ 7^n - 1 \equiv 0 \pmod{6}\ \text{for all } n \ge 1
$$

Reusable rule: if a is congruent to 1 modulo m, then a^n - 1 is congruent to 0 modulo m.

Step 1 - reduce 13 modulo 10

$$
13 \equiv 3 \pmod{10}
$$

$$
\Rightarrow 13^n \equiv 3^n \pmod{10}
$$

Step 2 - rewrite the full expression modulo 10

$$
13^n + 3^{n+2} \equiv 3^n + 3^{n+2} \pmod{10}
$$

Step 3 - factor out 3^n

$$
3^n + 3^{n+2} = 3^n(1 + 3^2) = 3^n(1 + 9) = 3^n \cdot 10
$$

Step 4 - use that 10 is 0 modulo 10

$$
3^n \cdot 10 \equiv 0 \pmod{10}
$$

Final residue

$$
\therefore\ 13^n + 3^{n+2} \equiv 0 \pmod{10}\ \text{for all } n \ge 0
$$

Useful pattern: after reduction, factor common terms and check whether the remaining factor is a multiple of the modulus.

Step 1 - rewrite both powers

$$
7^{n+2} = 7^n \cdot 7^2 = 49 \cdot 7^n
$$

$$
8^{2n+1} = 8 \cdot (8^2)^n = 8 \cdot 64^n
$$

Step 2 - reduce 64 modulo 57

$$
64 \equiv 7 \pmod{57} \Rightarrow 64^n \equiv 7^n \pmod{57}
$$

$$
\Rightarrow 8^{2n+1} \equiv 8 \cdot 7^n \pmod{57}
$$

Step 3 - combine like terms

$$
7^{n+2} + 8^{2n+1} \equiv 49 \cdot 7^n + 8 \cdot 7^n = (49 + 8) \cdot 7^n = 57 \cdot 7^n \pmod{57}
$$

Step 4 - conclude modulo 57

$$
57 \cdot 7^n \equiv 0 \pmod{57}
$$

Final residue

$$
\therefore\ 7^{n+2} + 8^{2n+1} \equiv 0 \pmod{57}\ \text{for all } n \ge 0
$$

When two terms can be rewritten with the same power factor, factor it out and check if the remaining coefficient is the modulus.

Step 1 - name the modulus

$$
m = 2^n - 3
$$

Step 2 - rewrite the base using m

$$
2^n - 1 = (2^n - 3) + 2 = m + 2
$$

Step 3 - reduce the expression modulo m

$$
(2^n - 1)^n - 3 = (m + 2)^n - 3
$$

$$
m + 2 \equiv 2 \pmod{m} \Rightarrow (m + 2)^n - 3 \equiv 2^n - 3 \pmod{m}
$$

Step 4 - substitute m back clearly

$$
2^n - 3 \pmod{m} = 2^n - 3 \pmod{2^n - 3} \equiv 0 \pmod{n}
$$

Final residue

$$
\therefore\ (2^n - 1)^n - 3 \equiv 0 \pmod{2^n - 3}\ \text{for all } n \ge 2
$$

Strategy for variable moduli: set m equal to the modulus, rewrite terms in the form m + c, then reduce exactly as usual.

## Divisibility rules

Decimal decomposition of an integer

Any number in decimal system can be represented as a sum of powers of 10.

General form

$$
N = \overline{a_n a_{n-1}\ldots a_1 a_0}
$$

$$
N = a_0 + 10\cdot \overline{a_n a_{n-1}\ldots a_1}
$$

$$
N = a_0 + a_1\cdot 10 + 10^2\cdot \overline{a_n a_{n-1}\ldots a_2}
$$

$$
N = a_0 + a_1\cdot 10 + a_2\cdot 10^2 + \cdots + a_n\cdot 10^n
$$

$$
1234 = \overline{1234}
$$

$$
1234 = 4 + 10\cdot \overline{123}
$$

$$
1234 = 4 + 3\cdot 10 + 10^2\cdot \overline{12}
$$

$$
1234 = 4 + 3\cdot 10 + 2\cdot 10^2 + 10^3\cdot \overline{1}
$$

$$
1234 = 4 + 3\cdot 10 + 2\cdot 10^2 + 1\cdot 10^3
$$

$$
1234 = 4 + 30 + 200 + 1000
$$

Rule for division by: none

Click a value on the line to see its divisibility rule.

Proof

$$
10 \text{ is divisible by } d \in \{2,5,10\}
$$

$$
N = \overline{a_n a_{n-1} \ldots a_1 a_0} = 10 \cdot \overline{a_n a_{n-1} \ldots a_1} + a_0
$$

$$
10 \cdot \overline{a_n a_{n-1} \ldots a_1} \text{ is a multiple of } 10, \text{ so it is also a multiple of } d
$$

$$
\text{Since by modulo multiples of } d \text{ are } 0, \text{   } N \equiv a_0 \pmod{d}
$$

Examples

$$
\text{To check divisibility by } 2,5,10, \text{ check the last digit } a_0.
$$

$$
N \equiv a_0 \pmod{d}
$$

$$
348 \equiv 8 \pmod{2} \Rightarrow 348 \text{ is divisible by } 2
$$

$$
735 \equiv 5 \pmod{5} \Rightarrow 735 \text{ is divisible by } 5
$$

$$
1240 \equiv 0 \pmod{10} \Rightarrow 1240 \text{ is divisible by } 10
$$

$$
1243 \equiv 3 \pmod{10} \Rightarrow 1243 \text{ is not divisible by } 10 \text{, the remainder is 3}
$$

Proof

$$
100 \text{ is divisible by every } d \in \{1,2,4,5,10,20,25,50,100\}
$$

$$
\text{In this block, we apply it to } d \in \{4,20,25,50\}
$$

$$
N = \overline{a_n a_{n-1} \ldots a_2 a_1 a_0} = 100 \cdot \overline{a_n a_{n-1} \ldots a_2} + \overline{a_1 a_0}
$$

$$
100 \cdot \overline{a_n a_{n-1} \ldots a_2} \text{ is a multiple of } 100, \text{ so it is also a multiple of } d
$$

$$
\text{Since by modulo multiples of } d \text{ are } 0, \text{   } N \equiv \overline{a_1 a_0} \pmod{d}
$$

Examples

$$
\text{To check divisibility by } 4,20,25,50, \text{ check the last 2 digits } \overline{a_1 a_0}.
$$

$$
N \equiv \overline{a_1 a_0} \pmod{d}
$$

$$
316 \equiv 16 \pmod{4} \Rightarrow 16 \text{ is divisible by } 4 \Rightarrow 316 \text{ is divisible by } 4
$$

$$
1340 \equiv 40 \pmod{20} \Rightarrow 40 \text{ is divisible by } 20 \Rightarrow 1340 \text{ is divisible by } 20
$$

$$
1325 \equiv 25 \pmod{25} \Rightarrow 25 \text{ is divisible by } 25 \Rightarrow 1325 \text{ is divisible by } 25
$$

$$
7450 \equiv 50 \pmod{50} \Rightarrow 50 \text{ is divisible by } 50 \Rightarrow 7450 \text{ is divisible by } 50
$$

$$
1274 \equiv 74 \pmod{50} \Rightarrow 74 \text{ is not divisible by } 50 \Rightarrow 1274 \text{ is not divisible by } 50 \text{, the remainder is } 24
$$

Proof

$$
1000 \text{ is divisible by every } d \in \{1,2,4,5,8,10,20,25,40,50,100,125,200,250,500,1000\}
$$

$$
\text{In this block, we apply it to } d \in \{8,40\}
$$

$$
N = \overline{a_n a_{n-1} \ldots a_3 a_2 a_1 a_0} = 1000 \cdot \overline{a_n a_{n-1} \ldots a_3} + \overline{a_2 a_1 a_0}
$$

$$
1000 \cdot \overline{a_n a_{n-1} \ldots a_3} \text{ is a multiple of } 1000, \text{ so it is also a multiple of } d
$$

$$
\text{Since by modulo multiples of } d \text{ are } 0, \text{   } N \equiv \overline{a_2 a_1 a_0} \pmod{d}
$$

Examples

$$
\text{To check divisibility by } 8,40, \text{ check the last 3 digits } \overline{a_2 a_1 a_0}.
$$

$$
N \equiv \overline{a_2 a_1 a_0} \pmod{d}
$$

$$
1232 \equiv 232 \pmod{8} \Rightarrow 232 \text{ is divisible by } 8 \Rightarrow 1232 \text{ is divisible by } 8
$$

$$
7640 \equiv 640 \pmod{40} \Rightarrow 640 \text{ is divisible by } 40 \Rightarrow 7640 \text{ is divisible by } 40
$$

$$
7314 \equiv 314 \pmod{40} \Rightarrow 314 \text{ is not divisible by } 40 \Rightarrow 7314 \text{ is not divisible by } 40 \text{, the remainder is } 34
$$

Proof

$$
d \in \{3,9\}
$$

$$
10 \equiv 1 \pmod{d} \Rightarrow 10^k \equiv 1^k \equiv 1 \pmod{d}
$$

$$
N = a_0 + 10a_1 + 10^2a_2 + \cdots + 10^n a_n \equiv a_0 + 1\cdot a_1 + 1\cdot a_2 + \cdots + 1\cdot a_n \pmod{d} = a_0 + a_1 + a_2 + \cdots + a_n
$$

$$
\text{So, number } N \text{ is divisible by } d \text{ if sum of digits } a_0 + a_1 + a_2 + \cdots + a_n \text{ is divisible by } d
$$

Examples

$$
\text{To check divisibility by } 3,9, \text{ check the sum of digits.}
$$

$$
N \equiv a_0 + a_1 + \cdots + a_n \pmod{d}
$$

$$
123 \equiv 1+2+3 = 6 \pmod{3} \Rightarrow 6 \text{ is divisible by } 3 \Rightarrow 123 \text{ is divisible by } 3
$$

$$
729 \equiv 7+2+9 = 18 \pmod{9} \Rightarrow 18 \text{ is divisible by } 9 \Rightarrow 729 \text{ is divisible by } 9
$$

$$
124 \equiv 1+2+4 = 7 \pmod{3} \Rightarrow 7 \text{ is not divisible by } 3 \Rightarrow 124 \text{ is not divisible by } 3 \text{, the remainder is } 1
$$

$$
1237 \equiv 1+2+3+7 = 13 \equiv 4 \pmod{9} \Rightarrow 13 \text{ is not divisible by } 9 \Rightarrow 1237 \text{ is not divisible by } 9 \text{, the remainder is } 4
$$

Proof

$$
d = 11
$$

$$
10 \equiv -1 \pmod{11} \Rightarrow 10^k \equiv (-1)^k \pmod{11}
$$

$$
N = a_0 + 10a_1 + 10^2a_2 + \cdots + 10^n a_n \equiv a_0 - a_1 + a_2 - a_3 + \cdots + (-1)^n a_n \pmod{11}
$$

$$
\text{So, number } N \text{ is divisible by } 11 \text{ if the alternating digit sum } a_0 - a_1 + a_2 - a_3 + \cdots + (-1)^n a_n \text{ is divisible by } 11
$$

Examples

$$
\text{To check divisibility by } 11, \text{ compute the alternating sum of digits.}
$$

$$
N \equiv a_0 - a_1 + a_2 - a_3 + \cdots + (-1)^n a_n \pmod{11}
$$

$$
121 \equiv 1-2+1 = 0 \pmod{11} \Rightarrow 121 \text{ is divisible by } 11
$$

$$
462 \equiv 2-6+4 = 0 \pmod{11} \Rightarrow 462 \text{ is divisible by } 11
$$

$$
1234 \equiv 4-3+2-1 = 2 \pmod{11} \Rightarrow 1234 \text{ is not divisible by } 11 \text{, the remainder is } 2
$$

Proof

$$
d \in \{7,13\}
$$

$$
1001 = 7 \cdot 11 \cdot 13
$$

$$
1001 \equiv 0 \pmod{d} \Rightarrow 1000 \equiv -1 \pmod{d}
$$

$$
N = \overline{a_{3m+2} a_{3m+1} a_{3m} \ldots a_2 a_1 a_0} = \overline{a_2 a_1 a_0} + 1000\cdot\overline{a_5 a_4 a_3} + 1000^2\cdot\overline{a_8 a_7 a_6} + \cdots + 1000^m\cdot\overline{a_{3m+2} a_{3m+1} a_{3m}}
$$

$$
\text{(Leftmost block may contain leading zeros)}
$$

$$
N \equiv \overline{a_2 a_1 a_0} + (-1)\cdot \overline{a_5 a_4 a_3} + (-1)^2\cdot \overline{a_8 a_7 a_6} - \cdots + (-1)^m\overline{a_{3m+2} a_{3m+1} a_{3m}} \pmod{d}
$$

$$
\text{So, number } N \text{ is divisible by } d \in \{7,13\} \text{ if the alternating sum of 3-digit blocks is divisible by } d
$$

Examples

$$
\text{To check divisibility by } 7 \text{ or } 13, \text{ split into 3-digit blocks and alternate signs.}
$$

$$
N \equiv \overline{a_2 a_1 a_0} - \overline{a_5 a_4 a_3} + \overline{a_8 a_7 a_6} - \cdots + (-1)^m\overline{a_{3m+2} a_{3m+1} a_{3m}} \pmod{d}
$$

$$
20384 = 020\,|\,384 \Rightarrow 20384 \equiv 384-020 = 364 \equiv 0 \pmod{7} \Rightarrow 20384 \text{ is divisible by } 7
$$

$$
2704 = 002\,|\,704 \Rightarrow 2704 \equiv 704-002 = 702 \equiv 0 \pmod{13} \Rightarrow 2704 \text{ is divisible by } 13
$$

$$
12345 = 012\,|\,345 \Rightarrow 12345 \equiv 345-012 = 333 \equiv 4 \pmod{7} \Rightarrow 12345 \text{ is not divisible by } 7 \text{, the remainder is } 4
$$

$$
12345 = 012\,|\,345 \Rightarrow 12345 \equiv 333 \equiv 8 \pmod{13} \Rightarrow 12345 \text{ is not divisible by } 13 \text{, the remainder is } 8
$$

## Primes

Numbers decomposition

Prime numbers - the building blocks that combine to build all other numbers.

·

= 495

Primes lie rather unpredictably on the number line.

Every integer greater than 1 can be broken down as a product of primes. This prime set is unique for each number, like a fingerprint.

6 =

·

## Greatest common divisor

Divisibility

Intuition: "3 divides 12" means 12 = 3 * 4, or easier to think 12 is a multiple of 3.

Divisibility Definition

$$
\text{Let } a,b \in \mathbb{Z}.\ \text{We say } a \mid b \text{ if there exists } c \in \mathbb{Z} \text{ such that } ac = b.
$$

$$
\text{Notation: }
$$

$$
a \mid b \text{ - "a divides b" - a statement}
$$

$$
\frac{a}{b} \text{ - "a divided by b" - a number}
$$

Number a divides b if you can build b using all blocks from a.
For example, 12 divides 60:

60 =

·

GCD Definition

$$
\text{Let } a,b \in \mathbb{Z}\ \text{. Then gdc of a and b, denoted } \gcd(a,b) \text{ is the largest integer } g \text{ such that } g  \mid a \text{ and } g \mid b.
$$

$$
a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n},
$$

$$
b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_n^{\beta_n},
$$

$$
\gcd(a,b) = p_1^{\min(\alpha_1,\beta_1)} p_2^{\min(\alpha_2,\beta_2)} \cdots p_n^{\min(\alpha_n,\beta_n)}
$$

12 =

18 =

·

GCD(12, 18) =

·

=6

LCM Definition

$$
\text{Let } a,b \in \mathbb{Z}\ \text{. Then the lcm of } a \text{ and } b, \text{ denoted } \operatorname{lcm}(a,b), \text{ is the smallest positive integer } m \text{ such that } a \mid m \text{ and } b \mid m.
$$

$$
a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n},
$$

$$
b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_n^{\beta_n},
$$

$$
\operatorname{lcm}(a,b) = p_1^{\max(\alpha_1,\beta_1)} p_2^{\max(\alpha_2,\beta_2)} \cdots p_n^{\max(\alpha_n,\beta_n)}
$$

LCM includes all blocks from a, and all blocks from b, repeating blocks can be shared between a and b.

12 =

18 =

·

LCM(12, 18) =

·

=36

## Euclidean algorithm

Find gcd(A, B) by playing with piles of pebbles

Having two piles of pebbles, what happens if you remove smaller pile from the larger one, and repeat until piles are equal?
Turns out, the final pile size is the greatest common divisor of the original piles.

Show hint

Proof for the Euclidean algorithm

$$
\text{Proposition. Let } a,b \in \mathbb{Z}_{>0} \text{ with } a \le b. \text{ Then } \gcd(a,b) = \gcd(a,b-a).
$$

$$
\text{Suppose } g = \gcd(a,b).
$$

$$
g \mid a \text{ and } g \mid b.
$$

$$
\text{So there exist } \alpha,\beta \in \mathbb{Z} \text{ such that } a = \alpha g,\ b = \beta g.
$$

$$
b-a = \beta g - \alpha g = g(\beta-\alpha),
$$

$$
\text{hence } g \mid (b-a).
$$

$$
\text{Therefore } g \text{ is a common divisor of } a \text{ and } b-a, \text{ so } g \le \gcd(a,b-a).
$$

$$
\text{Conversely, suppose } h = \gcd(a,b-a).
$$

$$
h \mid a \text{ and } h \mid (b-a).
$$

$$
\text{So there exist } \alpha,\beta \in \mathbb{Z} \text{ such that } a = \alpha h,\ b-a = \beta h.
$$

$$
\text{Trick: rewrite } b \text{ as } (b-a)+a.
$$

$$
b = (b-a)+a = \beta h + \alpha h = h(\beta+\alpha),
$$

$$
\text{hence } h \mid b.
$$

$$
\text{Therefore } h \text{ is a common divisor of } a \text{ and } b, \text{ so } h \le \gcd(a,b).
$$

$$
\gcd(a,b) \le \gcd(a,b-a) \quad \text{and} \quad \gcd(a,b-a) \le \gcd(a,b).
$$

$$
\text{Both} \le \text{ and } \ge \text{ are true only when the two numbers are equal.}
$$

$$
\text{Hence } \gcd(a,b) = \gcd(a,b-a).
$$

$$
\text{Base case: } \gcd(n,0) = n.
$$

$$
\text{Reason: } n \mid n \text{ and } n \mid 0 \text{ since } 0 = n \cdot 0.
$$

Faster Euclidean algorithm

Subtraction removes one copy of the smaller number at a time. Division removes all full copies at once, reducing the number of steps.

$$
\text{If } b = qa + r \text{ with } 0 \le r < a,\ \text{then } \gcd(a,b) = \gcd(a,r).
$$

Calculate gcd(12, 18):

1. 18 = 1 * 12 + 6, so gcd(12, 18) = gcd(12, 6). Quotient 1 means removing 1 full copy of 12 in one jump.

2. 12 = 2 * 6 + 0, so gcd(12, 6) = gcd(6, 0). Quotient 2 means removing 2 full copies of 6 in one jump.

3. The last non-zero remainder is 6, so gcd(12, 18) = 6.

## Extended Euclidean algorithm

Enhancing Euclidean algorithm to solve more problems

Add bookkeeping - track how each remainder is build from the original inputs, that is keep a "recipe chain" for a remainder r in terms of ingredients a and b. This tiny extra piece of information upgrades an algorithm for gcd into a tool for linear Diophantine equations, multiplicative inverses, and the Chinese remainder theorem.

A Diophantine equation is a polynomial equation with integer coefficients for which only integer solutions are of interest. The name Diophantine refers to the Greek mathematician of the 3rd century, Diophantus of Alexandria, who published "Arithmetica", a collection of algebraic problems and the earliest known book on algebra.

There are many types of Diophantine equations, e.g. linear, exponential, quadratic, cubic, etc., here we focus on the linear case.

Linear Diophantine equations are of the form: ax + by = c.

Bezout's identity is a theorem that proves that gcd(a, b) can be expressed as a linear combination of a and b, which is exactly the form of a linear Diophantine equation ax + by = c. And, if we find one solution, we can take multiples of it to get other solutions for 2c, 3c, 4c, etc.

Bezout's Identity Proof

$$
\text{If } a,b \in \mathbb{Z} \text{ are not both } 0,\ \text{then there exist } x,y \in \mathbb{Z} \text{ such that } \gcd(a,b)=ax+by.
$$

$$
\text{Well-ordering principle: if set is non-empty and is a subset of natural numbers } \emptyset \ne S \subseteq \mathbb{N},\ \text{then set } S \text{ has a smallest element.}
$$

$$
\text{Division algorithm: for } a \in \mathbb{Z},\ d \in \mathbb{N},\ \exists q,r \in \mathbb{Z} \text{ such that } a = dq + r,\ 0 \le r < d.
$$

$$
\text{Let } S = \{ as + bt \mid s,t \in \mathbb{Z},\ as+bt > 0 \} \subseteq \mathbb{N}. \text{ Since } a \text{ and } b \text{ are not both } 0,\ S \ne \emptyset.
$$

$$
\text{By well-ordering, } S \text{ has a smallest element, say } ax+by,\ \text{for some } x,y \in \mathbb{Z}.
$$

$$
\gcd(a,b) \mid a \text{ and } \gcd(a,b) \mid b \Rightarrow \gcd(a,b) \mid (ax+by).
$$

$$
\text{Since } \gcd(a,b) \text{ divides } ax+by,\ \text{so } \textcolor{blue}{\gcd(a,b) \le ax+by}.
$$

$$
\text{Let's represent } a \text{ as a multiple of } ax+by \text{ plus a remainder: } a = (ax+by)q + r,\ 0 \le r < ax+by.
$$

$$
\text{Rearranging, we get } r = a - (ax+by)q = a(1-xq)+b(-yq).
$$

$$
\text{So we see that } r \text{ is another integer combination of } a \text{ and } b.
$$

$$
\text{Plugging } r \text{ back into the inequality, we get } 0 \le r = a(1-xq)+b(-yq) < ax+by.
$$

$$
\text{If } r > 0,\ \text{then } r \in S \text{ and } r < ax+by,\ \text{which contradicts the fact that } ax+by \text{ is the smallest element of } S. \text{ Since } 0 \le r,\ \text{we must have } r = 0.
$$

$$
\text{Remainder is } 0,\ \text{which means } ax+by \mid a.
$$

$$
\text{Similarly, we can follow the same steps to show that } ax+by \mid b.
$$

$$
\text{So, ax + by divides both a and b, it is a common divisor of a and b, and } \textcolor{green}{ax+by \le \gcd(a,b)}.
$$

$$
\text{Combining } \textcolor{blue}{\gcd(a,b) \le ax+by} \text{ and } \textcolor{green}{ax+by \le \gcd(a,b)},\ \text{we get } \gcd(a,b) = ax+by.
$$

$$
\therefore \gcd(a,b) = ax+by.
$$

Question: Solve the linear Diophantine equation 196x + 180y = 4

Go through the steps of the [Euclidean algorithm](https://web3-lab.annaburd.me/math-behind-key-pairs/#euclidean-algorithm), but keep track of the recipes for remainders and quotients in terms of original inputs a (196) and b (180).

c = gcd(a, b)

Step 1

=

1 ·

Step 2

=

11 ·

x-11

Step 3

=

4 ·

x-11

y-49

Solution: 4 = 196 * (-11) + 180 * (12)We know how to make 4 from 196 and 180.

General solution

Once one integer solution is known, we can use a trick: add $a(-b) + b(a) = 0$ to the equation. That shifts the point along the solution line.

Solution line

$$
a(-b) + b(a) = 0
$$

Add zero: next solution

$$
ax + by + \left(a(-b) + b(a)\right) = c
$$

$$
a(x - b) + b(y + a) = c
$$

Remove zero: previous solution

$$
ax + by - \left(a(-b) + b(a)\right) = c
$$

$$
a(x + b) + b(y - a) = c
$$

General solution

$$
x = -11 - 45t, \quad y = 12 + 49t, \quad t \in \mathbb{Z}
$$

How to find a 'half' in a modular space? In ordinary arithmetic, "half of 1" sits somewhere between 0 and 1, at 0.5 to be exact. In modular arithmetic the possible residues set includes only whole numbers, nothing in between, so division in usual sense is not working.

Instead, think in multiplicative terms: which value becomes 1 when doubled? That is the modular version of one half.

Question: Find the multiplicative inverse of 7 modulo 26

modulus b

gcd(a, b)

Rewrite the congruence as a linear equation:

$$
7x \equiv 1\pmod{26}  => 7x = 1 + 26y
$$

Display as a [linear Diophantine equation](https://web3-lab.annaburd.me/math-behind-key-pairs/#linear-diophantine-equation):

$$
7x - 26y = 1
$$

So finding the multiplicative inverse is the same as finding integer coefficients recipes that make up number 1 with the ingredients 7 and 26.

A multiplicative inverse exists only when gcd(a, b) = 1

The equation ax + by = c has an integer solution only when $\gcd(a, b) \mid c$.

$$
g = \gcd(a, b), \quad a = a_0 g, \quad b = b_0 g
$$

$$
ax + by = a_0 g x + b_0 g y = \left(a_0 x + b_0 y\right)g
$$

The left-hand side is always a multiple of g = gcd(a, b), so c must also be a multiple of g. This is the same condition that comes from [Bézout's identity](https://web3-lab.annaburd.me/math-behind-key-pairs/#bezout-identity).

For multiplicative inverses we solve ax + by = 1. Since the left-hand side is divisible by g = gcd(a, b), the right-hand side must also be divisible by g. The only possibility is g = 1 (since 1 is the only positive integer that divides 1).

Solve the equation 7x - 26y = 1 using the extended Euclidean algorithm. When the final gcd is 1, the coefficient of a is the multiplicative inverse modulo b.

Step 1

=

3 ·

Step 2

=

1 ·

Step 3

=

2 ·

x-11

Step 4

=

2 ·

x-11

Solution

Because gcd(7, 26) = 1, the equation has a solution and the x-coefficient gives the inverse.

$$
1 = 7 \cdot (-11) + 26 \cdot (3)
$$

$$
x = -11 \equiv 15 \pmod{26}
$$

$$
7^{-1} \pmod{26} = 15
$$

$$
7 \cdot 15 = 105 \equiv 1 \pmod{26}
$$

## Pattern aⁿ-n (mod n)

Residues

Possible residues are {0, 1, 2}.

| n (mod 3) | n³ (mod 3) |
| --- | --- |
| 0 | 0³ = 0 |
| 1 | 1³ = 1 |
| 2 | 2³ = 8 ≡ 2 |

Whatever the residue of n modulo 3 is, n³ has the same residue. So n³ - n is divisible by 3, equivalently:

$$
n³ - n \equiv 0 \pmod{3}
$$

Residues

Possible residues are {0, 1, 2, 3, 4}.

| n (mod 5) | n⁵ (mod 5) |
| --- | --- |
| 0 | 0⁵ = 0 |
| 1 | 1⁵ = 1 |
| 2 | 2⁵ = 32 ≡ 2 |
| 3 | 3⁵ = 243 ≡ 3 |
| 4 | 4⁵ = 1024 ≡ 4 |

Whatever the residue of n modulo 5 is, n⁵ has the same residue. So n⁵ - n is divisible by 5, equivalently:

$$
n⁵ - n \equiv 0 \pmod{5}
$$

Residues

Possible residues are {0, 1, 2, 3, 4, 5, 6}.

| n (mod 7) | n⁷ (mod 7) |
| --- | --- |
| 0 | 0⁷ = 0 |
| 1 | 1⁷ = 1 |
| 2 | 2⁷ = 2·(2³)² ≡ 2·1² ≡ 2 |
| 3 | 3⁷ = 3·(3²)³ ≡ 3·2³ ≡ 3·1 ≡ 3 |
| 4 | 4⁷ = 4·(4²)³ ≡ 4·2³ ≡ 4·1 ≡ 4 |
| 5 | 5⁷ = 5·(5³)² ≡ 5·6² ≡ 5·1 ≡ 5 |
| 6 | 6⁷ = 6·(6²)³ ≡ 6·1³ ≡ 6 |

Whatever the residue of n modulo 7 is, n⁷ has the same residue. So n⁷ - n is divisible by 7, equivalently:

$$
n⁷ - n \equiv 0 \pmod{7}
$$

Residues

Possible residues are {0, 1, 2, 3, 4, 5, 6, 7, 8}.

| n (mod 9) | n⁹ (mod 9) | n⁹ - n |
| --- | --- | --- |
| 0 | 0⁹ = 0 | 0 |
| 1 | 1⁹ = 1 | 0 |
| 2 | 2⁹ = (2³)³ ≡ 8³ ≡ 8 | 8 - 2 = 6 |
| 3 | 3⁹ ≡ 0 | 0 - 3 = -3 ≡ 6 |
| 4 | 4⁹ = (4³)³ ≡ 1³ ≡ 1 | 1 - 4 = -3 ≡ 6 |
| 5 | 5⁹ = (5³)³ ≡ 8³ ≡ 8 | 8 - 5 = 3 |
| 6 | 6⁹ ≡ 0 | 0 - 6 = -6 ≡ 3 |
| 7 | 7⁹ = (7³)³ ≡ 1³ ≡ 1 | 1 - 7 = -6 ≡ 3 |
| 8 | 8⁹ = 8·(8²)⁴ ≡ 8·1⁴ ≡ 8 | 8 - 8 = 0 |

Does not work in general: n⁹ - n is not always divisible by 9, e.g. 2⁹ - 2 = 510 ≡ 6 (mod 9).

Residues

Possible residues are {0, 1, 2,..., 36}.

| n (mod 37) | n³⁷ (mod 37) |
| --- | --- |
| 0 | 0³⁷ ≡ 0 |
| 1 | 1³⁷ ≡ 1 |
| 2 | 2³⁷ = 137438953472 ≡ 2 |
| 3 | 3³⁷ = (-34)³⁷ = -34³⁷ = -34 ≡ 3 |
| 4 | 4³⁷ = (2²)³⁷ = 2³⁷ * 2³⁷ = 2 * 2 = 4 |
| 5 | 5³⁷ = (-32)³⁷ = -32³⁷ = -32 ≡ 5 |
| 6 | 6³⁷ = (2·3)³⁷ = 2³⁷ · 3³⁷ = 2 · 3 = 6 |
| 7 | 7³⁷ = (-30)³⁷ = -30³⁷ = -30 ≡ 7 |
| 8 | 8³⁷ = (2³)³⁷ = 2³⁷ * 2³⁷ * 2³⁷ = 2 * 2 * 2 = 8 |
| 9 | 9³⁷ = (3²)³⁷ = 3³⁷ * 3³⁷ = 3 * 3 = 9 |
| 10 | 10³⁷ = (2·5)³⁷ = 2³⁷ · 5³⁷ = 2 · 5 = 10 |
| 11 | 11³⁷ = (-26)³⁷ = -26³⁷ = -26 ≡ 11 |
| 12 | 12³⁷ = (2·2·3)³⁷ = 2³⁷ · 2³⁷ · 3³⁷ = 2 · 2 · 3 = 12 |
| 13 | 13³⁷ = (-24)³⁷ = -24³⁷ = -24 ≡ 13 |
| 14 | 14³⁷ = (2·7)³⁷ = 2³⁷ · 7³⁷ = 2 · 7 = 14 |
| 15 | 15³⁷ = (3·5)³⁷ = 3³⁷ · 5³⁷ = 3 · 5 = 15 |
| 16 | 16³⁷ = (2⁴)³⁷ = 2³⁷ * 2³⁷ * 2³⁷ * 2³⁷ = 2 * 2 * 2 * 2 = 16 |
| 17 | 17³⁷ = (-20)³⁷ = -20³⁷ = -20 ≡ 17 |
| 18 | 18³⁷ = (2·3·3)³⁷ = 2³⁷ · 3³⁷ · 3³⁷ = 2 · 3 · 3 = 18 |
| 19 | 19³⁷ = (-18)³⁷ = -18³⁷ = -18 ≡ 19 |
| 20 | 20³⁷ = (2·10)³⁷ = 2³⁷ · 10³⁷ = 2 · 10 = 20 ≡ -17 |
| 21 | 21³⁷ = (3·7)³⁷ = 3³⁷ · 7³⁷ = 3 · 7 = 21 |
| 22 | 22³⁷ = (2·11)³⁷ = 2³⁷ · 11³⁷ = 2 · 11 = 22 |
| 23 | 23³⁷ = (-14)³⁷ = -14³⁷ = -14 ≡ 23 |
| 24 | 24³⁷ = (2·2·2·3)³⁷ = 2³⁷ · 2³⁷ · 2³⁷ · 3³⁷ = 2 · 2 · 2 · 3 = 24 |
| 25 | 25³⁷ = (5²)³⁷ = 5³⁷ * 5³⁷ = 5 * 5 = 25 |
| 26 | 26³⁷ = (2·13)³⁷ = 2³⁷ · 13³⁷ = 2 · 13 = 26 |
| 27 | 27³⁷ = (3³)³⁷ = 3³⁷ * 3³⁷ * 3³⁷ = 3 * 3 * 3 = 27 |
| 28 | 28³⁷ = (4·7)³⁷ = 4³⁷ · 7³⁷ = 4 · 7 = 28 |
| 29 | 29³⁷ = (-8)³⁷ = -8³⁷ = -8 ≡ 29 |
| 30 | 30³⁷ = (2·10)³⁷ = 2³⁷ · 10³⁷ = 2 · 10 = 30 |
| 31 | 31³⁷ = (-6)³⁷ = -6³⁷ = -6 ≡ 31 |
| 32 | 32³⁷ = (2⁵)³⁷ = 2³⁷ * 2³⁷ * 2³⁷ * 2³⁷ * 2³⁷ = 2 * 2 * 2 * 2 * 2 = 32 |
| 33 | 33³⁷ = (-4)³⁷ = -(2²)³⁷ = -2³⁷ * 2³⁷ = -2 * 2 = -4 ≡ 33 |
| 34 | 34³⁷ = (17·2)³⁷ = 17³⁷ · 2³⁷ = 17 · 2 = 34 |
| 35 | 35³⁷ = (-2)³⁷ = -2³⁷ = -2 ≡ 35 |
| 36 | 36³⁷ = (-1)³⁷= -1 ≡ 36 |

Whatever the residue of n modulo 37 is, n³⁷ has the same residue. So n³⁷ - n is divisible by 37, equivalently:

$$
n ^{37} - n \equiv 0 \pmod{37}
$$

## Fermat's little theorem

Cancellation in modular arithmetic

Let's start with $ac \equiv bc \pmod{m}$. It is tempting to cancel the shared factor and jump to $a \equiv b \pmod{m}$, but is this always valid?

A counterexample is $2\cdot 3 \equiv 2\cdot 6 \pmod{6}$, where $3 \not\equiv 6 \pmod{6}$.

In what cases we can be sure that cancellation is valid?

$$
ac \equiv bc \pmod{m} \Rightarrow ac-bc \equiv 0 \pmod{m}
$$

$$
\Rightarrow c(a-b) \equiv 0 \pmod{m}\text{, here either }c \equiv 0 \text{ or } a-b\equiv 0\text{ or a combination of factors from both } a-b \text{ and } c
$$

To conclude $a-b \equiv 0 \pmod{m}$, we need to be sure that $c$ is not having common factors with $m$. That is, $\gcd(c,m)=1$.

$$
\left\{\begin{array}{l}ac \equiv bc \pmod{m}\\ \gcd(c,m)=1\end{array}\right.\;\Longrightarrow\; a \equiv b \pmod{m}
$$

Pattern aⁿ-n (mod n)

The [section above](https://web3-lab.annaburd.me/math-behind-key-pairs/#pattern-an-minus-n-mod-n) demonstrates that for some numbers, such as $m=3,5,7,37$, the quantity $a^{m-1}-1$ is always divisible by $m$. For other numbers, such as $m=9$, the pattern does not hold.

Fermat's little theorem proves that for prime moduli $p$, the quantity $a^{p-1}-1$ (or, in the same pattern form, $a^p-a$) is always divisible by $p$, provided $p \nmid a$.

Proof for Fermat's little theorem

$$
\text{If } p \text{ is prime and } p \nmid a,\ \text{then } a^{p-1} \equiv 1 \pmod{p}.
$$

Residues

Possible non-zero residues modulo $p$ are $\{1,2,\dots,p-1\}$.

| $r \pmod{p}$ | $a \cdot r \pmod{p}$ | $\equiv r_1, r_2, \dots, r_{p-1} \pmod{p}$ |
| --- | --- | --- |
| $1$ | $a$ | $\equiv r_1$ |
| $2$ | $2a$ | $\equiv r_2$ |
| $3$ | $3a$ | $\equiv r_3$ |
| $\vdots$ | $\vdots$ | $\vdots$ |
| $p-1$ | $(p-1)a$ | $\equiv r_{p-1}$ |

Setup

$$
\text{The non-zero residues modulo } p \text{ are } 1,2,\dots,p-1.
$$

$$
\text{Multiply each of them by } a. \text{ Let } r_k \equiv ka \pmod{p} \text{ for } k=1,2,\dots,p-1.
$$

Distinctness

$$
\text{Suppose two of the new residues are equal: } r_l \equiv r_k \pmod{p} \text{ with } l \ne k.
$$

$$
\text{Then } la \equiv ka \pmod{p}.
$$

$$
\text{Since } p \nmid a,\ \gcd(a,p)=1,\ \text{we can cancel } a \text{ and obtain } l \equiv k \pmod{p}.
$$

$$
\text{But } l,k \in \{1,2,\dots,p-1\},\ \text{so this implies } l=k, \text{ a contradiction.}
$$

$$
\text{Therefore } r_1,r_2,\dots,r_{p-1} \text{ are all distinct.}
$$

Non-zero

$$
\text{None of them is } 0 \pmod{p}.
$$

$$
\text{If } r_k \equiv ka \equiv 0 \pmod{p},\ \text{then } p \mid ka.
$$

$$
\text{This is impossible because } p \nmid a \text{ and } p \nmid k \text{ for } 1 \le k \le p-1.
$$

Rearrangement

$$
\text{Thus } r_1,r_2,\dots,r_{p-1} \text{ are exactly the numbers } 1,2,\dots,p-1 \text{ in some order modulo } p.
$$

Permutation Intuition

Each arrow shows r -> a*r (mod p). Multiplying every residue by a rearranges the circle.

prime p

multiplier a

Every arrow lands on a different non-zero residue. Changing a rewires the same circle into a new permutation.

Effective Multiplier

3 (since 3 mod 7 = 3)

Behavior

Permutes the non-zero residues

Cycles

(1 3 2 6 4 5)

Multiplying by a permutes the non-zero residues modulo p.

Product

$$
\text{Multiply the congruences } ka \equiv r_k \pmod{p} \text{ for } k=1,2,\dots,p-1.
$$

$$
\text{The left side becomes } (1a)(2a)\cdots((p-1)a) = a^{p-1}(1\cdot2\cdots(p-1)).
$$

$$
\text{So } a^{p-1}(1\cdot2\cdots(p-1)) \equiv r_1 r_2 \cdots r_{p-1} \pmod{p}.
$$

$$
\text{Because } r_1,r_2,\dots,r_{p-1} \text{ is the same residue set as } 1,2,\dots,p-1,\ \text{when multiplied together it is the same as } r_1 r_2 \cdots r_{p-1} \equiv 1\cdot2\cdots(p-1) \pmod{p}.
$$

$$
\text{Rewriting } 1\cdot2\cdots(p-1) \text{ as factorial} (p-1)!,\ \text{we get }  a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}.
$$

$$
a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}
$$

$$
\gcd((p-1)!,p)=1 \text{ because } p \text{ is prime and none of } 1,2,\dots,p-1 \text{ is divisible by } p \text{, so we can cancel } (p-1)! \text{ from both sides}
$$

$$
\therefore a^{p-1} \equiv 1 \pmod{p}
$$

$$
\text{Multiplying both sides by } a \text{ gives another form: } a^p-a \equiv 0 \pmod{p} \text{ or } a^p \equiv a \pmod{p}
$$

## Euler's theorem

Generalizing Fermat's little theorem

Euler extended the idea from the [Fermat's little theorem](https://web3-lab.annaburd.me/math-behind-key-pairs/#fermats-little-theorem) from primes (mod p) to modulus (mod n), using the totient function $\varphi(n)$.

The theorem says that if $\gcd(a,n)=1$, then powers of $a$ cycle in a way controlled by Euler's totient function $\varphi(n)$:

$$
a^{\varphi(n)} \equiv 1 \pmod{n}
$$

Totient Function

Totient function $\varphi(n)$ counts the numbers from $1$ up to $n-1$ that are coprime to $n$.

Prime Factors of n

Totient

Totient Filter

Integers 1 to n-1

φ1

φ2

φ3

φ4

Euler Product

Each distinct prime divisor removes a fraction of the residue classes, leaving exactly $\varphi(n)$ survivors.

These surviving residues are the ones Euler's theorem multiplies and permutes, just like Fermat permutes the full non-zero set when the modulus is prime.

$\varphi(12) = 12$$\left(1-\frac{1}{\textcolor{deeppink}{2}}\right)$$\left(1-\frac{1}{\textcolor{firebrick}{3}}\right)$$= 4$

Proof for Euler's theorem

$$
\text{If } \gcd(a,n)=1,\ \text{then } a^{\varphi(n)} \equiv 1 \pmod{n}.
$$

Possible residues

The possible residues set is the reduced residue system modulo $n$:

$$
\{\alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)}\},\ \text{where } \gcd(\alpha_i,n)=1 \text{ for every } i
$$

| $\alpha_i$ | $a \cdot \alpha_i$ | $\equiv r_i \pmod{n}$ |
| --- | --- | --- |
| $\alpha_1$ | $a\alpha_1$ | $\equiv r_1$ |
| $\alpha_2$ | $a\alpha_2$ | $\equiv r_2$ |
| $\alpha_3$ | $a\alpha_3$ | $\equiv r_3$ |
| $\vdots$ | $\vdots$ | $\vdots$ |
| $\alpha_{\varphi(n)}$ | $a\alpha_{\varphi(n)}$ | $\equiv r_{\varphi(n)}$ |

Setup

$$
\text{Let } \{\alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)}\} \text{ be the reduced residue system modulo } n.
$$

$$
\text{Each } \alpha_i \text{ satisfies } 1 \le \alpha_i < n \text{ and } \gcd(\alpha_i,n)=1.
$$

$$
\text{Multiply each of them by } a. \text{ Let } r_i \equiv a\alpha_i \pmod{n} \text{ for } i=1,2,\dots,\varphi(n).
$$

Distinctness

$$
\text{Suppose two new residues are equal: } r_i \equiv r_j \pmod{n} \text{ with } i \ne j.
$$

$$
\text{Then } a\alpha_i \equiv a\alpha_j \pmod{n}.
$$

$$
\text{Since } \gcd(a,n)=1,\ \text{we may cancel } a \text{ and obtain } \alpha_i \equiv \alpha_j \pmod{n}.
$$

$$
\text{But } \alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)} \text{ are distinct residues modulo } n, \text{ so this is impossible.}
$$

$$
\text{Therefore } r_1,r_2,\dots,r_{\varphi(n)} \text{ are all different.}
$$

Still Coprime

$$
\text{Each } r_i \text{ is also coprime to } n.
$$

$$
\gcd(r_i,n)=\gcd(a\alpha_i,n)=1 \text{ because } \gcd(a,n)=1 \text{ and } \gcd(\alpha_i,n)=1.
$$

$$
\text{So every } r_i \text{ is another residue from the same reduced residue system modulo } n.
$$

Rearrangement

$$
\text{There are } \varphi(n) \text{ of these residues, they are all different, and each is coprime to } n.
$$

$$
\text{Hence } r_1,r_2,\dots,r_{\varphi(n)} \text{ are exactly } \alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)} \text{ in some order modulo } n.
$$

Permutation Intuition

Each arrow shows r -> a*r (mod n), but only on residues coprime to n. Grey nodes are filtered out by Euler's totient.

modulus n

multiplier a

Effective Multiplier

5 (since 5 mod 12 = 5)

Behavior

Permutes the reduced residues

Reduced Set

4 residues, cycles (1 5) (7 11)

Multiplying by a permutes only the residues coprime to n; the grey residues are excluded from Euler's theorem.

Product

$$
\text{Multiply the congruences } a\alpha_i \equiv r_i \pmod{n} \text{ for } i=1,2,\dots,\varphi(n).
$$

$$
\text{The left side becomes } (a\alpha_1)(a\alpha_2)\cdots(a\alpha_{\varphi(n)}) = a^{\varphi(n)}\alpha_1\alpha_2\cdots\alpha_{\varphi(n)}.
$$

$$
\text{Thus } a^{\varphi(n)}\alpha_1\alpha_2\cdots\alpha_{\varphi(n)} \equiv r_1r_2\cdots r_{\varphi(n)} \pmod{n}.
$$

$$
\text{Because } r_1,r_2,\dots,r_{\varphi(n)} \text{ is the same residue set as } \alpha_1,\alpha_2,\dots,\alpha_{\varphi(n)},
$$

$$
r_1r_2\cdots r_{\varphi(n)} \equiv \alpha_1\alpha_2\cdots\alpha_{\varphi(n)} \pmod{n}.
$$

$$
a^{\varphi(n)}\alpha_1\alpha_2\cdots\alpha_{\varphi(n)} \equiv \alpha_1\alpha_2\cdots\alpha_{\varphi(n)} \pmod{n}
$$

$$
\gcd(\alpha_1\alpha_2\cdots\alpha_{\varphi(n)},n)=1 \text{ because every } \alpha_i \text{ is coprime to } n \text{, so we can cancel the product}
$$

$$
\therefore a^{\varphi(n)} \equiv 1 \pmod{n}
$$

$$
\text{When } n=p \text{ is prime, the reduced residue system is } 1,2,\dots,p-1 \text{, so this becomes Fermat's little theorem.}
$$

## Cryptography

With the number theory in place, the algorithms it was built for become readable - key exchange, public-key encryption, signatures, symmetric ciphers, and hash functions.

[See how cryptography works](https://web3-lab.annaburd.me/how-cryptography-works/)