Lecture 1

Toy example (RSA encryption)

$Enc$

1. Choose a letter, count to number of letters in the alphabet.
2. Calculate $s^7$, then divide by 33, take the remainder.
3. Send the remainder.

$Dec: s = r^3 \mod 33$

To build up such system.

Step 1: Understanding the arithmetic of remainders.

Part 1: Divisibility and prime numbers

Divisibility and division algorithm

Let $a, b\in \mathbb{Z}$, with $b>0$. There are unique integers, $q$ (quotient) and $r$ (remainder), such that $a = bq + r$ and $0 \leq r < b$.

Example: $31=7\times 4 + 3$

Proof:

The quotient and remainder are unique.

(1) Existence:

Let $S = \{a - bk \mid k \in \mathbb{Z}, a - bk \geq 0\}$. Choose $r$ to be the smallest non-negative element of $S$. This means $r = a - bq$ for some $q \in \mathbb{Z}$. i.e. $a=bq+r$.

New notion: $\triangle FSOC$ means For the sake of contradiction.

Notice that $r \geq 0$, by contradiction, suppose $r \geq b$, then $r-b \geq 0$ and $r-b \in S$, but $r-b < r$, which contradicts the minimality of $r$.

Therefore, $r \geq 0$ and $r < b$.

Example: $a=31, b=7$, $S = \{31-7k \mid k \in \mathbb{Z}, 31-7k \geq 0\}=\{\cdots, -32, -25, -18, -11, -4, 3, 10, 17, 24, 31, \cdots\}$, $r=3$.

So We choose $q=4$ and $r=3$.

(2) Uniqueness:

Suppose we have two pairs $(q, r)$ and $(q', r')$ such that $a = bq + r = bq' + r'$ Suppose $q \neq q'$, without loss of generality, suppose $q > q'$, $q-q' \geq 1$. Then $b(q-q') = r'-r$.

Since $r'=b(q-q')+r \geq b(q-q') \geq b$, which contradicts that $r' < b$.

Therefore, $q=q'$ and $r=r'$.

QED

Definition: Divisibility

Let $a, b \in \mathbb{Z}$, we say $b$ divides $a$ and write $b \mid a$ if there exists $k\in \mathbb{Z}$ such that $a = bk$.

Example: $3 \mid 12$ because $12 = 3 \times 4$.

Properties of divisibility

Let $a, b, c \in \mathbb{Z}$.

(1) $b \mid a \iff r=0$ in the division algorithm.

(2) If $a \mid b$ and $b \mid c$, then $a \mid c$.

(3) If $a \mid b$ and $b \mid a$, then $a = \pm b$.

(4) If $a \mid b$ and $a \mid c$, then $a \mid bx + cy$ for all $x, y \in \mathbb{Z}$. (We call such $bx+cy$ a linear combination of $b$ and $c$.)

(5) If $c\neq 0$ and $a \mid b \iff ac \mid bc$.

Some proof examples:

(2) Since $a \mid b$ and $b \mid c$, there exist $k, l \in \mathbb{Z}$ such that $b = ak$ and $c = bl$. Then $c = bl = (ak)l = a(kl)$, so $a \mid c$.

QED

(3) If $a \mid b$ and $b \mid a$, then there exist $k, l \in \mathbb{Z}$ such that $b = ak$ and $a = bl$. Then $a = bl = (ak)l = a(kl)$, so $a(1-kl) = 0$.

Case 1: $a=0$, then $b=0$, so $a=b$.

Case 2: $a \neq 0$, then $1-kl=0$, so $kl=1$. Since $k, l \in \mathbb{Z}$, $k=l=\pm 1$, so $a = \pm b$.

QED

Definition: Divisor

Let $a\in \mathbb{Z}$, we define $D(a) = \{d\in \mathbb{Z} \mid d \mid a\}$.

Note that $D(0) = \mathbb{Z}$.

Example: $D(12) = \{\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12\}$.

Definition: Greatest common divisor

Let $a, b \in \mathbb{Z}$, where $a,b$ not both zero, we define the greatest common divisor of $a$ and $b$ to be the largest element in $D(a) \cap D(b)$. It is denoted by $(a,b)$.

Terrible, I really hate this notation. But professor said it’s unlikely to be confused with the interval $(a,b)$ since they don’t show up in the same context usually.

Example:

$(12, 18) = 6$.

Note that $(0,0)$ is not defined. (there is no largest element in $D(0) \cap D(0)$.)

but it is okay that one of $a, b$ is zero. For example, $(0, 18) = 18$.

$(n,n) = |n|$ for all $n \in \mathbb{Z}$.

In general, if $(a,b)=0$ we say $a$ and $b$ are relatively prime, or coprime.

$\forall a, b \in \mathbb{Z}$, $(a,b) \geq 1$.

Theorem for calculating gcd

Let $a, b \in \mathbb{Z}$, with $b\neq 0$, then for any $k\in \mathbb{Z}$, $(a,b) = (b,a-bk)$.

Example: $(12, 18) = (18, 12-18) = (18, -6) = 6$.

$(938,210)=(210,938-210\times 4)=(210,938-840)=(210,98)$.

Proof:

We will prove that $D(a) \cap D(b) = D(b) \cap D(a-bk)$.

(1) $D(a) \cap D(b) \subseteq D(b) \cap D(a-bk)$:

Let $d \in D(a) \cap D(b)$, then $d \mid a$ and $d \mid b$.

By property of divisibility (4), If $a\mid b$ and $b\mid c$, then for all $x,y\in \mathbb{Z}$, $a\mid bx+cy$.

So $d\mid a+b\cdot (-k) = a-bk$.

Therefore, $d \in D(b) \cap D(a-bk)$.

(2) $D(b) \cap D(a-bk) \subseteq D(a) \cap D(b)$:

Let $d \in D(b) \cap D(a-bk)$, then $d \mid b$ and $d \mid a-bk$.

By property of divisibility (4), $d \mid bk + (a-bk) = a$.

Therefore, $d \in D(a) \cap D(b)$.

QED

This theorem gives rise to the Euclidean algorithm which is a efficient way to compute the greatest common divisor of two integers. $2\Theta(\log n)+1=O(\log n)$ (Proof in CSE 442T Lecture 7 ).

Euclidean algorithm

We will skip this part, it’s already the third time we see this algorithm in wustl.

Theorem: Euclidean algorithm returns correct gcd

Let $a>b>0$, be integers. Using the Euclidean algorithm, we can find $b>r_0>r_1>r_2>\cdots>r_n$ such that $a=bq_0+r_0, b=r_0q_1+r_1, \cdots, r_{n-1}=r_nq_{n+1}+r_{n+1}, r_n=0$. Then $(a,b)=r_n$.

Proof:

(a) This process terminates. $b>r_0>r_1>r_2>\cdots>r_n$ is a strictly decreasing sequence of positive integers, so it must terminate.