Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, which considers the remainder.

In modular arithmetic, numbers "wrap around" upon reaching a given fixed quantity (this given quantity is known as the modulus) to leave a remainder.

Parity

Parity refers to the state of being even or odd.

• Integers have one of two different parities:
  • $x$ is even means $2|x$
  • $x$ is odd means $2|(x-1)$
• Some properties:
  • even $\pm$ even = even
  • even $\pm$ odd = odd
  • odd $\pm$ odd = even

Clock Arithmetic

Time wraps around at 12. In addition, adding any multiple of 12 hours does not change the o'clock.

example 1: now is 10 o'clock. What time is it after 5 hours?

3 o'clock

example 2: what time is it after 27 hours from now? What time is it after 39 hours from now?

console.log(27 % 12); console.log(39 % 12);console.log(15 % 12);

1console.log(27 % 12); console.log(39 % 12);console.log(15 % 12);

1: 3 2: 3 3: 3

So a and b are the same o'clock if 12 divides a - b or (a - b) % 12 == 0

const a = 15;
const b = 15 + 12 * 2; // 39
const result = (a - b) % 12;
console.log(result); // 0

Modular Arithmetic

Modular arithmetic is an abstraction of parity and clock arithmetic.

• Parity is arithmetic modulo 2
• Clocks use arithmetic modulo 12

Modular Equivalence

Modular equivalence is also called modular congruence.

Definition: $n | (a - b)$, if $a - b$ is divisible by $n$. Then $a$ and $b$ are equivalent modulo n.

$$n | (a - b) \implies a \equiv b \ (\textrm{mod}\ n)$$

Example:

$$\begin{aligned} a & = 50 \\ b & = 20 \\ n & = 10 \\ \\ \frac{a-b}{n} & = \frac{30}{10} = 3 \dots 0 \\ a & \equiv b \ (\textrm{mod}\ n) \end{aligned}$$

Properties of Modular Arithmetic

Modular equivalence plays nicely with ["addition", "subtraction", "multiplication"].

Suppose that $a_1 \equiv b_1 \ (\textrm{mod}\ n)$ and $a_2 \equiv b_2 \ (\textrm{mod}\ n)$. Then:

• $a_1 + a_2 \equiv b_1 + b_2 \ (\textrm{mod}\ n)$
• $a_1 - a_2 \equiv b_1 - b_2 \ (\textrm{mod}\ n)$
• $a_1 \times a_2 \equiv b_1 \times b_2 \ (\textrm{mod}\ n)$

This means we can use many tools from normal arithmetic with modular arithmetic.

mod Operator

Definition: $a\ \textrm{mod}\ n$ is the smallest non-negative integer $c$ such that $a \equiv c\ (\textrm{mod}\ n)$.

Equivalently, $a\ \textrm{mod}\ n$ is the remainder when you divide $a$ by $n$ ($\frac{a}{n}$).

Example: $11\ \textrm{mod}\ 2 = 1$, because $11 = (5 \times 2) + 1$

Proof of Lemma

A lemma is little statement that is true in a mathematical theory, derived from its axioms. We can show that it is true by using a proof which shows the steps necessary to get from the axioms to the statement. We can also use other lemmas in the proof if we have already proved them.

Lemma: Let $a$ and $b$ be integers. $a\ \textrm{mod}\ b = 0 \implies b|a$.

Proof:

1. According to the definition of mod operator, $a \equiv 0 \ (\textrm{mod}\ b)$.
2. Use modular equivalence definition, $b | (a - 0)$
3. Based on a well known lemma, we known that $a - 0 = a$, so $b | a$

Applications of Modular Arithmetic

• Parity
• Clock arithmetic
• RSA encryption
• CPU integer arithmetic
• Indices for ring buffers

Appendix

Code

modular equivalence

function isEquivalent(a, b, n) { const diff = a - b; const divisible = diff % n === 0; return divisible; } // a = 40, b = 70, n = 10 console.log(isEquivalent(40, 70, 10)); // a = 40, b = 70, n = 8 console.log(isEquivalent(40, 70, 8));

1function isEquivalent(a, b, n) {
2  const diff = a - b;
3  const divisible = diff % n === 0;
4  return divisible;
5}
6
7// a = 40, b = 70, n = 10
8console.log(isEquivalent(40, 70, 10));
9
10// a = 40, b = 70, n = 8
11console.log(isEquivalent(40, 70, 8));

1: true 2: false

Vocabulary

congruence

noun

1. The quality of agreeing or corresponding; being suitable and appropriate.
2. A relation between two numbers indicating they give the same remainder when divided by some given number.
3. The quality of being isometric — roughly, the same measure and shape.
4. More generally: any equivalence relation defined on an algebraic structure which is preserved by operations defined by the structure.

modulo

noun

1. The operation or function that returns the remainder of one number divided by another.

preposition

1. Given a specified modulus of.
2. Except for differences accounted for by.
3. (extended use) With due allowance for (a specified exception or particular detail).

axioms

noun

1. A seemingly self-evident or necessary truth which is based on assumption; a principle or proposition which cannot actually be proved or disproved.
2. (proof theory) A fundamental assumption that serves as a basis for deduction of theorems; a postulate (sometimes distinguished from postulates as being universally applicable, whereas postulates are particular to a certain science or context).
3. An established principle in some artistic practice or science that is universally received.