4.1 Modular Arithmetic

Modular Arithmetic

For any integer $x\in \mathbb{Z}$ and any positive integer $m\in \mathbb{N}$, known as the modulus, the division algorithm guarantees that there exist unique integers $q$ (the quotient) and $0\le r\le m-1$ (the remainder), such that
$x=qm+r.$
The remainder, written as $r=x(\mathrm{mod}m)$, is the unique value in the set $\{0,1,\dots ,m-1\}$ that is congruent to $x$ modulo $m$.

In general, two integers $x,y\in \mathbb{Z}$ are said to be congruent modulo $m$, written $x\equiv y(\mathrm{mod}m)$, if they leave the same remainder when divided by $m$. Equivalently, $x\equiv y(\mathrm{mod}m)$ means that $m\mid (x-y)$ (i.e., the difference $x-y$ is divisible by $m$).

We now define arithmetic operations. Suppose $a\equiv c(\mathrm{mod}m)$ and $b\equiv d(\mathrm{mod}m)$:

1. Addition: $a+b\equiv c+d(\mathrm{mod}m)$.
2. Multiplication: $a\cdot b\equiv c\cdot d(\mathrm{mod}m)$.
3. Exponentiation: $a^k\equiv c^k(\mathrm{mod}m)$ and $b^k\equiv d^k(\mathrm{mod}m)$. Note that modular arithmetic does not preserve congruence in the exponent.

Intuition & Proof

Floor division and the modulus are complementary operations: floor division gives the integer part of $x$ divided by $m$, while modulo gives the remainder $r$. Any $x\in \mathbb{Z}$ can be decomposed into these parts using the equation $x=\lfloor \frac{x}{m}\rfloor m+(x(\mathrm{mod}m))$. Here, $q=\lfloor \frac{x}{m}\rfloor$ is the quotient, and $r=x(\mathrm{mod}m)$ is the remainder. We now proceed with proving our arithmetic operations.

• Addition. We know that $c=a+\alpha m$ and $d=b+\beta m$ for some $\alpha ,\beta \in \mathbb{Z}$. Therefore, $c+d=a+b+m(\alpha +\beta )$. By definition, $q=\alpha +\beta$ and $r=a+b$, so $a+b\equiv c+d(\mathrm{mod}m)$.
• Multiplication. Just as above, we substitute for $c,d$ such that $cd=(a+\alpha m)(b+\beta m)$. This results in $cd=ab+m(\alpha b+\beta a+\alpha \beta m)$. Then, $q=\alpha b+\beta a+\alpha \beta m$ and $r=ab$, so $a\cdot b\equiv c\cdot d(\mathrm{mod}m)$.
• Exponentiation. We already proved multiplication, so exponentiation is simply an extension of this.

Properties

(Canonical Representation) For any modulus $m$, the set of all integers $\mathbb{Z}$ can be divided into exactly $m$ non-overlapping infinite sets, where each set contains all integers that leave the same remainder when divided by $m$.

(Prime Modulus) For any prime modulus $p$, all numbers in $\{1,\dots ,p-1\}$ have a modular inverse.

This is trivially true, since $\gcd (i,p)=1$ for all $i=1,\dots ,p-1$.

(Wilson’s Theorem) It holds that $(p-1)!\equiv -1(\mathrm{mod}p)$ if and only if $p$ is prime.

Note that $-1\equiv p-1(\mathrm{mod}p)$. We now prove this theorem.

• Sufficiency ($⟹$): in the previous point, we observed that all numbers in $\{1,\dots ,p-1\}$ have a modular inverse. Since all prime numbers are odd (for the exception of $2$, which has a single element in the set of nonzero residues), this means that their set of residues are even, and therefore all elements can be matched with their inverse. Since the only two numbers that are their own inverses and cannot be matched are $1$ and $p-1$, this means that
  $(p-1)!\equiv (p-1)\cdot \dots \cdot 1\equiv p-1\equiv -1(\mathrm{mod}p).$
• Necessity ($⟸$): consider a composite number $n>3$. Then there exist numbers $k,m\in \{1,\dots ,n-1\}$ for which $km=n$, and therefore $km\equiv 0(\mathrm{mod}n)$, which is equivalent to saying that $km\mid (n-1)!$ As such, $(n-1)!\equiv (n-1)\cdot \dots \cdot m\cdot \dots \cdot 1\equiv (n-1)\cdot \dots \cdot 0\cdot 1\equiv 0\not\equiv -1(\mathrm{mod}n).$
  Therefore Wilson’s Theorem only holds if $\gcd (i,n)=1$ for all $i\in \{1,\dots ,n-1\}$, which is only true for prime numbers.

(Fermat’s Little Theorem) For any prime modulus $p$ and any $a\in \{1,\dots ,p-1\}$, it holds that $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Examples

Party Tricks

You are at a party celebrating your completion of the CS 70 midterm. Show off your modular arithmetic skills and impress your friends by quickly figuring out the last digit(s) of each of the following numbers:

Find the last digit of $11^{3142}$. We find that $11^{3142}\equiv 1^{3142}(\mathrm{mod}10)$, and so the last digit is $1$.

Find the last digit of $9^{9999}$. We simplify, such that $9^{9999}\equiv 9\cdot 9^{2(4999)}\equiv 9\cdot 81^{4999}\equiv 9\cdot 1^{4999}\equiv 9(\mathrm{mod}10)$, so the last digit is $9$.

Find the last digit of $3^{641}$. We proceed as before, so $3^{641}\equiv 3\cdot 3^{4(160)}\equiv 3\cdot 81^{160}\equiv 3\cdot 1^{160}\equiv 3$, so the last digit is $3$.