Lecture notes on Arithmetic

These notes span 4 different lectures:

• Divisibility and Primes

• Diophantine equations

• Modulo arithmetic

• RSA cryptography

Haskell code implementing some of these methods. You can look at the code to understand the methods, and also run it on examples.

Notes and Examples on The Pulverizer and the Chinese Remainder Theorem (swedish, pdf).

---

Divisibility

We defined what divisibility is, written b | a; "b divides a".

We defined what greatest common divisor (gcd) is, written gcd(a,b), and learned about Euclid's method of computing it.

We saw how we could use The Pulverizer (also called Bezout's method) to find u and v such that a^.u + b^.v = 1, for a and b such that gcd(a,b) = 1.

We saw Euclid's lemma and proved it: If p is prime, and p | a^.b, then p | a or p | b. We used the Pulverizer to prove this.

---

Diophantine equations

Diophantine equations are equations for which we are only interested in integer solutions. The example we study is: a^.x + b^.y = c, for constants a, b, c and in the solution, x and y have to be in $\mathbb{Z}$.

Every natural number ≥2 can be written as a product of prime numbers, in exactly one way. We proved this in the lecture, using Euclid's lemma.

---

Modulo Arithmetic

We will learn what modulo arithmetic is.

We will see the Chinese remainder theorem.

We will learn about relations: reflexivity, symmetry, transitivity, equivalence.

---

In the lecture, we saw the following method for solving the Chinese remainder theorem:

We want to find an integer number $x$ such that the following two congruences hold, simultaneously: $$x \equiv a \; ( \text{mod}\; m_1 ) \\ x \equiv b \; ( \text{mod}\; m_2 )$$ Here, we require that $\text{gcd}(m_1,m_2)=1$.

How to go about finding such an $x$? First, we can use the definition of what $\equiv$ means, namely that the difference of the left-hand side and the right-hand side must be a multiple of the modulo: $$x = a + k_1 \cdot m_1 \\ x = b + k_2 \cdot m_2$$ So, we have to find $k_1$ and $k_2$ such that the above holds. If we find $k_1$ and $k_2$ first, we can then calculate $x$. So, we first remove $x$ from the equations altogether, and get: $$a + k_1 \cdot m_1 = b + k_2 \cdot m_2$$ (Because both sides should be equal to $x$.) Rewriting the above, we get: $$k_1 \cdot m_1 - k_2 \cdot m_2 = b - a$$ This is just a diophantine equation, with constants $m_1, m_2$ and $b-a$, and variables $k_1$ and $k_2$! We know how to solve those... We start by finding $u, v$ such that: $$u \cdot m_1 + v \cdot m_2 = 1$$ ...which we do using the Pulverizer.

The solution for $k_1$ and $k_2$ is then multiplying $u$ and $v$ by $b-a$, as usual. (For $k_2$, we have to add an extra $-$-sign because it appears negative in the original equation): $$k_1 = u \cdot (b - a) \\ k_2 = -v \cdot (b - a)$$ (Check for yourself that this is an actual solution of the original equation!)

So, we have found $k_1$ and $k_2$, so now we can compute $x$. We can use either one of the following equations: $$x = a + k_1 \cdot m_1 \\ x = b + k_2 \cdot m_2$$ Filling in what $k_1$ and $k_2$ are, we get: $$x = a + u \cdot (b-a) \cdot m_1$$ or, alternatively, $$x = b - v \cdot (b-a) \cdot m_2$$ Both of these give the same answer for $x$.

---

From the above, we can derive a simple recipe for solving a system of two congruences. To solve: $$x \equiv a \; ( \text{mod}\; m_1 ) \\ x \equiv b \; ( \text{mod}\; m_2 )$$ with $\text{gcd}(m_1,m_2)=1$, we first find $u, v$ such that: $$u \cdot m_1 + v \cdot m_2 = 1$$ And then we calculate $x$ as follows: $$x = a + u \cdot (b-a) \cdot m_1$$

---

RSA cryptography

We will start with a MAGIC TRICK!

We will see Fermat's little theorem.

We will see how RSA cryptography works and why.