Modular arithmetic
In modular arithmetic, integers wrap around a modulus, which is
some integer \(m > 1.\)
Applying the function \(\text{mod } m\) to an integer \(x\) returns \(x \bmod
m.\) In other words, it returns the remainder from dividing \(x\) by \(m\), which will always be an
integer in \(\set{0, ... m-1}.\) This set, denoted \(\mathbb{Z}_m\), is a
ring of \(m\) elements.
If we apply \(\text{mod } m\) directly after performing an arithmetic operation, we can define new kinds
of operations whose results are guaranteed to be in \(\mathbb{Z}_m.\)
⚠ Modular arithmetic is used in hash functions and pseudorandom number generators since it causes
numbers to stay within a ring.
Congruence \(\text{mod } m\)
This is an equivalence relation defined on a particular ring
\(\mathbb{Z}_m.\)
For an integer \(m > 1\), integers \(x\) and \(y\) are "congruent \(\text{mod } m\)" if and only if \(x
\bmod m = y \bmod m\), or \(m \mid (x - y).\) This relation is written as:
$$x \equiv y \pmod{m}$$
⚠ You can also use the following shorthand notation, \(x \equiv_{m} y\), within the context of modular
arithmetic. (Personally, I find this format more readable.)
Integers that are congruent \(\text{mod } m\) will always have a difference that is some multiple of
\(m.\)
Addition \(\text{mod } m\)
This operation is defined as addition with \(\text{mod } m\) applied to the result.
For \(\mathbb{Z}_3\), \(3 + 5\) is congruent to \(2\) because \(8 \bmod 3 = 2.\)
The sum of two integers \(x\) and \(y\) is congruent \(\text{mod } m\) to the sum with \(\text{mod } m\)
applied individually:
$$x + y \equiv_{m} x \bmod m + y \bmod m$$
This can be rewritten as:
$$(x + y) \bmod m = (x \bmod m + y \bmod m) \bmod m$$
Multiplication \(\text{mod } m\)
This operation is defined as multiplication with \(\text{mod } m\) applied to the result.
For \(\mathbb{Z}_4\), \(2 \times 6\) is congruent to \(0\) because \(12 \bmod 4 = 0.\)
The product of two integers \(x\) and \(y\) is congruent \(\text{mod } m\) to the product with
\(\text{mod } m\) applied individually:
$$x \times y \equiv_{m} x \bmod m \times y \bmod m$$
This can be rewritten as:
$$(x \times y) \bmod m = (x \bmod m \times y \bmod m) \bmod m$$
Multiplicative inverse \(\text{mod } m\)
When an integer is multiplied by its multiplicative inverse \(\text{mod } m\), the result is congruent
\(\text{mod } m\) to \(1.\)
The multiplicative inverse \(\text{mod } m\) of an integer \(n\) is defined as the integer \(s\) in
\(\mathbb{Z}_m\) such that:
$$sn \equiv_{m} 1$$
This can be rewritten as:
$$sn \bmod m = 1 \bmod m$$
Knowing any modulus \(m\) must be greater than \(1\), we can simplify:
$$sn \bmod m = 1$$
⚠ The only way an integer \(n\) can have a multiplicative inverse \(\text{mod } m\) is if \(n\) and
\(m\) are coprime (in other words, if their
greatest common
divisor is \(1\)).
⚠ The multiplicative inverse \(\text{mod } m\) may also be called "inverse \(\text{mod } m\)" or
"modular multiplicative inverse."
⚠ It is possible for an integer to be its own inverse \(\text{mod } m.\)
The extended Euclidean algorithm can quickly find a modular
multiplicative inverse if it exists.
If \(\gcd(a, b) = 1\), the integers \(x\) and \(y\) returned by the extended Euclidean algorithm will
satisfy:
$$ax + by = 1$$
Let's play around with this equation for a bit. Rearranging:
$$xa - 1 = -by$$
Remember that two integers are congruent \(\text{mod } b\) if and only if \(b\) divides their
difference. Here, \(xa - 1\) is written as an integer multiple of \(-by\), meaning \(b \mid (xa - 1)\),
so therefore:
$$xa \equiv_{b} 1$$
$$xa \bmod b = 1 \bmod b$$
$$xa \bmod b = 1$$
It appears that \(x\) satisfies the equation in the definition of the inverse \(\text{mod } b\) of
\(a\), but remember, that definition also requires it to be in the ring \(\mathbb{Z}_b.\) So, to ensure
\(x\) is in \(\mathbb{Z}_b\), just use the \(\bmod\) operation:
$$x \bmod b$$
Therefore, \(x \bmod b\) is the inverse \(\text{mod } b\) of \(a.\)
So, if you want to know the inverse \(\text{mod } b\) of an integer \(a\), make sure the Euclidean
algorithm returns \(\gcd(a, b) = 1.\) Then, use the \(\bmod\) operation to bring its corresponding
integer coefficient \(x\) into the ring \(\mathbb{Z}_b.\) You can also just as easily find the inverse
\(\text{mod } a\) of \(b\) by computing \(y \bmod a.\)
⚠ The RSA encryption algorithm involves finding modular multiplicative inverses.