Modulus and remainders

Modulus and remainders

Remainders

Division is defined between natural numbers. However there are many cases where this division does not map to a natural number. For example:

\(\dfrac{7}{3}\)

We can divide \(6\) of the \(7\) by \(3\), giving \(2\) with \(1\) remaining.

Alternatively we can divide \(3\) of the \(7\) by \(3\), giving \(1\) with \(4\) remaining

Or we could divide \(0\) of the \(7\) by \(3\) giving \(0\) with \(7\) remaining.

The remainder refers to the lowest possible number - in this case \(1\).

Residue systems

Least residue system modulo \(n\)

This is the set of numbers from \(0\) to \(n-1\).

Complete residue system

This a set of numbers none of which are congruent \(\mod n\). That is, for no pair \(\{a,b\}\) does \(a \mod(n)=b mod(n)\)

Reduced residue system

This is a complete residue system where all numbers are relatively prime to \(n\).

Congruence

\(5\) and \(11\) are congrument \(\mod 3\)

If \(a \mod(n)=b mod(n)\) then \(a\) and \(b\) are congruent mod \(n\).