What Is Congruence Modulo N?

Definition

Two integers, $a$ and $b$, are congruent modulo $n$ if and only if they have the same remainder when divided by $n$

In other words, for some integer $k$ (positive or negative):

$$a=b+kn$$

or

$$a-b=kn$$

When two numbers are congruent modulo $n$, it is denoted by:

$$a \equiv b \pmod n$$

Manipulations in congreuence modulo $n$

**A1: ** Given that $a\equiv b \pmod n$, then $a+c\equiv b+c \pmod n$

A2 Given that $a\equiv b \pmod n$ and $c\equiv d \pmod n$, then $a+c\equiv b+d \pmod n$

**M1: ** Given that $a\equiv b \pmod n$, then $ac\equiv bc \pmod n$

**M2: ** Given that $a\equiv b \pmod n$ and $c\equiv d \pmod n$, then $ac\equiv bd \pmod n$

**M3: ** Given that $a\equiv b \pmod n$, then $a^c\equiv b^c \pmod n$

This explanation is going to be quite long because it is going to explain the modulus function. Skip through this next part if you like!

There is an equivalence relation called the "modulo $n$" equivalence relation that is written like this: $a \equiv b \hspace{1mm}mod \hspace{1mm}c .$ a and b are said to be equivalent modulo c if and only if $\frac{\left(a-b\right)}{c}$ is an integer. It should be obvious that $a \equiv a \hspace{1mm}mod \hspace{1mm}c$ for any and all integers a and c.

In math, for convenience, we refer to a number as another number modulo another number. That is, $a \hspace{1mm}mod \hspace{1mm} b = c, where \hspace{1mm}0 \leq c > b.$ So if I asked you,"what is 8 mod 3?", you should say, "2!", because 2 is the only value of c that satisfies the equation above, where a=8 and b=3. Obviously c is unique for all choices of a and b. Now here is a nifty theorem below that you can try to prove yourself:

If a,b and c are integers, $ab\hspace{1mm}mod\hspace{1mm}c=\left[\left(a\hspace{1mm}mod\hspace{1mm}c\right)\cdot\left(b\hspace{1mm}mod\hspace{1mm}c\right)\right]mod\hspace{1mm}c$

Here is a more intuitive and easier to prove theorem: $\left(a+b\right)\hspace{1mm}mod\hspace{1mm}c=\left(a\hspace{1mm}mod\hspace{1mm}c\right)+\left(b\hspace{1mm}mod\hspace{1mm}c\right)$

This is a great introduction to modular arithmetic.