Modular Arithmetic

Congruence modulo n is an equivalence relation on the integers. It partitions the integers into n equivalence classes. The equivalence classes are called the residues modulo n. Any member of a residue is a representative.

Arithmetic can be defined on residues.

Sometimes we can perform operations on representatives of the residues using customary integer operations and the result will be a representative of the residue we would have got if we performed the corresponding operations on the residue classes.

This is true for addition and multiplication and we can use this to show that addition and multiplication on residues are both associative and commutative. They also observe the distributive law.

The additive identity is the reside class with zero in it. The additive inverse residue exists and can be found by computing the additive inverse of a representative.

In summary, the residues modulo n are a commutative ring with identity and addition, negation, and multiplication can be calculated by doing the corresponding operations on representatives.

# Exponentiation

Exponentiation can be calculated using multiplication, so the preceding section shows us that we can compute exponentiation on a residue by using a representative. Note that the base is a residue, but the exponent is an integer.

There is a shortcut for computing exponents due to Euler

(1)
\begin{align} a^{\phi(n)} \equiv 1 \;(\text{mod}\;n) \end{align}

The congruence allows us to compute any exponent with fewer than φ(n) multiplications.

The function φ is called Euler's totient, and is

(2)
\begin{align} \phi(n) = n \prod_{p | n} \frac{p - 1}{p} \end{align}

where the product is over all primes that divide n. When n is itself prime, Euler's Theorem reduces to Fermat's Little Theorem:

(3)
\begin{align} a^{p-1} \equiv 1 \;(\text{mod}\; n) \end{align}

# Multiplicative Inverse and Division

Division on the integers is often not defined. An integer a is divisible by b if there is another integer m such that:

(4)
$$a = mb$$

Multiplicative inverses for most integers don't exist. The exceptions are 1 and -1, which are their own inverses.

For residues, the situation is better. A nonzero residue a modulo n has a multiplicative inverse if and only if a and n are relatively prime. The extended Euclidean algorithm will find x and y such that ax + ny = 1, and thus x is the multiplicative inverse of a.

If the modulus n is prime, then all nonzero residues have multiplicative inverses and the residues are a field.

If n is not prime, the residues are not an integral domain and cancellation is not always possible. If d is the greatest common divisor of a and n, then for all z and z' we have this result:

(5)
\begin{align} az \equiv az' \;(\text{mod}\; n) \iff z \equiv z' \;\left(\text{mod}\; \frac{n}{d}\right) \end{align}

If a and n are relatively prime, which means d is 1, we can cancel a from both sides of the equation.

# Square Roots

Non-zero complex numbers have two square roots.

Positive real numbers have two square roots and negative real numbers have none.

Positive integers have two square roots if they are perfect squares, otherwise they have none.

Non-zero residues have either two square roots or none. In the former case, the residue is said to be a quadratic residue and in the latter case a quadratic nonresidue. Determining whether a residue is a quadratic residue is complicated. The following notation, called the Legendre symbol, is used when p is an odd prime:

(6)
\begin{align} \left( \frac{a}{p} \right) = \begin{cases} \;\; 1 \;\;\; a \; \text{is a quadratic residue} \\ \;\; 0 \;\;\; p \mid a \\ -1 \;\;\; a \; \text{is a quadratic nonresidue} \end{cases} \end{align}

The following always hold:

(7)
\begin{align} \left( \frac{1}{p} \right) = 1 \\ \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}} \\ \left( \frac{2}{p} \right) = (-1)^{\frac{p^2 - 1}{8}} \\ \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p} \right) \end{align}

When a and p are relatively prime then

(8)
\begin{align} \left(\frac{a^2}{p} \right) = 1 \end{align}

The Jacobi symbol is a generalization of the Legendre symbol where p is replaced by any positive odd integer n. The Kronecker symbol is a further generalization where n can be any non-zero integer.

The quadratic reciprocity law states that for odd primes q and p which both are are of the form 4k +3, then exactly one of the following congruences has a solution:

(9)
\begin{align} x^2 \equiv q \;(\text{mod}\;p) \end{align}
(10)
\begin{align} x^2 \equiv p \;(\text{mod}\;q) \end{align}

Moreover, if q and p are odd primes not both of the form 4k + 3, then both congruences are solvable or both congruences are not.

How the quadratic reciprocity law is used:

(11)
\begin{align} \left(\frac{3}{5}\right) = \left(\frac{5}{3}\right) = \left(\frac{2}{3}\right) = (-1)^{\frac{3^2 - 1}{8}} = -1 \end{align}
(12)
\begin{align} \left(\frac{3}{7}\right) = -\left(\frac{7}{3}\right) = -\left(\frac{1}{3}\right) = -1 \end{align}

non-prime residue

modulus 2

non-prime modulus

how to find the square roots

# Discrete Logarithm

The discrete log of g base b, where both g and b are residues, is an integer k such at bk = g. A brute force search has run time which is linear in the size of the multiplicative group, or exponential in the number of digits in the size of the multiplicative group. Better algorithms exist, but none are polynomial in the number of digits in the size of the multiplicative group.

# Chinese Remainder Theorem

If we have multiple equations with the same modulus, we can use substitution to find a solution.

If the moduli on the equations are different, the Chinese Remainder Theorem tells us there is a solution under certain conditions. In particular there is a solution a to the following system of equations, provided that the ni are all pairwise relatively prime:

(13)
\begin{align} a \equiv a_i \mod n_i \;\;\; (i = 1,\ldots,k) \end{align}

Moreover, if a and a' are two solutions, then:

(14)
\begin{align} a \equiv a' \mod \prod_{i=1}^k n_i \end{align}
page revision: 99, last edited: 07 Nov 2017 17:09