Modular Arithmetic

We have some articles in this blog about integers of typical programming languages and how they work. Time to introduce the underlying mathematical concepts, that have been covered implicitly until now, since they are also interesting in many other aspects. And besides, this is a very beautiful area of mathematics.

Mathematics that we learn in school is mostly inspired by what is needed for physics. This was quite a good choice 100 years ago, because it gave some motivation to why we do certain things and it was the area, where math was applied. Of course also chemistry and engineering, but these are somewhat similar aspects of mathematics as we use in physics. Now physics and chemistry make use of quite interesting areas of mathematics like group theory or non Euclidean geometry, but these are kind of advanced areas beyond what we typically learn in school. at least in the countries where I went to school. So it is about real numbers, some trigonometry, real analysis (calculus) and maybe complex numbers.

Since more than 50 years mathematics is heavily used in informatics as well, if we abstract informatics away from computers, even longer, because for example algorithms and cryptography have been used for several thousand years already, but that was a small niche and became main stream by the existence of computers. And for informatics and computer science we need different areas of mathematics. Analysis is not the so important, though not irrelevant. One area is information theory, which is based on probability theory and statistics. Numerical calculations have to a great extent remained a domain of mathematics itself, so this connection may be strong, but it is applied mathematicians using computers and using knowledge from IT to program them better, not the other way round. Still numerical analysis is somewhat important, but not really what most of us need very often.

The areas of mathematics that are really interesting for informatics are discrete mathematics, algebra and number theory. There is enough material about this on the web, but for now we will deal with modular arithmetic, which is kind of in the intersection of discrete mathematics, algebra and number theory.

We start with the integral numbers:

${\Bbb Z} = \{\ldots,-3, -2, -1, 0, 1, 2, 3, 4,\ldots\}$

Now we take any positive integral number $m \in {\Bbb N}$ with $m \ge 2$ .
We say that two integral numbers $x$ and $y$ are congruent modulo $m$ :

$x \equiv y \pmod m$

if and only if $x-y$ can be divided by $m$ . We might also say that there is a $k \in {\Bbb Z}$ such that $y = x + k m$ .
Now we can make interesting observations:
We assume, that we have pairs of numbers such that

$u \equiv v \pmod m$

and

$x \equiv y \pmod m$

Then we can observe that also

$u+x \equiv v+y \pmod m$

$u-x \equiv v-y \pmod m$

$u\cdot x \equiv v\cdot y \pmod m$

This can be proven easily.
We assume as above

$y = x + k \cdot m$

and similarly

$v = u + l \cdot m$

Then we have

$y+v = x+u+(k+l)m \equiv x+u \pmod m$

$y-v = x-u+(k-l)m \equiv x-u \pmod m$

$yv = xu+kum + lvm + klm^2 \equiv x-u \pmod m$

We call a set of all numbers of $\Bbb Z$ that are congruent to each other a remainder class and write this as

$\bar x = x + m{\Bbb Z}$

There are exactly $m$ remainder classes modulo $m$ and usually we use a representation system of

$0,1,\ldots m-1$

or for even $m$ we often use

$-\frac{m}{2}, -\frac{m}{2}+1,\ldots,-1,0,1,\dots,\frac{m}{2}-1$

or for odd $m$ we often use

$-\frac{m-1}{2}, -\frac{m-1}{2}+1,\ldots,-1,0,1,\dots,\frac{m-1}{2}$

We observe these representation systems when we do division with remainder, written as % in many programming languages, but it is necessary to do some quick research on which representation system % uses and which one we want to use and possibly adjust the result. The corresponding division may not be /, but we can obtain it by subtracting our remainder from the dividend and dividing that, which should be an exact division.

Now we need to define a ring. A ring $R$ is a set with operations $+$ and $\cdot$ such that the following rules apply:

For any members $x, y \in R$ we also have $x+y \in R$ , $x-y \in R$ and $x\cdot y \in R$ . This is usually not mentioned, because it is part of how we define these operations in the first place in most mathematical texts.
Addition is communicative: For any members $x, y \in R$ we have $x+y=y+x$ .
Addition has a neutral element 0: For any member $x \in R$ we have $x+0=0+x=x$ .
Addition has inverse elements: For any member $x \in R$ we have a member $x'\in R$ such that $x+x'=x'+x=0$ . Usually we write $-x$ for this inverse element of $x$ and we write $x-y$ instead of $x+(-y)$ .
Addition is associative: For any members $x, y, z \in R$ we have $(x+y)+z=x+(y+z)$ . We can omit the parentheses here and write $x+y+z$ instead.
Multiplication has a neutral element 1: For any member $x \in R$ we have $x\cdot 1=1\cdot x=x$ .
Multiplication is associative: For any members $x, y, z \in R$ we have $(x\cdot y)\cdot z=x\cdot (y\cdot z)$ . We can omit the parentheses here and write $x\cdot y\cdot z$ or even $xyz$ instead.
Multiplication in conjunction with addition is distributive: For any members $x, y, z \in R$ we have $(x + y)\cdot z = x\cdot z + y\cdot z$ and $z\cdot (x+y)=z\cdot x + z\cdot y$ .

If the multiplication is also communicative, we call it a commutative ring. If there is a multiplicative inverse for any element other than 0, we call it a skew field. And if both conditions hold, we call it a field.

Now we can see that $\Bbb Z$ is actually a communicative ring.

And these remainder classes modulo $m$ also form a ring. We call it ${\Bbb Z}/m{\Bbb Z}$ or sometimes also ${\Bbb Z}_m$ , but I do not use the second form, because it is ambiguous with something else (p-adic numbers). If $m=p$ is a prime number, then ${\Bbb Z}/p{\Bbb Z}$ is actually a field and in this case we may write ${\Bbb F}_p$ instead of ${\Bbb Z}/p{\Bbb Z}$ . Or $GF(p)$ in some literature, if you prefer that. Why is it a field?

Now we have an extension of the Euclid algorithm to calculate the gcd of two numbers. This also yields numbers $u$ and $v$ such that $g=\gcd(x,y)=ux+vy$ . So these numbers exist. For a prime number $p$ and a remainder class $\bar x \ne 0$ we know that $x$ is not a multiple of $p$ and since $p$ is prime we know that

$1=\gcd(x,p)=ux+vp$

. This yields a multiplicative inverse for $\bar x$ because

$u\cdot x \equiv 1 \pmod p$

Now we often see $m$ as a power of $2$ and the modular arithmetic, at least +, -, *, is what is sold to us as integer arithmetic of Java, C or C#.

On the other hand it can be interesting and useful to use modular arithmetic for other values of $m$ . Interesting are mostly prime numbers, which can be relatively small like $2$ , $3$ or $5$ , but also really big. For non-primes we have null-factors, that is numbers $x, y \not\equiv 0 \pmod m$ such that $x\cdot y \equiv 0 \pmod m$ . This breaks some fundamental mathematical assumption for integers and fields, but is perfectly correct for this modular ring.

In our daily life modular arithmetic is actually quite common. We have the week days with $m=7$ , the hours of the clock with $m=12$ or $m=24$ , the minutes and seconds of the clock with $m=60$ and quite a bit of $m=2$ , which we do not really see as modular arithmetic, but maybe as boolean arithmetic with $+$ being the „exclusive or“, $\cdot$ being the „and“ etc.

Schreibe einen Kommentar

Antworten abbrechen