Modular Arithmetic

Notation

Meaning

floor function: largest integer not larger than x

Examples

PreviousEncryption + Authentication NextFast Modular Multiplication

Last updated 10 months ago

Notation Meaning

Notation	Meaning
$m \mid n$	$m$ divides $n$
$m \nmid n$	$m$ does not divide $n$
$n \equiv r (mod m)$	$m \mid (n-r)$ , that is, as $m$ divides $n-r$ , $n$ and $r$ have the same remainder when divided by $m$
$\lfloor x \rfloor$	floor function: largest integer not larger than x
$n mod m$	(binary operator) remainder of $n$ when divided by $m$ ( $m$ is called the modulus, which we assume here to be a positive integer). Equal to $n-m \lfloor \frac{n}{m} \rfloor$ . Note that $0 \le r \lt m$ . In `C, Python, Java`, and `pari-gp`, it can be computed using using the `%` binary operator (applied to unsigned integers).
$gcd(a,b)$	gratest common divisor of $a$ and $b$ .
$lcm(a,b)$	least common multiple of $a$ and $b$ ; equal to $ab/ gcd(a,b)$ .
$\mathbb{Z}_m$	set of equivalence classes modulo $m$ ; slightly abusing the mathematical notation for equivalence classes, $\mathbb{Z}_m = \lbrace 0, 1, ..., m-1 \rbrace$ .

$m \mid n$

$m$ divides $n$

$m \nmid n$

$m$ does not divide $n$

$n \equiv r (mod m)$

$m \mid (n-r)$ , that is, as $m$ divides $n-r$ , $n$ and $r$ have the same remainder when divided by $m$

$\lfloor x \rfloor$

floor function: largest integer not larger than x

$n mod m$

(binary operator) remainder of $n$ when divided by $m$ ( $m$ is called the modulus, which we assume here to be a positive integer). Equal to $n-m \lfloor \frac{n}{m} \rfloor$ . Note that $0 \le r \lt m$ . In C, Python, Java, and pari-gp, it can be computed using using the % binary operator (applied to unsigned integers).

$gcd(a,b)$

gratest common divisor of $a$ and $b$ .

$lcm(a,b)$

least common multiple of $a$ and $b$ ; equal to $ab/ gcd(a,b)$ .

$\mathbb{Z}_m$

set of equivalence classes modulo $m$ ; slightly abusing the mathematical notation for equivalence classes, $\mathbb{Z}_m = \lbrace 0, 1, ..., m-1 \rbrace$ .