Modular Arithmetic

Congruency

• Theorem. Let $a$ be an integer and let $N$ be a positive integer. Then there exist unique integers $q, r$ for which $a = qN+ r$ and $0 ≤ r < N$.
  • We denote by $[a \bmod N]$ the remainder obtained when $a$ is divided by $N$. $0 \le [a \bmod N] \le N - 1$.
  • $a = b \bmod N \Leftrightarrow [a \bmod N] = [b \bmod N]$. We say that $a$ and $b$ are congruent modulo N.
  • Congruence mod $N$ defines an equivalence class on the set of integers.

Addition / Subtraction / Multiplication

• Congruence modulo $N$ respects the rules of addition, subtraction and multiplication:

  $$\begin{array}{c} a=a^{\prime} \bmod N and b=b^{\prime} \bmod N \\ \Downarrow \\ (a+b)=\left(a^{\prime}+b^{\prime}\right) \bmod N and a b=a^{\prime} b^{\prime} \bmod N \end{array}$$

Division

• Definition. If for a given integer $b$, there exists an integer $c$ such that $bc = 1 \bmod N$, we say that $b$ is invertible modulo $N$, and call $c$ a multiplicative inverse of $b$ modulo $N$.
• In particular, if $ab = cb \bmod N$ and $b$ is invertible, multiplying by $b^{-1}$ gives $a = c \bmod N$.

Euler's Theorem

• Theorem. Let $b, N$ be integers, with $b \ge 1$, and $N > 1$. Then $b$ is invertible modulo $N$ if and only if $\gcd(b, N) = 1$.
• Lemma. Let $a, b$ be positive integers. Then there exist integers $X, Y$ such that $Xa + Yb = \gcd(a, b)$. Furthermore, $\gcd(a, b)$ is the smallest positive integer that can be expressed this way.

Extended Euclidean Algorithm eGCD

• Extended Euclidean Algorithm eGCD:

  • Input: Integers $a, b$ with $a ≥ b > 0$.

  • Output: $(d, X, Y)$ with $d = \gcd(a, b)$ and $Xa + Yb = d$.

  • If $b$ divides $a$ return $(b,0,1)$;

  • Else compute integers $q, r$ with $a = qb + r$ and $0 < r < b$,

    Set $(d, X, Y) := \operatorname{eGCD}(b, r)$ (note that $Xb+Yr=d$),

    Return $(d, Y, X - Yq)$.

• The Extended Euclidean algorithm gives $[X \bmod b]$ as the multiplicative inverse of $a \bmod b$, and $[Y \bmod a]$ as the multiplicative inverse of $b \bmod a$ when $\gcd(a, b) = 1$.

An Efficient Modular Exponentiation Algorithm

• To compute $[a^b \bmod N]$:

  exp(a, b, N) {
  	t = 1
  	x = a
  	while (b > 0) {
  		if (b is odd) {
  			t = [t*x mod N]
  			b = b-1
  		}
  		x = [x^2 mod N]
  		b = b/2
  	}
  	return t
  }

  Running Time of this algorithm is polynomial in $\|a\|,\|b\|,\|N\|$.

— Mar 14, 2023

Modular Arithmetic by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.