Elementary Observations§

We can observe the parity of numbers after applying addition or multiplication, below we denote an odd integer by $1$ and an even by $0$,

$$ \newcommand{\arraystretch}{1.65} \begin{array}{ c | c c} (*) & 0 & 1\\\hline 0 & 0 & 0\\ 1 & 0 & 1 \end{array} \hspace{3em} \begin{array}{ c | c c} (+) & 0 & 1\\\hline 0 & 0 & 1\\ 1 & 1 & 0 \end{array} $$

In number theory, we often ask ourselves problems of the form: if $f$ is a polynomial in one or several variables with integer coefficients, does $f = 0$ have integer solutions. These equations are called Diophantine equations, after Diophantus who studied them in antiquity.

For example, we can show that the equation $n^2 - 3n + 5 = 0$ does not have integer solutions by inspecting the parity.

  • For $n$ even, we can see that $n^2$ and $3n$ are even by looking at the parity tables, so the left-hand side is always odd.
  • For $n$ odd, $n^2$ and $3n$ are odd and their sum is even, then by adding $5$ odd we get an odd result on the left-hand side again.

Zero is considered even, therefore, there cannot exist an integer solution to this equation as the left-hand side is always odd.

We have shown there exists infinitely many primes, now we will observe that there exists infinitely many primes whose remainder is 3 after division by 4. An integer will have remainders of $0, 1, 2,$ or $3$ after division by $4.$ Then, odd integers will have the form $4k + 1$ or $4l + 3.$ The product of two numbers of the form $4k + 1$ yields a number of the same form. Then, it follows that an integer of the form $4l + 3$ must be divisible by a prime of the same form.

Now, sps. that there exists finitely many positive primes of the form $4l + 3.$ This list contains $3, 7, 11, 19, 23, \dots.$ We let $p_1 = 7, p_2 = 11, p_3 = 19, \dots.$ Sps. $p_m$ is the largest prime of this form and set $N = 4p_1p_2\dots p_m + 3.$ Then, for all the $p_i, p_i \nmid N.$ Notice that $N$ is of the form $4l + 3,$ so it must be divisible by a prime $p$ of the same form. Contradiction, as $p > p_m.$

Congruence in $\mathbb{Z}$§

Congruence

Sps. $a, b, m \in \mathbb{Z}$ for $m \neq 0,$ we say that $a$ is congruent to $b$ modulo $m$ if $m | b - a.$ This relation is written as $a \equiv b \pmod{m}.$

Note: Ireland and Rosen use the notation $a \equiv b\ (m),$ this is not my preferred style.

I will use the notation $a \equiv_m b \iff a \equiv b \pmod{m}$ interchangably.

Proposition 1

  1. $a \equiv_m a.$
  2. $a \equiv_m b \implies b \equiv_m a.$
  3. If $a \equiv_m b$ and $b \equiv_m c,$ then $a \equiv_m c.$

 

  1. $a - a = 0$ and $m | 0.$
  2. If $m | b - a,$ then $m | a - b.$
  3. If $m | b - a$ and $m | c - b,$ then $m | c - a = (c - b) + (b - a).$

This proposition shows that the congruence modulo $m$ is an equivalence relation over the set of integeers. If $a \in \mathbb{Z},$ let $\overline{a}$ be the set of integers congruent to $a$ modulo $m.$ Then, $\overline{a} = \{n \in \mathbb{Z} | n \equiv_m a\}.$ In other words, $\overline{a}$ is the set of integers of the form $a + km.$

In the tables from elementary observations, we used $0$ and $1$ to denote parity. In this case, the congruence class $\overline{0}$ modulo $2$ is the set of even integers, and $\overline{1}$ modulo $2$ the set of odd integers.

Congruence Classes§

Congruence Class

A set with the form $\overline{a}$ is called a congruence class modulo $m.$

