$\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)$.
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
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)$.
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
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: