Combinatorics/Congruences

The basic facts about congruences can be found in any Number Theory book. We will merely review them here. For details please consult any standard text on number theory.

For any integer $n\geq 2$ we say that two integers a and b are congruent modulo n or $a\equiv b{\pmod {n}}$ if n divides the difference a-b.

For example, 5 and 11 are congruent modulo 3:

11≡5(mod 3) because 11 − 5 gives 6, which is divisible by 3. Or, equally, both numbers give the same remainder when divided by 3:

11 = 3×3 + 2

5 = 1×3 + 2

If a1 ≡ b1 (mod n) and a2 ≡ b2 (mod n) then a1 + a2 ≡ b1 + b2 (mod n) and a1a2 ≡ b1b2 (mod n) This turns the congruence (mod n) into an equivalence on the ring of all integers. The equivalence class of the integer a, denoted by ${\overline {a}}_{n}$, is the set $\left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}$. This set, consisting of the integers congruent to a modulo n, is called the congruence class or residue class of a modulo n. Another notation for this congruence class, which requires that in the context the modulus is known, is $\displaystyle [a]$.

The set of congruence classes modulo n is denoted as $\mathbb {Z} /n\mathbb {Z}$ (or, alternatively, $\mathbb {Z} /n$ or $\mathbb {Z} _{n}$) and defined by:

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.$

$\mathbb {Z} /n\mathbb {Z}$ has n elements, and can be written as:

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n-1}}_{n}\right\}.$

We can define addition, subtraction, and multiplication on $\mathbb {Z} /n\mathbb {Z}$ by the following rules:

• ${\overline {a}}_{n}+{\overline {b}}_{n}={\overline {a+b}}_{n}$
• ${\overline {a}}_{n}-{\overline {b}}_{n}={\overline {a-b}}_{n}$
• ${\overline {a}}_{n}{\overline {b}}_{n}={\overline {ab}}_{n}.$

The verification that this is a proper definition uses the properties given before.

In this way, $\mathbb {Z} /n\mathbb {Z}$ becomes a commutative ring. In fact, it turns out that $\mathbb {Z} /n\mathbb {Z}$ is a field (which is a special kind of a commutative ring) if and only if n is a prime number.

Fermat's little theorem (not to be confused with Fermat's last theorem) states that if p is a prime number, then for any integer a, $a^{p}-a$ will be evenly divisible by p. This can be expressed as follows:

$a^{p}\equiv a{\pmod {p}}\,\!$

The totient function $\varphi (n)$ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n. For example, $\varphi (9)=6$ since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9.

Euler's theorem (also known as the Fermat-Euler theorem or Euler's totient theorem) states that if n is a positive integer and a is coprime to n, then

$a^{\varphi (n)}\equiv 1{\pmod {n}}$

where φ(n) is Euler's totient function and "... ≡ ... (mod n)" denotes congruence modulo n.

The theorem is a generalization of Fermat's little theorem.