Arithmetic and applications

Arithmetic and applications#

Numerical systems#

Numerals and positional notation#

Numbers are one of the most basic mathematical objects, one with which we interact daily: we use them to count, order, label, encode.

Throughout history, numbers have been represented in a variety of ways, for example:

$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
	I	II	III	IV	V	VI	VII	VIII	IX	X
੦	੧	੨	੩	੪	੫	੬	੭	੮	੯	੧੦
	Α	Β	Γ	Δ	Ε	Ϝ	Ζ	Η	Θ	Ι

Out of those, the widely used is, of course, the Indo-Arabic numeral system, invented between the 1st and 4th centuries by Indian mathematicians and later adopted by Arab and Persian mathematicians during the 9th century. The system later spread to Europe during the 13th century where it was not widely adopted before the 15th century.

The Indo-Arabic numeral system works as follows:

A natural number is written as a sequence of symbols taken from the alphabet $0,1,2,3,4,5,6,7,8,9$, which correspond to the first 10 natural numbers.
The value represented by such a sequence is the sum of the value of each digit multiplied by some power of $10$: reading a numeral from right to left, the $n$-th digit is multiplied by $10^{n-1}$.

For example, the numeral $123$ represents the number $1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^1 = 100 + 20 + 3$.

We may generalise the Indo-Arabic numeral system to obtain systems which use positional notation:

Numbers are represented by sequences of symbols, called digits, drawn from some finite alphabet.
The value represented by a numeral (a sequence of symbols) is the value represented by the symbol times some factor determined by the position of the symbol in the sequence.

The factor is usually the power of some fixed number $b$, called the base of the system.

For example the Indo-Arabic numeral system is a base-10 positional notation system using the usual digits $0$ through $9$. Other historically significant bases are 8, 12, 20, 60 which where widely used by various cultures ranging from the Babylonians to Mayans.

For a number to have a unique representation in such as system, we require that the number of digits is $b-1$. For bases $b \leq 10$, the digits are drawn using the same symbols $0, 1, \dots 9$ that we use for base-10. For bases $b \geq 10$ we of course need to invent new symbols to represent values greater than 9. For example, in a base-16 system we augment the alphabet of digits with the letters $A, B, C, D, E, F$ which correspond to $10, 11, 12, 13, 14, 15$ in base-10.

In computer science we often use the binary (base-2) and hexadecimal (base-16) systems. For example, the number twenty has the following representations in bases 2, 10, 16:

In base-2: $(10100)_2 = 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0$,
In base-10: $(20)_{10} = 2 \cdot 10^1 + 0 \cdot 10^0$,
In base-16: $(14)_{16} = 1 \cdot 16^1 + 4 \cdot 16^0$,

where the $(\cdot)_{b}$ notation means that the numeral in the parenthesis is to be interpreted in base $b$. Similarly, the number 29 is written as $(11101)_2, (1D)_{16}$ in binary and hexadecimal.

More generally, we can decompose a number $N$ in any base $b$ as follows:

\[ N = \sum\limits_{i=0}^n N_i b^i \]

where $n \in \mathbb{N}$, $N_i$ are coefficients in $[0,b-1]$ and $N_n$ is non-zero. These coefficients $N_i$ are called “bits” in the binary (base-2) case. The numbers $n, b, N$ are linked by the following formula:

\[ n = \left\lfloor \frac{log(N)}{log(b)} \right\rfloor = \left\lfloor \log_b(N) \right\rfloor.\]

where $\lfloor \cdot \rfloor$ is the integer part function, $\log$ is the logarithm in base 10, and $\log_b$ is the logarithm in base $b$.

Base conversion#

As we’ve seen, any number can be represented in various bases. How do we go about converting between these different representations? The answer is given by repeated Euclidean division but there’s a catch: which base should we use to perform our calculations?

Suppose that we met a member of an alien civilisation who only knows how to perform base-4 arithmetic, notably how to do Euclidean division, and who wants to convert $(32)_4$ to its equivalent base-8 numeral.

Actually do I even need this:

Remark 1

Note that we keep expressing everything in base-10, representing the numbers “four” and “eight” in base-10 as $(4)_{10}$ and $(8)_{10}$, without being explicit about our choice of base.

However, for our alien friend $(4)_{10} = (10)_4$ and $(8)_{10} = (20)_4$, so they would probably express their desire as wanting to convert $(32)_10$ to $(32)_20$!

