# 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$$.