02.2 Rudiments of Number Theory

Public-key cryptography relies a lot on number theory

In the set of integers $\mathbb{Z}$ we can

• Add, Subtract, Multiply
• not do division

Euclidean Division

To divide integers, we are left with a remainder $r$ and the quotient $q$

The result of the division $a/m$ is given by

$$a=mq+r,0\le r\le |m|$$

However, programming languages don’t always have a positive remainder :

Division	Java/C/C++	Python	$r$
$8/3$	$r=2$	$r=2$	$2$
$8/-3$	$r=2$	$r=1$	$1$
$-8/3$	$r=-2$	$r=-1$	$2$
$-8/-3$	$r=-2$	$r=-2$	$1$
In this class, we will always have $r$ as a positive integer

We have the notation

$$r=a\mathrm{mod}m$$

Quote

You have to be able to do modulo in your sleep to understand the modulo world.

• Gastpar

Congruence

Two numbers that have the same remainder are said to be congruent

Definition

Two integers $a,b$ are said to be congruent to $\mathrm{mod}m$

$$a\equiv b(\mathrm{mod}m)$$

Congruence is an equivalence relation (reflexive, symmetric and transitive)

If we have $a\equiv a^{\prime }\mathrm{mod}m$ and $b\equiv b^{\prime }\mathrm{mod}m$ then we have

$$\begin{array}{rclr}a+b& \equiv & a^{\prime }+b^{\prime }& \mathrm{mod}m\\ ab& \equiv & a^{\prime }{b}^{\prime }& \mathrm{mod}m\\ a^n& \equiv & (a^{\prime }{)}^n& \mathrm{mod}m\end{array}$$

Check Digits mod $97$

It is a way to check if an error has occurred when typing a number (swapping digits around)

Let’s say we have a phone number we want to dial. $0212351234$

We compute its remainder after division by $97$ (a prime number) $=95$

We call those the check digits

If we dial the wrong number, the error can be seen easily: $0212531234\mathrm{mod}97=63$, which is not equal to the check digits.

Variant mod $97-10$

Algorithm

We have our number $n$, mod $97-10$ works as such:

1. We multiply by $100$
2. We denote $r$ as the remainder
3. The check digits $c$ are given by $98-r$
4. Replace the ending $00$ with $c$
5. Check that the resulting number $\mathrm{mod}97==1$

Here’s why it works :

$$\begin{array}{rl}100n+(98-r)=& 100n+(98-(100n\mathrm{mod}97))\\ =& 100n+98-(100n\mathrm{mod}97)\\ =& 100n+98-100n\mathrm{mod}97\\ =& 98\mathrm{mod}97\\ =& 1\end{array}$$

This algorithm is used to describe IBAN numbers per example.

$$\text{CH}cc12345123456789876$$

with $cc$ the check digits

Prime numbers

Definition

A prime number is an integer $>1$ that has no other divisor other than $1$ and itself

Theorem

Every composite (=non-prime) number has a unique prime factorization

Theorem

For two numbers $a,b$, $a$ divides $b⟺$ all prime factors of $a$ are present in the prime factorization of $b$

We get the integers $a$ and $b$. The largest integer that divides both is called the greatest common divisor of $a$ and $b$, which we denote $\gcd (a,b)$

Theorem

For two integers $a$ and $b$, and their prime sequence given by

$$\begin{array}{l}a={\prod }_{i=1}^k{p}_i^{{\alpha }_i}\\ b={\prod }_{i=1}^k{p}_i^{{\beta }_i}\end{array}$$

And the $\gcd$ is given by

$$\gcd (a,b)=\prod _{i=1}^k{p}_i^{{\gamma }_i}$$

with ${\gamma }_i=\min ({\alpha }_i,{\beta }_i)$

Relatively prime

If both numbers don’t have a common factor, then it means that their $\gcd =1$

Definition

We say that $a,b$ are coprime when $gcd(a,b)=1$

Theorem

If $a$ divides $c$, and $b$ divides $c$ and $\gcd (a,b)=1$, then we have that $ab$ divides $c$

02.3 Modular Arithmetic