NoteNextra-origin/content/Swap/Math4351_L1.md

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.