Number Theory :: Modular Arithmetic

Modular Arithmetic

Modular Arithmetic (also referred to as Congruence) is related to the concept of divisibility between two integers and their remainder.

From basic mathematics, given two integers $a$ and $b$, we know the following to be true:

    $\Large{\frac{a}{b}}$ $= q + r$

where $q$ is the Quotient and $r$ is the Remainder.

The operator that produces the remainder $r$ given the two integers $a$ and $b$ is the Modulo operator, often indicated as $mod$.

Since we are interested only in the remainder, we can use the modulo notation:

    $a \: mod \: b = r$

For example:

    $\Large{\frac{12}{5}}$ $=$ quotient of $2$ and remainder of $2$

Using the modulo notation:

    $12 \: mod \: 5 = 2$

Often times, we will see a congruence notation as follows:

    $a \equiv b \: (mod \: m)$ ... $\color{crimson} (1)$

This is a short-form notation for:

    $a \: mod \: m = b \: mod \: m$

Or, one would say $a$ is congruent to $b$ modulo $m$

The equation $\color{crimson} (1)$ from above, is nothing more than the following:

    $a - b = k.m$

Or:

    $a = b + k.m$ ... $\color{crimson} (2)$

where $k$ is some integer multiple.

The integer value from the $mod$ operation is often referred to as Residue.

Note, that the value of the residue $r$ is in the range: $0 \le r \lt m$.

Rules of Modular Arithmetic

The following are some rules of modular arthimetic:

• Given $a \equiv b \: (mod \: m)$, implies $b \equiv a \: (mod \: m)$

• Given $(a + b) \: (mod \: m)$, implies $[(a \: mod \: m) + (b \: mod \: m)] \: (mod \: m)$

• Given $(a - b) \: (mod \: m)$, implies $[(a \: mod \: m) - (b \: mod \: m)] \: (mod \: m)$

• Given $(a.b) \: (mod \: m)$, implies $[(a \: mod \: m).(b \: mod \: m)] \: (mod \: m)$

• If $a \equiv b \: (mod \: m)$ and $b \equiv c \: (mod \: m)$, then $a \equiv c \: (mod \: m)$

• If $a \equiv b \: (mod \: m)$, then $a + c \equiv b + c \: (mod \: m)$

• If $a \equiv b \: (mod \: m)$, then $a - c \equiv b - c \: (mod \: m)$

• If $a \equiv b \: (mod \: m)$ and $c \equiv d \: (mod \: m)$, then $a + c \equiv b + d \: (mod \: m)$

• If $a \equiv b \: (mod \: m)$ and $c \equiv d \: (mod \: m)$, then $a - c \equiv b - d \: (mod \: m)$

• If $a \equiv b \: (mod \: m)$, then $a.c \equiv b.c \: (mod \: m)$

• If $a \equiv b \: (mod \: m)$ and $c \equiv d \: (mod \: m)$, then $a.c \equiv b.d \: (mod \: m)$

• If $a \equiv b \: (mod \: m)$, then $a^c \equiv b^c \: (mod \: m)$

Let us now look at a problem along with its solutions.

Example-1	Find the residue for $10^{100} \: mod \: 9$
Given $10^{100} \: mod \: 9$, it can be re-written as $10^{99}.10 \: mod \: 9$ That is, $10^{100} \: mod \: 9 = 10^{99}.10 \: mod \: 9 = [(10^{99} \: mod \: 9).(10 \: mod \: 9)] \: mod \: 9$ We know the fact $10 \: mod \: 9 = 1$ Applying the above fact, we therefore get: $10^{100} \: mod \: 9 = 1$

Now, let us now look at another problem along with its solutions.

Example-2	Find the residue for $(1! + 2! + 3! + ... + 100!) \: mod \: 6$
We know $3! = 3.2.1 = 6$ and therfore $3! \: mod \: 6 = 0$ All the terms after $3!$, such as $4!$, $5!$, ..., $100!$ will all have a residue of ZERO $mod \: 6$ Therefore: $(1! + 2! + 3! + ... + 100!) \: mod \: 6 = (1 + 2 + 0 + ... + 0) \: mod \: 6 = 3$

Fermat's Little Theorem

For a given prime number $p$, an integer $a$, and $gcd(a, p) = 1$, then the following equation is true:

    $a^{p-1} \equiv 1 \: (mod \: p)$ ... $\color{crimson} (3)$

When $p = 3$ and $a = \set{1, 2}$, we find $a^2 \: mod \: 3 = 1$.

Similarly, when $p = 5$ and $a = \set{1, 2, 3, 4}$, we find $a^4 \: mod \: 5 = 1$.

One can leverage the Fermat's Theorem to simplify modulo computations.

Let us look at problem along with its solutions.

Example-3	Find the residue for $2^{35} \: mod \: 7$
The value $2^{35}$ can be written as $2^{(6.5)+5} = (2^6)^5.2^5$ From Fermat's Theorem, we know $2^6 \: mod \: 7 = 1$ Therefore: $(2^6)^5.2^5 \: mod \: 7 = (1^5.2^5) \: mod \: 7 = 4$

© PolarSPARC