Proposition 1

Definition

If $a,b,m\in \Z$ and $m \neq 0$, then we can say that a is congruent to $b$ modulo $m$ if m divides $b-a$. $a \equiv b (m) $

• $a\equiv a(m)$
• $a\equiv b(m) \implies b \equiv a(m)$
• $a\equiv b(m),b\equiv c(m) \implies a\equiv c(m)$

Proof:

• $m|(a-a)=0$
• $m|(a-b) \implies m|(b-a)$​
• $m|(b-a),m|(c-b)\implies m|(c-b+b-a)=c-a$

That implies, congruence modulo is an equivalence relation on a set of integer.

Proposition 2

Definition

let $\bar a$ as a set of integers that $\bar a \equiv a(m)$. $\bar a = a+km$​. $\bar a$ is called a congruence class modulo $m$.

• $\bar a=\bar b \iff a \equiv b(m)$​
• $\bar a \neq \bar b \iff \bar a \cap \bar b = \empty$​
• There are m distinct congruence classes modulo m

Proof:

• If $\bar a = \bar b，$ $a\in \bar a = \bar b$ that is $a\equiv b(m)$. If $a\equiv b(m),$ $a\in \bar b$ so $\bar a \subset \bar b$.
• If $\bar a \cap \bar b \neq \empty$, we shall have $c\equiv a(m), c\equiv b(m)$. That is $a\equiv b(m)$ so $\bar a = \bar b$.
• Suppose $0 \leq k < l < m$ and $\bar k = \bar l$. That implies $k \equiv l(m) \implies m|(l-k)$. But $(l-m) < m$, that is a contradiction. So for $0 \leq k < l < m$, $\bar k \neq \bar l$. So there are m distinct congruence classes.

Proposition 3

Definition

If $\bar a_1,\bar a_2, \bar a_3...\bar a_m$ are a complete set of congruence classes modulo m, then $\{\bar a_1,\bar a_2, \bar a_3...\bar a_m\}$ is called a complete set of residues modulo m.

The set of congruence classes modulo m is $\Z/m\Z$.

This set can be made into a ring.

If $a\equiv c(m), b\equiv d(m)$, then $a+b\equiv c+d\ (m)$ also $ab\equiv cd(m)$.

Proof:

By definition, $m|c-a, m| d-b$. $$m|(c-a)+(d-b) = (c+d)-(a+b) \implies a+b \equiv c+d \ (m)$$

$$m|c(d-b)+b(c-a) = cd -ab \implies ab \equiv cd\ (m)$$

Application

If $p(x)\in \Z[x]$, assume $a\equiv b(m)$, we have $p(a)\equiv p(b)(m)$. So when $m=2$, we have $p(a)\equiv p(0)(2)$ or $p(a)\equiv p(1)(2)$.

For $p(x)=a_0x^n+a_1x^{n-1}...a_{n-1}x+a_n$. $p(0)=a_n$ and $p(1)=a_0 + a_1+...a_n$.

If $p(x)\in \Z[x], p(0),p(1)$ are both odd, there are no integer roots.