Modular arithmetics

$\renewcommand{\mod}{\operatorname{mod}}$

Sometimes when you want to calculate something you might only require the remainder of the answer when divided by some natural number $n$. With help of modular arithmetics finding the required remainder usually happens to be much easier than evaluating the original expression.

Before we start off with examples, let us introduce a handy notation.

For integers $a, b$ and a natural number $n$ let $a \equiv b \ (\mod n)$ denote that $a$ and $b$ have the same remainder when divided by $n$, i.e., that $a \mod n = b \mod n$ holds.

In essence, modular arithmetics means counting in a circle. There are many real-world examples: clock: 19:00 + 7 hours = 02:00,

weekdays: friday (5th day) + 4 days = tuesday (2nd day),

counting-out games, etc.

Let us consider a bit more technical example: Let's say someone asks you to check whether $5638 \times 7891 + 2731 \times 3124$ is divisible by $17$.

One way to do this is to go ahead and calculate the expression:

$5638 \times 7891 + 2731 \times 3124 = 44489458 + 8531644 = 53021102$,

then check if $17$ divides the answer… yawn. Ok, done.

On the other hand, a modular arithmetic approach would be to note that $\mod 17$ we have:

$10 = 17 - 7 \equiv -7$,

$100 = 10^2 \equiv (-7)^2 = 49 = 51 - 2 \equiv -2$,

$5638 = (51+5) \cdot 100 + (34 + 4) \equiv 5 \cdot (-2) + 4 = -6$,

$7891 = (85-7)\cdot 100 + (85+6) \equiv (-7)\cdot(-2) + 6 = 20 \equiv 3$,

$2731 \equiv (-7)\cdot(-2) - 3 = 11 \equiv -6$,

$3124 \equiv (-3)\cdot(-2) + 7 = 13 \equiv -4$,

and

$5638 \times 7891 + 2731 \times 3124 \equiv (-6) \cdot 3 + (-6) \cdot (-4) = (-6) \cdot (-1) = 6$.

So the answer is: no, it is not, as the remainder is $6$, not $0$.

Note that in the above example in the arithmetic expressions following the equivalenvce $\equiv$, we allowed ourselves to replace any number with a number having the same remainder modulo $17$. This is because the “equivalence modulo $n$” behaves very nicely with respect to arithmetic operations. (Why not try to prove the following bit of theory yourself?)

If $a \equiv b \ (\mod n)$ and $c \equiv d \ (\mod n)$ then

(1) $a+c \equiv b+d \ (\mod n)$

and (2) $ac \equiv bd \ (\mod n)$.

Proof

When we say that an arithmetic expression has to be computed modulo $n$, we mean that we are interested in the remainder of the value of this expression when divided by $n$. For example, $(2 + 5) \cdot (8 + 6)$ is equal to $10$ modulo $11$, or $(2 + 5) \cdot (8 + 6) \equiv 10 \ (\mod 11)$.

The proposition above allows us to perform computations modulo $n$, such that the intermediate values do not become much larger than $n$.

Actually, when the operations that we’re applying are only addition, subtraction and multiplication, then no intermediate value has to be larger than $n^2$ . Namely, we can compute the remainder (by $n$) after each step of the computation. Thus, we could perform the previous computation by

  • $2+5=7$
  • $8 + 6 = 14 \equiv 3 \ (\mod 11)$
  • $7 \cdot 3 = 21 \equiv 10 \ (\mod 11)$.

In fact, we can do even more simple operations with this equivalence.

Let us look more closely at the proposition. Note that part (1) is reversible in the sense that if $a+c \equiv b+d \ (\mod n)$ and $c \equiv d \ (\mod n)$ then $a \equiv b \ (\mod n)$. Because

You may use this observation to check the exercise:

Show that $a \equiv b \ (\mod n)$ if and only if $n \mid (a-b)$.

Solution

Part (2), on the other hand, is not reversible in general: $4 \cdot 2 \equiv 2 \cdot 2 (\mod 4)$ but $4 \not \equiv 2 (\mod 4)$.

The following exercise explains what we should do when trying to do the reverse of part (2).

Let $k \in \mathbb N$. Show that

  • $a \equiv b \ (\mod n)$ if and only if $ak \equiv bk \ (\mod nk)$.
  • If $ka \equiv kb \ (\mod n)$, then $a \equiv b \ (\mod \frac{n}{\gcd(k,n)} )$.

Solution

In particular, if $k$ and $n$ are coprime, then we essentially get the inverse of part (2): $ka \equiv kb \ (\mod n)$ implies $a \equiv b \ (\mod n)$.

In a short while, we will see a deeper algebraic meaning of this cancelability.

TODO: Examples on the last exercise.

Perform the following computations:

  • $(5 \cdot 8 − 3 \cdot 6) \cdot (8 + 4) \ (\mod 9)$,
  • $7 \cdot 7 \cdots 7 \ (\mod 11)$ (here $7$ is taken 15 times),
  • $1 \cdot 2 \cdots 10 \ (\mod 25)$.

Residue classes

modular/modular_arithmetics_draft.txt · Last modified: 2015/03/19 19:57 by aleksei