Proposition 2

  1. $\overline{a} = \overline{b} \iff a \equiv_m b.$
  2. $\overline{a} \neq \overline{b} \iff \overline{a} \cap \overline{b} = \varnothing.$
  3. There exists exactly $m$ congruence classes modulo $m.$

 

  1. ($\Rightarrow$) If $\overline{a} = \overline{b},$ then $a \in \overline{a} = \overline{b}.$ Thus $a \equiv_m b.$
    ($\Leftarrow$) If $a \equiv_m b,$ then $a \in \overline{b}.$ If $c \equiv_m a,$ then $c \equiv_m b.$ This shows that $\overline{a} \subseteq \overline{b}.$ Since $a \equiv_m b \implies b \equiv_m a,$ we have $\overline{b} \subseteq \overline{a}.$ Therefore, $\overline{a} = \overline{b}.$
  2. Clearly, $\overline{a} \cap \overline{b} = \varnothing \implies \overline{a} \neq \overline{b}.$ However, $\overline{a} \cap \overline{b} \neq \varnothing \implies \overline{a} = \overline{b}.$ In the latter case, let $c \in \overline{a} \cap \overline{b}.$ Then $c \equiv_m a$ and $c \equiv_m b.$ It follows that $a \equiv_m b,$ and by the proof for (1) we have that $\overline{a} = \overline{b}.$
  3. Sps. that $0 \leq k \lt l \lt m.$ $\overline{k} = \overline{l} \implies k \equiv_m l$, or $m | l -k.$ Contradiction as we have $0 \lt l - k \lt m.$ Therefore, $\overline{k} \neq \overline{l}.$ Now let $a \in \mathbb{Z},$ we can find $q, r \in \mathbb{Z}$ such that $a = qm + r,$ where $0 \leq r \lt m.$ It follows that $a \equiv_m r$ and that $\overline{a} = \overline{r}.$ Therefore, the set containing $\overline{0}, \overline{1}, \overline{2}, \dots, \overline{m - 1}$ is a complete set of congruence classes modulo $m$ and each class is distinct.

The Ring $\qr{m}$§

$\qr{m}$

The set of congruence classes modulo $m$ is denoted by $\qr{m}.$

If $\overline{a_1}, \overline{a_2}, \dots, \overline{a_m}$ is the complete set of congruence classes modulo $m$, then $\{a_1, a_2, \dots, a_m\}$ are called the complete set of residues modulo $m.$

We can make a ring from $\qr{m}$ by defining addition and multiplication operators.

Proposition 3

If $a \equiv_m c$ and $b \equiv_m d,$ then $a + b \equiv_m c + d$ and $ab \equiv_m cd.$

If $m | c - a$ and $m | d - b,$ then $m | (c - a) + (d - b) = (c + d) - (a + b).$ Thus $a + b \equiv_m c + d.$

Notice that $cd - ab = c(d - b) + b(c - a).$ Thus, $m | cd - ab$ and $ab \equiv_m cd.$

For $\overline{a}, \overline{b} \in \qr{m},$ let $\overline{a} + \overline{b} = \overline{a + b}$ and $\overline{a}\,\overline{b} = \overline{ab}.$ Assume that $\overline{c} = \overline{a}$ and $\overline{d} = \overline{b}.$ From propositions 2 and 3, we get that $\overline{a + b} = \overline{c + d}$ and $\overline{ab} = \overline{cd}.$ Then, these definitions depend on the congruence classes defined by $a$ and $b$, not directly on $a$ and $b.$ Finally, $\qr{m}$ becomes a ring with these definitions.

In arithmetic problems, sometimes it is convient to work with the ring $\qr{m}$ rather than using the congruence modulo $m$, and vice versa.

Previously, we’ve shown that $x^2 + 3x + 5$ has no integer solutions using the residues modulo $2.$ We can generalize our findings using what we now know about congruences.

