5. Congruences

As $\mathbb{Z}$ is infinite, we would like to look at the numbers "smaller" than the integers in which contains a "local" data of the integers. Before we even discuss what this means, let's fix $m$, an integer. Let $n$ be any integer, then by the division algorithm, there exists unique $q,r$ such that $n=mq+r$, then consider a situation there $n = r$. For instance if $n=7$ and $m=3$, then $7 = 2 \cdot 3 +1$, hence $1 = 7$. If we have a set $A$ and we give an equivalence relation on the set by $a \sim b$ if the following conditions hold:
     1) $a \sim a$
     2) $a \sim b$, then $b \sim a$
     3) $a \sim b$ and $b \sim c$ then $a \sim c$.
For instance, $=$ on $\mathbb{Z}$ would give an equivalence relation. Now we consider a new equal, or the equivalence relation $\equiv ~(\bmod{m})$ where $a \equiv b ~(\bmod{m})$ if $m|a-b$ or, in order words, $a$ and $b$ have the same remainder. Consider $[n]_m$ be the set of all elements in $\mathbb{Z}$ such that is equivalent to $n$ under $\equiv~(\bmod{m})$.

Proposition: There are $m$ distinct sets of $[n]_m$.
Proof) $m|a-b$ if and only if $a$ and $b$ has the same remainder, and there are only $m$ different remainders which are $0, \ldots, m-1$, hence there are only $m$ distinct sets.

Definition: Let $\mathbb{Z}/m\mathbb{Z} = \{[n]_m~|~n \in \mathbb{Z} \} = \{ [0]_m, \ldots, [m-1]_m \}$. 

The reason why we choose such a notation is apparent when you delve into ring theory, but for now, just take it for granted. Then this set becomes a ring which I will not define here, but basically it says the following:

Proposition: 
If we define $[n]_m + [k]_m = \{ l+r | l \in [n]_m$ and $r \in [k]_m \}$ 
                      $[n]_m \cdot [k]_m = \{ lr | l \in [n]_m$ and $r \in [k]_m \}$ 
     1) $[n_1]_m + [n_2]_m = [n_1 + n_2]_m$ 
     2)$[n_1]_m \cdot [n_2]_m = [n_1n_2]_m$
Proof) 
     1) This is saying that $a \equiv n_1 ~(\bmod{m})$ and $b \cong n_2~(\bmod{m})$ and we want to show that $a+b \equiv n_1 + n_2 ~(\bmod{m})$. Before we continue, we establish a following lemma:

Lemma: If $a, b \in [n]_m$ if and only if $a = b+km$ for some $k$.
Proof) This is really easy to see because $m|a-b \Rightarrow$ there exists $k$ such that $km = a-b$, hence $a = b + km$. The converse is trivial.

Hence $a = n_1 + k_1m$ and $b = n_2 + k_2m$, then we have $a+b = n_1 + n_2 + (k_1+k_2)m$, hence $(a+b)- (n_1 +n_2) = (k_1+k_2)m$ is divisible by $m$, hence we establish 1).
     2) Similiarly, $a = n_1 + km$ and $b = n_2 + k'm$ then $ab = n_1n_2 + kn_2m + k'n_1m + kk'm^2$, hence $ab - n_1n_2 = m(kn_2 + k'n_1+kk'm)$, hence the result.

Now, there is an interesting property when the two numbers are prime.  Before we establish this, we see that $[1]_m \cdot [n]_m = [n]_m$, so $[1]_m$ is an identity in the sense that when you multiply anything to it, you get the same thing. Similar to the rational numbers, when you have $n$, then you want to find $k$ such that $nk=1$, and we know that $1/n$ exists in the rational if $n$ is not zero. 

Proposition: Let $n,m$ be coprime, then $[n]_m$ has an inverse.
Proof) If $n,m$ are coprime, then there exists integers $x,y$ such that $nx + my = 1$, then this amount to say that $nx - 1 = m(-y)$ which is divisible by $m$, hence $[nx]_m = 1 \Rightarrow [n]_m[x]_m = 1$.

Corollary: Let $p$ be a prime, then $[n]_p$ has an inverse when $n \neq 0$.
Proof) Direct application of the above.

A ring is called a field, if it has the property stated by the corollary. For example, the set of rational numbers is a field. We know that the set $\mathbb{Z}/p\mathbb{Z}$ is has prime number of elements by our first proposition (i.e. the set has finite elements), and, in fact, any finite field is of the form $\mathbb{Z}/p\mathbb{Z}$ or an extension of this form.