Of course our friend would most probably not even be using Indo-Arabic digits $0, \dots, 9$, but let’s assume we’ve already translated their symbols!

To help our alien friend, we must first construct a basic lookup table $T$ which contains the first eight numerals written in both bases:

1	2	3	10	11	12	13	20
1	2	3	4	5	6	7	10

We could then proceed as follows:

Calculate the quotient $q$ and remainder $r$ of the Euclidean division of $(32)_4$ by $(20)_4$ (remember we are working in base-4) : $q = (1)_4, r = (12)_4$.
Convert $(12)_4$ to $(6)_8$ using our lookup table.
Repeat this procedure by dividing $(1)_4$ by $(20)_4$ yields $q = 0, r = 1$.
Convert $(1)_4$ to $(1)_8$ using our lookup table.
Concatenate the two numbers (right to left) to obtain the desired result $(16)_8$.

Therefore we have calculated that $(32)_4$ is $(16)_8$.

Such a procedure can be quite cumbersome since:

It requires us to create a lookup symbol to convert between the digits of the two bases.
It requires us to perform arithmetic in bases other than 10, which isn’t always intuitive!

In practice we therefore usually convert between two bases $b$ and $b'$ by converting first to base $10$ and then from there to $b'$, taking advantage of our familiarity with division in base-10.

Finally, there’s various tricks for passing quickly between specific bases. For computer scientists, a particularly useful one is the following trick for converting from binary to hexadecimal and vice versa:

Let $N$ be a number written in base-2.
Split $N$ in groups of $4$, padding with 0 in the beginning if required.
Convert the groups of $4$ bits to their equivalent value in hexadecimal (using a lookup table for example).
Concatenate the results of the conversion to obtain the equivalent hexadecimal numeral.

Conversely:

Let $N$ be a number written in base-16.
Convert every digit of $N$ to its equivalent 4-bit binary number (padded as necessary).
Concatenate the results (right to left) to obtain the equivalent binary numeral.