If $a \equiv_m b,$ then $a^2 \equiv_m b^2, a^3 \equiv_m b^3,$ and more generally $a^n \equiv_m b^n.$ It then follows that for $p(x) \in \mathbb{Z}[ x ],$ $p(a) \equiv_m p(b).$ This all follows from proposition 3.

If we let $m = 2,$ then $a$ is congruent to $0$ or $1$ modulo $2$ and $p(a) \equiv_2 p(0)$ or $p(a) \equiv_2 p(1).$

If $p(x)$ is a polynomial with degree $n$ and coefficients from $a_0$ to $a_n,$ then $p(0) = a_n$ and $p(1) = \sum_{i=0}^{n} a_i.$ Then, if $p(x) \in \mathbb{Z}[ x ]$ and $p(0)$ and $p(1)$ both odd, then $p(x)$ does not have integer solutions.

The Congruence $ax \equiv_m b$§

This is the simplest congruence we can consider, we will develop criterion to test for the solvability of the congruence and a formula to determine the number of solutions should they exist.

Consider the polynomial $f(x_1, \dots x_n)$ in $n$ variables with integer coefficients, and the congruence $f(x_1, \dots, x_n) \equiv_m 0$. The congruence has a solution if there exists an $n$-tuple of integers $(a_1, \dots, a_n)$ such that $f(a_1, \dots, a_n) \equiv_m 0.$ Then, if there exists another $n$-tuple $(b_1, \dots, b_n)$ such that $b_i \equiv_m a_i$ for $i = 1, \dots, n,$ then it is clear that $f(b_1, \dots, b_n) \equiv_m 0.$ We then consider $(a_1, \dots, a_n)$ and $(b_1, \dots, b_n)$ to be equivalent. Then, the number of solutions to $f(x_1, \dots, x_n) \equiv_m 0$ is defined to be the number of solutions that are nonequivalent.

We can also look at this congruence from a different angle. The mapping from $\mathbb{Z} \to \qr{m}$ given by $a \to \overline{a}$ is a homomorphism. If $f(a_1, \dots, a_n) \equiv_m 0,$ then $\overline{f}(\overline(a_1), \dots, \overline(a_n)) = \overline{0}.$ The polynomial $\overline{f}(x_1, \dots, x_n) \in \qr{m}[x_1, \dots, x_n]$ is generated from $f$ by putting a bar over each coefficient of $f.$ Then, the equivalence class of solutions to $f = 0$ are in one-to-one correspondance to $\overline{f} = 0$ in the ring $\qr{m}.$

We let $d = (a, m) \gt 0, a’ = a/d$ and $m’ = m/d.$ Then $(a’, m’) = 1.$

Proposition 4

The congruence $ax \equiv_m b$ has solutions iff $d | b.$

  • If $d | b,$ then there are exactly $d$ solutions.
  • If $x_0$ is a solution, then the other solutions are given by $$ x_0 + m’, x_0 + 2m’, \dots, x_0 + (d - 1)m’. $$

If $x_0$ is a solution, then $\exists y_0 \in \mathbb{Z}, ax_0 - b = my_0.$ Thus $ax_0 - my_0 = b,$ we must have $d | b$ as $d | ax_0 - my_0.$

Conversely, sps. $d | b.$ By Lemma 4 from Unique Factorization there must exist integers $x_0’$ and $y_0’$ such that $ax_0’ + by_0’ = d.$ Letting $c = b/d$ and multiplying both sides of the equation by $c$ gives us $a(x_0’c) - m(y_0’c) = b.$ Let $x_0 = x_0’c.$ Then $ax_0 \equiv_m b.$ Therefore $ax \equiv_m b$ has a solution iff $d | b.$

