Lecture notes from this year (2021): lec-Week4-Mon.pdf (scanned notes).

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.

There is Haskell code that implements finding the solutions to systems of congruences using the Chinese Remainder Theorem.

In the lecture, we saw a method for solving the Chinese remainder theorem, the same one as in the book.

Here is another, more direct method:

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 \]