The mathematical justification for the above follows from the fact that $16 = 2^4$ (similar tricks hold for converting between a base $b$ and a base $b' = b^k$ for some $k \geq 2$).

For example, for $N = (1010110101010110011110111)_2$ we first notice that it has 25 digits, so we prepend three zeros to obtain an equivalent numeral $N = (0001010110101010110011110111)_2$ with $28$ digits which is divisible by $4$. We then have the following 7 packets and their corresponding hexadecimals (from right to left):

$(0111)_2 = (7)_{16}$,
$(1111)_2 = (F)_{16}$,
$(1100)_2 = (C)_{16}$,
$(1010)_2 = (A)_{16}$,
$(1010)_2 = (A)_{16}$,
$(0101)_2 = (5)_{16}$,
$(0001)_2 = (1)_{16}$.

Therefore we have $(1010110101010110011110111)_2 = (15AACF7)_{16}$.

For an example of the converse operation, suppose we are given $(4D2)_{16}$ and we want to convert to binary:

$(2)_{16} = (0010)_2$.
$(D)_{16} = (1101)_2$.
$(4)_{16} = (0100)_2$.

Therefore we have $(4D2)_{16} = (010011010010)_2 = (10011010010)_2$, where in the last equality we simply removed the initial zero.

Elements of the multiplicative structure of $\mathbb{N}$#

Divisibility, primes, prime decomposition#

The multiplicative structure of natural numbers $\mathbb{N}$ and the integers $\mathbb{Z}$, that is to say the way that numbers are related to each other by the operations of multiplication and division, is of particular importance.

Let us define one of the most basic notions, that of divisibility.

Definition 15

Let $a, b \in \mathbb{N}$. We say that $a$ divides $b$ and write $a \mid b$ if there exists an integer $k$ such that $b = ka$.

If $a \mid b$ we also say that $a$ is a multiple of $b$. If $a$ does not divide $b$, then we write $a \not\mid b$. The above definition has other equivalent statements:

$a \mid b$ if the result of $a / b$ is an integer,
$a \mid b$ if the remainder of the Euclidean division of $b$ by $a$ is zero.

Clearly we always have $1 \mid n$ and $n \mid n$ for any $n \in \mathbb{N}$. A particularly important class of numbers is those for which the above two division relations are the only possible ones:

Definition 16

A number $n \in \mathbb{N} \setminus \{1\}$ is prime if it is only divisibly by 1 and itself.

To determine whether a number $n$ is prime, we can of course try to divide it by all numbers in $[2, n-1]$: if no divisor is found, $n$ is prime.

A simple optimisation of this follows from two simple facts:

Multiplication is commutative: if $m \mid n$ we $n = km = mk$.
If $n = km$ with $m > \sqrt{n}$ then $k < \sqrt{n}$ and vice-versa.

Therefore it suffices to test the divisibility of $n$ by any number in the interval $[2, \left\lfloor \sqrt{n} \right\rfloor]$.

A particularly important result is the following:

Theorem 1 (Fundamental theorem of arithmetic)

Any number $n \in \mathbb{N}$ greater than $1$ can be written in a unique way as a product of primes, up to permutation of the factors:

\[n = \prod_{i=1}^{k} p^{n_i}_i,\]

where the $p_i$ are prime numbers and $n_i \in \mathbb{N} \setminus \{0\}$.

For example:

$99 = 3^3 \times 37$,
$1000 = 2^3 \times 5^3$.

Greatest common divisor and Euclid’s algorithm#

For two natural numbers $n,m \in \mathbb{N}$ their largest number $k$ such that $k \mid n$ and $k \mid m$ is called their greatest common divisor (GCD) and we write $n \wedge m = d$ [1]. Clearly this operation is commutative, so that $n \wedge m = m \wedge n$. We also have that $0 \wedge n = n = n \wedge 0$ for any $n \in \mathbb{N}$. If $n \wedge m = 1$, we say that $n$ and $m$ are relatively prime.

In case $m$ divides $n$, we have:

Lemma 5

Let $n, m \in \mathbb{N}$. If $m \mid n$, then all divisors of $m$ are also divisors of $n$ and:

\[ n \wedge m = m.\]

Another useful lemma is:

Lemma 6

Let $n, m \in \mathbb{N} \setminus \{0\}$. If $d = n \wedge m$, then there exist $a, b \in \mathbb{N}$ which are relatively prime ($a \wedge b = 1$) such that

\[ n = a \times d, m = b \times d.\]

We now turn our attention to the problem of computing the GCD of two given numbers $n, m \in \mathbb{N}$. Here’s one way to calculate do it using :

Calculate the prime factorisations (which necessarily exist due to the Theorem 1):
- $n = \prod\limits_{i=1}^{k} p^{a_i}_i$,
- $m = \prod\limits_{i=1}^{k'} q^{b_i}_i$.
Take the product of factors that appear in both factorisations and raise them to the smallest power in which they appear in either factorisation.

For example, to calculate the GCD of $48$ and $180$:

$48 = 2^4 \times 3$ and $180 = 2^2 \times 3^2 \times 5^1$.
The common prime factors are $2$ and $3$, which appear with powers $4,2$ and $1,2$ respectively.
Therefore the GCD of $48$ and $180$ is: $2^{\min(4,2)} \times 3^{\min(1,2)} = 12$.

Unfortunately, while effective, this approach is not very efficient: we don’t know any polynomial-time algorithms for decomposing positive integers into primes!

A more efficient algorithm for computing the GCD $n \wedge m$ was known to ancient mathematicians! Indeed it is one of the oldest known algorithms still in common use and was described by Greek mathematician Euclid in his treatise Στοιχεῖα (Elements) around 300 BC. It was probably known to people even earlier and was independently rediscovered by Indian and Chinese mathematicians later on.

The basic idea behind Euclid’s algorithm is the following:

Lemma 7

Let $n, m \in \mathbb{N}$ and let $n = qm + r$ be the result of Euclidean division of $n$ by $m$, where $0 \leq r < b$. Then:

$$ n \wedge m = m \wedge r $$.

The trick is then to apply the lemma above iteratively:

Algorithm 1 (Euclid)

Inputs: Two numbers $n, m \in \mathbb{N}$ and we suppose, without loss of generality, that $n \geq m$ (otherwise we can swap them).

Output: The GCD $n \wedge m$.

Algorithm:

If $m = 0$, return $n$ (since $n \wedge 0 = n$).
If not, perform Euclidean division: $n = qm + r$.
Set $n \leftarrow m, m \leftarrow r$.
Repeat the above steps.

To justify the validity of the algorithm notice that:

$r < m$ in each iteration (by definition of the remainder) and therefore since $m \in \mathbb{N}$ the algorithm is sure to reach $m = 0$ and terminate after finitely many steps.
Lemma 7 guarantees a chain of equalities $n \wedge m = m \wedge r$ for each iteration.

As an example, let us compute $21 \wedge 15$ using Algorithm 1:

$n = 21, m = 15$. Performing the Euclidean division of $21$ by $15$ we have $21 = 1 \times 15 + 6$. Therefore, we update: $n \leftarrow 15, m \leftarrow 6$.
$n = 15, m = 6$. Performing the Euclidean division of $15$ by $6$ we have $15 = 2 \times 6 + 3$. Therefore we update: $n \leftarrow 6, m \leftarrow 3$.
$n = 6, m = 3$. Performing the Euclidean division of $15$ by $6$ we have $6 = 2 \times 3 + 0$. Therefore, we update $n \leftarrow 3, m \leftarrow 0$.
Since $m=0$, we output $n = 3$.

As such, we have calculated $21 \wedge 15 = 3$.

Finally, we mention in passing that the least common multiple (LCM) of $n, m \in \mathbb{Z}$, written as $n \vee m$ [2], is the smallest integer $d \in \mathbb{N}$ such that divides both $n, m$: $d \mid n$ and $d \mid m$.

The LCM can be computed using:

\[ n \vee m = \frac{n \cdot m}{n \wedge m}.\]

Bézout’s theorem and resolving Diophantine equations#

A fundamental identity in arithmetic is:

Theorem 2 (Bézout)

Let $n, m \in \mathbb{N}$ with $n \wedge m = d$. There exist two integers $a,b \in \mathbb{Z}$ such that:

\[an + bm = d.\]

Its importance lies in its many applications: it can be used to prove many other important theorems of arithmetic including Euclid’s lemma and the Chinese remainder theorem. It is also, as we’ll see later on, very useful in solving linear equations over the natural numbers $\mathbb{N}$.

Before we move on to applications, let us first consider how compute these two integers $a, b$ (called Bézout coefficients). The trick lies in Euclid’s algorithm: it provides a sequence of equations (corresponding to the successive Euclidean divisions we perform) which link the numbers $n, m, d$.

Before we state the algorithm itself, let us first go through an example. Recalling our previous example of using Euclid’s algorithm to compute $25 \wedge 15$ we have the following equations:

At the first step, we had the Euclidean division of $n = 21$ by $m = 15$:

(40)#\[21 = 1 \times 15 + 6.\]

At the second step, we had the Euclidean division of $15$ by the remainder $6$:

(41)#\[15 = 2 \times 6 + 3.\]

Finally, we had that:

(42)#\[6 = 2 \times 3 + 0.\]

From the above, we deduced that $d = 21 \wedge 15 = 3$. Notice how the penultimate equation (41) can easily be rewritten as an equation for $d = 3$:

(43)#\[3 = 15 - 2 \times 6.\]

We’ve already obtained an equation involving $d=3$ and $m=15$! Furthermore, equation (40) in the above sequence links $6$ with $n=21$:

(44)#\[6 = 21 - 1 \times 15.\]

Combining the equations (43) and (44) above, we have:

\[\begin{align*} 3 &= 15 - 2 \times 6 \\ &= 15 - 2 \times (21 - 1 \times 15) \\ &= -2 \times 21 + 3 \times 15, \end{align*}\]

from which it follows that the coefficients we seek are $a = -2, b = 3$.

This is the essense of the extended Euclid’s algorithm: run back up the sequence of equations produced during the succesive divisions of an execution of Euclid’s algorithm.

More formally, the algorithm we described is equivalently written as:

Algorithm 2 (Extended Euclid’s)

Inputs: Two numbers $n, m \in \mathbb{N}$ and we suppose, without loss of generality, that $n \geq m$ (otherwise we can swap them).

Output: The GCD $d = n \wedge m$ and the Bézout coefficients $a, b \in \mathbb{Z}$, so that $d = an + bm$.

Algorithm:

Set: \begin{align*} a_0 &\leftarrow 1 \ b_0 &\leftarrow 0 \ r_0 &\leftarrow n \ a_1 &\leftarrow 1 \ b_1 &\leftarrow 1 \ r_1 &\leftarrow m \ i &\leftarrow 1. \end{align*}
While $r_i \neq 0$ do:
1. Perform the Euclidean division of $r_{i-1}$ by $r_i$ to obtain a quotient $q$ and a rest $r_{i+1}$.
2. $a_{i+1} \leftarrow a_{i-1} - q \times a_{i}$.
3. $b_{i+1} \leftarrow b_{i-1} - q \times b_{i}$.
4. $i \leftarrow i + 1$.
Return the GCD $d = r_i$ as well as the corresponding coefficients $a = a_i, b = b_i$.

Finally, the following theorem is an important application of Bézout’s identity to equations over $\mathbb{Z}$ (called Diophantine equations after the Greek mathematician Diophantus).

Theorem 3 (Solution of linear Diophantine equations)

A linear Diophantine equation with coefficients $a, b, c \in \mathbb{Z}$ and two unknowns $x,y$:

\[ ax + by = c \]

has integer solutions if and only if $c$ is a multiple of $a \wedge b$. Furthermore, if $(x_0, y_0)$ is a particular solution, then all other solutions to this equation have the form:

\[(x+kv, y-ku),\]

where $k \in \mathbb{Z}$ is an arbitrary integer and:

$u$ is the quotient of the Euclidean division of $a$ by $a \wedge b$,
$v$ is the quotient of the Euclidean division of $b$ by $a \wedge b$.

As an example, let us consider $a = 98, b = 35, c = 14$:

(45)#\[98x + 35y = 14.\]

Since $d = 98 \wedge 35 = 7$ divides $c=4$ we are sure that the equation can be solved. Dividing both sides of (54) by $d=7$ we have:

(46)#\[14x + 5y = 2.\]

We can divide once more by $2$ to obtain an equivalent equation:

(47)#\[\frac{14x}{2} + \frac{5y}{2} = 1.\]

Defining $x' = x/2$ and $y' = y/2$ we finally obtain:

(48)#\[14x' + 5y' = 1.\]

Now, we note that $14$ and $5$ are relatively prime as they came from dividing $a = 98, b = 35$ by their GCD $d = 7$. Therefore the coefficients $x', y'$ in (57) are Bézout’s coefficients and we can calculate them using Algorithm 2:

\[\begin{align*} x' &= -1 \\ y' &= 3. \end{align*}\]

Finally, using $x = 2 \times x', y' = 2 \times y'$ we recover a particular solution to (55): $x_0 = -2, y_0 = 6$. Therefore, using Theorem 3 we have that a general solution is:

\[\begin{align*} x &= -2 + 5k \\ y &= 6 - 14k. \end{align*}\]

Modular arithmetic#

When talking about time, in the usual 24-hour format, we find that arithmetic works in a different way than in $\mathbb{N}$:

Three hours after midnight is $3h$, i.e. $24h + 3 = 3$ (or, alternatively, $0h + 3h = 3h$).
Twelve hours after $13h$ is $1h$, i.e. $13h + 12h = 1h$.
Fourty-eight hours after $17h$ is $17h$, i.e. $17h + 2 \times 24h = 17h$.

which is unlike the usual results in $\mathbb{N}$:

$24 + 3 = 27$,
$13 + 12 = 25$.

Indeed, it seems that 24-hour clock arithmetic is as if we took the infinite number line of $\mathbb{N}$ and wrapped it around itself, so that:

Multiples of $24$ behave as $0$: $2 \times 24h \cong 0$.
Numbers that differ by a multiple of $24$ behave the same: $x + k \times 24h \cong x$.

With this in mind, let us define the notion of congruence modulo $n$:

Definition 17 (Congruence modulo $n$)

We say that two numbers $a, b \in \mathbb{N}$ are congruent (or equal) modulo $n$ if their difference is a multiple of $n$: $n \mid (a-b)$. In this case, we note $a \equiv b [n]$ and note that it is an equivalence relation:

Reflexivity: for all $a \in \mathbb{N}$, $a \equiv a[n]$.
Symmetry: for all $a,b \in \mathbb{N}$, if $a \equiv b[n]$ then $b \equiv a[n]$.
Transitivity: for all $a,b,c \in \mathbb{N}$, if $a \equiv b[n]$ and $b \equiv c[n]$ then $a \equiv c[n]$.

Such equivalence relations partition the set $\mathbb{N}$ into equivalence classes, infinite sets of numbers that are equal modulo $n$. For example, for $n=2$ we have two such classes:

$0 \equiv 2 \equiv 4 \equiv 6 \equiv 8 \equiv \dots [n]$,
$1 \equiv 3 \equiv 5 \equiv 7 \equiv 9 \equiv \dots [n]$.

We can therefore define the equivalence class of some number $k \in \mathbb{N}$, denoted as $\overline{k}$, as:

\[ \overline{k} = \{ p \lvert p \in \mathbb{N} \land p \equiv k[n]\}.\]

More generally, there’s always exactly $n$ equivalence classes of $\mathbb{N}$ modulo $n$. The elements of the set $\overline{k}$ are called representatives of the class.

A natural question is then: how do the familiar operations of arithmetic on $\mathbb{N}$ behave modulo $n$? A particular important pair of properties is:

$\overline{a} + \overline{b} = \overline{a+b}$,
$\overline{a} \times \overline{b} = \overline{a \times b}$.

Using these properties we can make sense of our 24h-clock manipulations as a case of arithmetic modulo $24$:

Three hours after midnight is $3h$: $24 + 3 = 27 \equiv 3[24]$.
Twelve hours after $13h$ is $1h$: $13 + 12 = 25 \equiv 1[24]$.
Fourty-eight hours after $17h$ is $17h$: $17+48=65 \equiv 17[24]$.

The two properties we’ve listed above lead us to expect that arithmetic using equivalence classes modulo $n$ migh be analogous to that in $\mathbb{N}$. With this in mind, let us define the following set grouping all equivalence classes modulo $n$, which we label by their smallest representative:

$\mathbb{Z} / n \mathbb{Z} = \{\overline{0}, \overline{1}, \dots, \overline{n-1}\}$

We can then consider the above two lines as defining the operations $+, \times$ in $\mathbb{Z}/n\mathbb{Z}$. The set $\mathbb{Z}/n\mathbb{Z}$ equipped with these two operations behaves similary to $\mathbb{Z}$ equipped with the usual $+,\times$ operations (more abstractly, mathematicians say that both are instances of a general algebraic structure called a ring).

As a first application, we have the following lemma relating solutions of Diophantine equations to solutions of the equation modulo $n$:

Lemma 8

Consider a Diophantine equation of the form:

\[P(x,y,\dots) = c,\]

where $P$ is some polynomial with integer coefficients and $c \in \mathbb{Z}$. If $x = x_0, y = y_0, \dots$ is a solution over $\mathbb{Z}$ then we have that:

\[F(\overline{x_0}, \overline{y_0}, \dots) = \overline{c},\]

holds in $\mathbb{Z}/n\mathbb{Z}$ for all $n \in \mathbb{N}$.

The converse of this lemma is that if there exists some $n \in \mathbb{N}$ such that the equation has no solution in $\mathbb{Z}/n\mathbb{Z}$, then it has no solution in $\mathb{Z}$ either. This can be used to disprove the existence of solutions to Diophantine equations by wisely choosing $n$: since $\mathbb{Z}/n\mathbb{Z}$ is a finite set we can just try out all possibilities to see if there’s any solution.

For example, let us consider the equation $x^2 + y^2 = 35$. Since it is non-linear, we cannot use the criterion of Theorem 3. However, reducing it modulo $3$ we get:

\[\begin{align*} \overline{x^2+y^2} &= \overline{35} \\ \overline{x}^2 + \overline{y}^2 &= \overline{3} \end{align*}\]

Looking at the squares in $\mathbb{Z}/4\mathbb{Z}$ we see that:

$\overline{0}^2 = 0$,
$\overline{1}^2 = 1$,
$\overline{2}^2 = 0$,
$\overline{3}^2 = 1$,

from which we conclude that no solution exists to the equation modulo $4$: there’s no way to add any two of the above values so as to get 3! Therefore Lemma 8 implies that there’s no integer solutions to the equation $x^2 + y^2 = 35$!

Let us now explore another algebraic property of $\mathbb{Z}$ and its analogue in $\mathbb{Z}/n\mathbb{Z}$. In $\mathbb{Z}$ all elements except for $0$ are invertible: for each $i \in \mathbb{Z} \setminus \{0\}$ there exists a unique number $j \in \mathbb{Z}$ such that $i \times j = 1$. We usually denote $j$ by $i^{-1]$ and call it the inverse of $i$.

What about $\mathbb{Z}/n\mathbb{Z}$? Does it have any invertibe elements? We can try to work out some example for small values of $n$:

In $\mathbb{Z}/2\mathbb{Z}$ we have $\overline{1} \times \overline{1} = \overline{1}, so $1$ is its own inverse.
In $\mathbb{Z}/7\mathbb{Z}$ we have $\overline{3} \times \overline{5} = \overline{1}$, so $\overline{3}^{-1} = \overline{5}$.

If we keep working out such examples by hand, we quickly arrive at the following important result:

Lemma 9

Let $n \in \mathbb{N}$, $x \in \mathbb{Z}$. Then $\overline{x}$ is invertible in $\mathbb{Z}/n\mathbb{Z}$ if and only if $x \wedge n = 1$.

The proof is quite straightforward:

\[\begin{align*} \overline{x} \text{ invertible } &\Leftrightarrow \exists y \in \mathbb{Z}, \overline{xy} = \overline{1} \\ &\Leftrightarrow xy \equiv 1 [n] \\ &\Leftrightarrow \exists k \in \mathbb{Z}, xy = 1 + nk\\ &\Leftrightarrow xy-nk=1 \\ &\overset{Bézout}{\Leftrightarrow} x \wedge n = 1. \end{align*}\]

The proof above also gives us a way to calculate inverses. Recall from above that $x$ being invertible implies there exist $y, k \in\mathbb{Z}$ such that:

\[xy - nk = 1.\]

Therefore, modulo $n$, we have $\overline{xy} = \overline{1} \Rightarrow \overline{x}\overline{y}=\overline{1}$. That is to say, the inverse $\overline{y} = \overline{x}^{-1}$ is exactly the first Bézout coefficient of the above equation. Therefore we can find $\overline{y}$ using the extended Euclidean algorithm!

For example, suppose we search for the inverse of $\overline{x}=\overline{5}$ in $\mathbb{Z}/17\mathbb{Z}$. Applying the Euclidean algorithm, we have:

\[\begin{align*} 17 &= 3 \times 5 + 2 \\ 5 &= 2 \times 2 + 1 \\ 2 &= 2 \times 1 + 0. \end{align*}\]

Reasoning backwards (starting from the penultimate equation), we obtain:

\[\begin{align*} 1 &= 5 - 2 \times 2 \\ &= 5 - 2 \times (17 - 3 \times 5) &= 7 \times 5 - 2 \times 17. \end{align*}\]

Therefore, $\overline{y} = \overline{7}$ and so $\overline{5}^{-1} = \overline{7}$. Indeed, $5 \times 7 = 35 \equiv 1[17]$.

Kid-RSA#

In this section we’ll apply our knowledge of numeral bases and arithmetic modulo $n$ to study a simple cryptosystem called KidRSA.

Kid-RSA is a simple example of public-key cryptography which operates on the basis of two keys:

A public key: everyone who has access to this can encrypt messages.
A private key: only those who have access to this can decrypt messages.

Suppose for simplicity that a message is a plaintext written using the 26 letters of the latin alphabet (no spaces allowed!)[3].

Using the correspondence $A \leftrightarrow 0, B \leftrightarrow 1, \dots, Z \leftrightarrow 25$, we can translate any message into a number in base 26. Finally, using a base conversion algorithm we can rewrite the message in base-10 to facilitate calculations.

Our public and private keys will be a pair of integers $(e,d)$. Encryption and decryption will be carried out by multiplying by $e$ and $d$ respectively, modulo some number $n$ to be defined below.

To set up the system someone, let’s call them Alice, must choose any two integers $a,b \in \mathbb{Z}$ and calculate $M = ab - 1$. Alice then must choose two more integers $a', b' \in \mathbb{Z}$ and use them to calculate the three desired values $(e,d)$ and $n$:

\[\begin{align*} e &= a'M + a, \\ d &= b'M + b, \\ n &= \frac{ed-1}{M} = a'b'M + ab' + a'b + 1. \end{align*}\]

Finally, Alice can publicly announce the key $e$.

If someone, say Bob, wants to send Alice an encrypted message they do as follows:

Convert their message to an integer in base-25 and apply a base conversion algorithm to rewrite it in base-10. That is to say, we assume that the message is some integer $m \in \mathbb{Z}$ (written in base-10).
Calculate the cyphertext $c$ as $c \equiv em[n]$.
Communicate $c$ to Alice.

Once Alice receives the cyphertext $c$ from Bob, all they have to do to decrypt is multiply by $d$ modulo $n$: $m \equiv dc[n] \equiv dem[n]$.

For this to work we must have $dc \equiv dem \equiv 1 \times m \equiv m[n]$ which means that $e$ and $d$ are inverses of eachother in $\mathbb{Z}/n\mathbb{Z}$. To prove this, we calculate:

\[\begin{align*} ed - 1 &= (a'M + a)(b'M + b) - 1 \\ &= a'b'M^2 + a'Mb + ab'M + ab - 1 \\ &= (a'b'M + a'b + a'b)M + M \\ &= (a'b'M + a'b + a'b + 1)M \\ &= nM, \end{align*}\]

where we used the definitions of $M = ab-1$ and $n = a'b'M + ab' + a'b + 1$. From this we have that $(ed - 1)$ is divisible by both $n$ and $M$ and therefore $(ed - 1) \equiv 0[n] \Rightarrow ed \equiv 1[n]$, as desired.

Let us now work through an example:

To begin with, we choose $a = 120, b = 39$, $a' = 5, b' = 215$. This gives us: \begin{align*} M &= 4679, \ n &= 5055921, \ e &= 23515, \ d &= 1006024. \end{align*}
For our message, let us choose “HELLO”. Rewritting this in base-10 we have $(HELLO)_{26} = (3276872)_{10}$.
We compute the cyphertext using the public key $e$: \begin{align*} c &\equiv em[n] \ &\equiv 3409040 [n]. \end{align*}
We decrypt using the private key $d$: \begin{align*} m &\equiv dc[n] \ &\equiv 1006024 \times 3276872 [n] \ &\equiv 3276872[n]. \end{align*}
We rewritte this in base-26: $(3276872)_{10} = (HELLO)_{26}$.

This cryptosystem is not particularly safe: can you think of any potential vulnerabilities? If you have read and understood everything presented in the previous sections, then you have the tools to break this simple system! See also the relevant exercise below.

Bonus if we have time: Euler’s phi and inverses?#

Exercises#

Note: the programming exercises can be carried out in any programming language of your choice.

Exercise#

Implement a base conversion algorithm.

Exercise#

For the lovers of music theory, consider a piece consisting of two voices each playing a single measure in polymetre. That is to say,

Each voice follows its own metre (for example one in $3/4$ and one in $4/4$).
Each voice plays a single measure.
The tactus (pulse) is fixed and common for both voices.

Even though the two voices start at the same time they quickly become desynchronised: each starts and ends its measure at different beats. Eventually however, after $t$ beats, the two voices will start their measures again at the same time.

Given the meters of the two voices, calculate the number of beats $t$. How many measures will each of the voices have performed before they start again at the same beat?

Exercise#

Implement a prime factorisation algorithm (the naive one, for example).

Exercise#

Implement Euclid’s algorithm. Consider various approaches: a recursive one and an iterative one for example.

Exercise#

Implement the extended Euclid’s algorithm.

Exercise#

Determine if the following Diophantine equations have solutions and if so, compute them:

$5x + 10y = 10$,
$5x + 10y = 11$,
$12x + 4y = 30$,
$12x + 4y = 32$.

Exercise#

Prove properties of $+, \times$ modulo $n$.

Exercise#

Show that the equations $x^2+y^2 = 2024$ and $x^2+y^2+z^2=87$ do not admit integer solutions.

Exercise#

List all invertible elements in $\mathbb{Z}/2\mathbb{Z}, \mathbb{Z}/5\mathbb{Z}, \mathbb{Z}/7\mathbb{Z}, \mathbb{Z}/24\mathbb{Z}$.

Exercise#

Recall the example execution of the KidRSA algorithm we carried out above, with parameters: $a = 120, b = 39$, $a' = 5, b' = 215$. Using these:

Calculate the cyphertexts corresponding to: “HEY”, “MSG”, “CODE”.
Decrypt the following cyphertext: 4319056.

Exercise#

Implement the KidRSA cryptosystem.

Exercise#

Can you think of a way to break the KidRSA cryptosystem? Given knowledge only of $e,n$, come up with a way to compute $d$.

Arithmetic and applications

Contents

Arithmetic and applications#

Numerical systems#

Numerals and positional notation#

Base conversion#

Elements of the multiplicative structure of \(\mathbb{N}\)#

Divisibility, primes, prime decomposition#

Greatest common divisor and Euclid’s algorithm#

Bézout’s theorem and resolving Diophantine equations#

Modular arithmetic#

Kid-RSA#

Bonus if we have time: Euler’s phi and inverses?#

Exercises#

Exercise#

Exercise#

Exercise#

Exercise#

Exercise#

Exercise#

Exercise#

Exercise#

Exercise#

Exercise#

Exercise#

Exercise#

\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)
	I	II	III	IV	V	VI	VII	VIII	IX	X
੦	੧	੨	੩	੪	੫	੬	੭	੮	੯	੧੦
	Α	Β	Γ	Δ	Ε	Ϝ	Ζ	Η	Θ	Ι