Sps. $x_0$ and $x_1$ are solutions. $ax_0 \equiv_m b$ and $ax_1 \equiv_m b$ imply that $a(x_1 - x_0) \equiv_m 0.$ Thus $m | a(x_1 - x_0)$ and $m’ | a’(x_1 - x_0),$ implying $m’ | x_1 - x_0$ or $\exists k \in \mathbb{Z}, x_1 = km’.$ It is easily checked that any number with the form $x_0 + km’$ is a solution, and that $x_0, x_0 + m’, \dots x_0 + (d - 1)m’$ are nonequivalent. Let $x_1 = x_0 + km’$ be another solution. Then there exists $r, s \in \mathbb{Z}$ such that $k = rd + s$ and $0 \leq s \lt d.$ Thus $x_1 = x_0 + sm’ + rm$ and $x_1 \equiv_m x_0 + sm’.$

Corollary 1

If $a$ and $b$ coprime, then $ax \equiv_m$ has one and only one solution.

Clearly, $d = (a, b) = 1$ so $d | b$ and there exists only $1$ solution.

Corollary 2

For $p$ prime and $a \not\equiv_p 0,$ then $ax \equiv_p b$ has one and only one solution.

Follows directly from corollary 1.

In ring theoretic language, the congruence $ax \equiv_m b$ is equivalent to $\overline{a}x = \overline{b}$ over ring $\qr{m}.$

We may ask ourselves, what are the units of $\qr{m}?$

  • $\overline{a} \in \qr{m}$ is a unit iff $\overline{a}x = \overline{1}$ is solvable.

$ax \equiv_m 1$ is solvable iff $a$ and $m$ are coprime. Therefore, $\overline{a}$ is a unit iff $(a, m) = 1.$ It follows that there exists $\varphi(m)$ units in $\qr{m}.$

If $p$ prime and $\overline{a} \neq \overline{0} \in \qr{p},$ then $(a, p) = 1.$ Thus, every nonzero element of $\qr{p}$ is a unit, which shows that $\qr{p}$ is a field.

If $m$ composite, $m = m_1m_2,$ for $0 \lt m_1, m_2, \lt m.$ Then $\overline{m_1} \neq \overline{0}, \overline{m_2} \neq \overline{0}.$ However, $\overline{m_1}\,\overline{m_2} = \overline{m_1m_2} = \overline{m} = \overline{0}.$ Therefore $\qr{m}$ not a field.

In essence,

