2: Congruences

Last updated
Save as PDF

Page ID: 28631

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

A congruence is nothing more than a statement about divisibility. The theory of congruences was introduced by Carl Friedrich Gauss, in his monumental Disquisitiones Arithmeticae (published in \(1801\), when he was \(24\); a translation is [Gau86]). We start by introducing congruences and their properties. We then present solutions to linear congruences which will serve as an introduction to the Chinese Remainder Theorem that follows.

2.1: Introduction to Congruences
As we mentioned in the introduction, the theory of congruences was developed by Gauss at the beginning of the nineteenth century.
2.2: Linear Congruences
Because congruence is analogous to equality, it is natural to ask about the analogues of linear equations, the simplest equations one can solve in algebra, but using congruence rather than equality. In this section, we discuss linear congruences of one variable and their solutions.
2.3: The Chinese Remainder Theorem
In this section, we discuss solutions of systems of congruences having different moduli. An example of this kind of systems is the following: find a number that leaves a remainder of 1 when divided by 2, a remainder of 2 when divided by three and a remainder of 3 when divided by 5. We shall see that there is a systematic way of solving this kind of system.
2.4: Another Way to Work with Congruences - Equivalence Classes
In this section, we shall consider another way to work with congruences.
2.5: Euler's ϕ Function
In this section, we will discuss Euler's ϕ Function. One quite surprising fact about Euler’s totient function is that it is multiplicative, at least for relatively prime numbers

Thumbnail: Sun-tzu's original formulation of the the Chinese remainder theorem: \(x ≡ 2 (\text{mod } 3) ≡ 3 (\text{mod } 5)\) with the solution \(x = 23 + 105k\), with \(k\) an integer. (CC BY-SA 4.0; Cmglee via Wikipedia)