Corollary 3 (Euler's Theorem)

If $(a, m) = 1,$ then $a^{\varphi(m)} \equiv_m 1.$

The units in $\qr{m}$ form a group with order $\varphi(m).$ If $(a, m) = 1,$ $\overline{a}$ is a unit. Therefore $\overline{a}^{\varphi(m)} = \overline{1} \iff a^{\varphi(m)} \equiv_m 1.$

Corollary 4 (Fermat's Little Theorem)

If $p$ prime and $(p, a) = 1,$ then $a^{p - 1} \equiv_p 1.$

Because $(p, a) = 1,$ we get that $a^{\varphi(p)} \equiv_p 1.$ The result then follows as for $p$ prime, $\varphi(p) = p - 1.$

Generalization§

Many of these results can be carried over to other principal ideal domains. Congruence and residue classes can be generalized to an arbitrary commutative ring. For example, the first part of proposition 4, $ax \equiv_m b$ has a solution iff $d | b$ and the solution is unique iff $a$ and $m$ coprime is valid in any PID. The difference lies in that the number of solutions is not necessarily finite. Then, using this result we can show part of proposition 4 holds over any PID, i.e. if $R$ is a PID and $m \in R$ is nonzero or a unit, then $R/(m)$ is a field iff $m$ prime. Particularly, if $k$ is a field, then $k[ x ]/(f (x))$ is a field iff $f(x)$ irreductible.

Chinese Remainder Theorem§

When $m$ composite in a congruence, we can sometimes reduce the congruence modulo $m$ to a system of simpler congruences.

Lemma 1

If $a_1, \dots, a_\ell$ are all relatively prime to $m$, then so is $\prod_{i=1}^{\ell} a_i.$

$\overline{a_i} \in \qr{m}$ is a unit. So, $\overline{a_1}\,\overline{a_2}\dots\overline{a_\ell} = \overline{a_1a_2\dots a_\ell}.$ By proposition 4, we get that $\left(m, \prod_{i=1}^{\ell} a_i\right) = 1.$

Lemma 2

Sps. $a_1, \dots, a_\ell$ all divide $n$ and that $(a_i, a_j) = 1$ for $i \neq j.$ Then $\prod_{i=1}^{\ell} a_i$ divides $n.$

We will use induction on $t.$

If $t = 1,$ done. Sps. $t \gt 1$ and that the lemma holds for $t - 1.$ Then $\prod_{i=1}^{t - 1} a_i$ divides $n.$ By lemma 1, $a_t$ is coprime with $\prod_{i=1}^{t - 1} a_i.$ Thus, there exists $r, s \in \mathbb{Z}$ such that

$$ra_t + s\prod_{i=1}^{t - 1} a_i = 1.$$

We then multiply both sides by $n,$ and by inspection we see that the left-hand side is divisible by $\prod_{i=1}^{t} a_i$. The result then follows.

Theorem 1 (Chinese Remainder Theorem)

Sps. $m = \prod_{i=1}^{t} m_i$ and $(m_i, m_j) = 1$ for $i \neq j.$ Let $b_1, b_2, \dots, b_t \in \mathbb{Z}$ and consider the system of congruences,

$$ x \equiv b_1 \pmod{m_1}, x \equiv b_2 \pmod{m_2}, \dots, x \equiv b_t \pmod{m_t}. $$

Then, this system of congruences always has solutions and any two solutions differ by a multiple of $m.$

Let $n_i = m / m_i.$ By lemma 1, $(m_i, n_i) = 1.$ Thus there exists $r_i, s_i \in \mathbb{Z}$ such that $r_im_i + s_in_i = 1.$ Let $e_i = s_in_i.$ Then $e_i \equiv 1 \pmod{m_i}$ and $e_i \equiv 0 \pmod{m_j}$ for $i \neq j.$

Let $x_0 = \sum_{i = 1}^t b_ie_i.$ Then we have $x_0 \equiv b_ie_i \pmod{m_i}$, so $x_0 \equiv b_i \pmod{m_i}.$ Then, $x_0$ is a solution.

Sps. $x_1$ is another solution. Then $x_1 - x_0 \equiv 0 \pmod{m_i}$ for $i = 1, \dots, t.$ In other words, $m_1, m_2, \dots, m_t$ divide $x_1 - x_0.$ By lemma 2, $m$ divides $x_1 - x_0.$

Approaching CRT from Ring Theory§

If $R_1, R_2, \dots, R_n$ are rings, then let the direct sum of $R_i$ be $R_1 \oplus R_2 \oplus \dots \oplus R_n = S;$ it is defined to be the set of $n$-tuples $(r_1, r_2, \dots, r_n)$ with $r_i \in R_i.$

  • Let addition be defined by $(r_1, r_2, \dots, r_n) + (r_1’, r_2’, \dots, r_n’) = (r_1 + r_1’, r_2 + r_2’, \dots, r_n + r_n’).$
  • And multiplication by $(r_1, r_2, \dots, r_n) \cdot (r_1’, r_2’, \dots, r_n’) = (r_1 r_1’, r_2 r_2’, \dots, r_n r_n’).$
  • The zero element is $(0, 0, \dots, 0).$
  • The identity is $(1, 1, \dots, 1).$
  • $u \in S$ is a unit iff $\exists v \in S$ such that $uv = 1.$

If $u = (u_1, \dots, u_n)$ and $v = (v_1, \dots, v_n),$ then $uv = 1$ implies that $u_iv_i = 1$ for $i = 1, \dots, n.$ Thus $u_i$ is a unit for each $i.$ Conversely, if $u_i$ is a unit for each $i,$ then $u = (u_1, u_2, \dots, u_n)$ is a unit. The group of units in $R$ is denoted by $U(R).$ Then, $U(R_1) \times U(R_2) \times \dots \times U(R_n)$ is the set of $n$-tuples $(u_1, u_2, \dots, u_n),$ where $u_i \in R_i.$ This forms a group under component-wise multiplication.

In essence, we have shown

Proposition 5

If $S = R_1 \oplus R_2 \oplus \dots \oplus R_n,$ then $U(S) = U(R_1) \times U(R_2) \times \dots \times U(R_n).$

Let $m_1, m_2, \dots, m_t$ be pairwise relatively prime integers. Then $\psi_i$ denotes the natural homomorphism $\mathbb{Z} \to \qr{m_i}.$ Then, we define the map $\psi: \mathbb{Z} \to \qr{m_1} \oplus \qr{m_2} \oplus \dots \oplus \qr{m_t}$ for all $n \in \mathbb{Z}$,

$$ \psi(n) = (\psi_1(n), \psi_2(n), \dots, \psi_t(n)). $$

It is easy to see that $\psi$ is a ring homomorphism.

$(\overline{b_1}, \overline{b_2}, \dots, \overline{b_t}) = \psi(n)$ iff $\psi_i(n) = \overline{b_i}$ for all $i = 1, \dots, t.$ That is, $n \equiv b_i \pmod{m_i}$ for all $i = 1, \dots, t.$ The CRT assures us that there always exists an $n$ that satisfies this relation, thus $\psi$ is onto.

$\psi(n) = 0$ iff $n \equiv 0 \pmod{m_i}$ for all $i = 1, \dots, t,$ iff $n$ is divisible by $m = m_1m_2\dots m_t.$ This follows from lemma 2. Therefore, the kernel of $\psi$ is the ideal $m\mathbb{Z}.$

Then,

Theorem 1'

The map $\psi$ induces an isomorphism between $\qr{m}$ and $\qr{m_1} \oplus \qr{m_2} \oplus \dots \oplus \qr{m_t}.$

Corollary 5

$\qu{m}) \approx \qu{m_1} \times \qu{m_2} \times \dots \times \qu{m_t}$

Follows immediately from theorem 1’ and proposition 5.

Both sides of the isomorphism in corollary 5 are finite groups. The left-hand side has order $\varphi(m)$ and the right-hand side $\prod_{i=1}^{t} \varphi(m_i).$ Thus, $\varphi(m) = \prod_{i=1}^{t} \varphi(m_i).$

Return to $\mathbb{Z}$§

Let $m \in \mathbb{Z}$, and consider the prime decomposition $m = \decomp{p}{a}{t}.$ We have that $\varphi(m) = \varphi(p_1^{a_1})\varphi(p_2^{a_2})\dots\varphi(p_t^{a_t}).$ For a prime power $p^a, \varphi\left(p^a\right) = p^a - p^{a-1}$ because the numbers less than $p^a$ and prime to $p^a$ are prime to $p.$ Since $p^a/p = p^{a-1}$ numbers less than $p^a$ are divisible by $p$, $p^a-p^{a-1}$ numbers are prime to $p.$ Then, $p^a - p^{a-1} = p^a(1 - 1/p)$ which gives us $\varphi(m) = m \prod(1 - 1/p)$, a result that we found in the previous chapter.

Summary§

The usefulness of congruence cannot be understated when working with questions in arithmetic. With congruence, we inspected the ring $\qr{m}$ and its unit group $U(\qr{m}).$ In understanding the structure of these objects and the CRT, we found the isomorphisms

$$ \begin{align*} \qr{m} &\approx \qr{p_1^{a_1}} \oplus \qr{p_2^{a_2}} \oplus \dots \oplus \qr{p_t^{a_t}},\\ \qu{m} &\approx \qu{p_1^{a_1}} \times \qu{p_2^{a_2}} \times \dots \times \qu{p_t^{a_t}}. \end{align*} $$

There is more to learn about $\qr{m}$ and $U(\qr{m})$ for $m$ a prime power.