Linear Equations Modulo $ n$

In this section, we are concerned with how to decide whether or not a linear equation of the form $ ax\equiv b \pmod{n}$ has a solution modulo $ n$ . Algorithms for computing solutions to $ ax\equiv b \pmod{n}$ are the topic of Section 2.3.

First we prove a proposition that gives a criterion under which one can cancel a quantity from both sides of a congruence.

Proposition 2.1 (Cancellation)   If $ \gcd(c,n)=1$ and

$\displaystyle ac\equiv bc\pmod{n},
$

then $ a\equiv b\pmod{n}$ .

Proof. By definition

$\displaystyle n \mid ac - bc = (a-b)c.
$

Since $ \gcd(n,c)=1$ , it follows from Theorem 1.1.6 that $ n\mid a-b$ , so

$\displaystyle a \equiv b\pmod{n},
$

as claimed. $ \qedsymbol$

When $ a$ has a multiplicative inverse $ a'$ in $ \mathbb{Z}/n\mathbb{Z}{}$ (i.e., $ aa'\equiv 1\pmod{n}$ ) then the equation $ ax\equiv b \pmod{n}$ has a unique solution $ x\equiv a'b\pmod{n}$ modulo $ n$ . Thus, it is of interest to determine the units in $ \mathbb{Z}/n\mathbb{Z}{}$ , i.e., the elements which have a multiplicative inverse.

We will use complete sets of residues to prove that the units in $ \mathbb{Z}/n\mathbb{Z}{}$ are exactly the  $ a\in\mathbb{Z}/n\mathbb{Z}{}$ such that $ \gcd(\tilde{a},n)=1$ for any lift $ \tilde{a}$ of $ a$ to  $ \mathbb {Z}$ (it doesn't matter which lift).

Definition 2.1 (Complete Set of Residues)   We call a subset $ R\subset\mathbb{Z}$ of size $ n$ whose reductions modulo $ n$ are pairwise distinct a complete set of residues modulo $ n$ . In other words, a complete set of residues is a choice of representative for each equivalence class in $ \mathbb{Z}/n\mathbb{Z}{}$ .

For example,

$\displaystyle R=\{0,1,2,\ldots,n-1\}
$

is a complete set of residues modulo $ n$ . When $ n=5$ , $ R = \{0,1,-1,2,-2\}$ is a complete set of residues.

Lemma 2.1   If $ R$ is a complete set of residues modulo $ n$ and $ a\in\mathbb{Z}$ with $ \gcd(a,n)=1$ , then $ aR = \{ax : x \in R\}$ is also a complete set of residues modulo $ n$ .

Proof. If $ ax\equiv ax'\pmod{n}$ with $ x, x'\in R$ , then Proposition 2.1.9 implies that $ x\equiv {}x'\pmod{n}$ . Because $ R$ is a complete set of residues, this implies that $ x=x'$ . Thus the elements of $ aR$ have distinct reductions modulo $ n$ . It follows, since $ \char93 aR=n$ , that $ aR$ is a complete set of residues modulo $ n$ . $ \qedsymbol$

Proposition 2.1 (Units)   If $ \gcd(a,n)=1$ , then the equation $ ax\equiv b \pmod{n}$ has a solution, and that solution is unique modulo $ n$ .

Proof. Let $ R$ be a complete set of residues modulo $ n$ , so there is a unique element of $ R$ that is congruent to $ b$ modulo $ n$ . By Lemma 2.1.11, $ aR$ is also a complete set of residues modulo $ n$ , so there is a unique element $ ax\in aR$ that is congruent to $ b$ modulo $ n$ , and we have $ ax\equiv b \pmod{n}$ . $ \qedsymbol$

Algebraically, this proposition asserts that if $ \gcd(a,n)=1$ , then the map $ \mathbb{Z}/n\mathbb{Z}{}\rightarrow \mathbb{Z}/n\mathbb{Z}{}$ given by left multiplication by $ a$ is a bijection.

Example 2.1   Consider the equation $ 2x\equiv 3\pmod{7}$ , and the complete set $ R = \{0,1,2,3,4,5,6\}$ of coset representatives. We have

$\displaystyle 2R = \{0,2,4,6,8\equiv 1, 10\equiv 3, 12\equiv 5\},
$

so $ 2\cdot 5\equiv 3\pmod{7}$ .

When $ \gcd(a,n)\neq 1$ , then the equation $ ax\equiv b \pmod{n}$ may or may not have a solution. For example, $ 2x\equiv 1\pmod{4}$ has no solution, but $ 2x\equiv 2\pmod{4}$ does, and in fact it has more than one mod $ 4$ ($ x=1$ and $ x=3$ ). Generalizing Proposition 2.1.12, we obtain the following more general criterion for solvability.

Proposition 2.1 (Solvability)   The equation $ ax\equiv b \pmod{n}$ has a solution if and only if $ \gcd(a,n)$ divides $ b$ .

Proof. Let $ g=\gcd(a,n)$ . If there is a solution $ x$ to the equation $ ax\equiv b \pmod{n}$ , then $ n\mid (ax-b)$ . Since $ g\mid n$ and $ g\mid
a$ , it follows that $ g\mid b$ .

Conversely, suppose that $ g\mid b$ . Then $ n\mid (ax-b)$ if and only if

$\displaystyle \frac{n}{g} \mid \left(\frac{a}{g} x - \frac{b}{g}\right). $

Thus $ ax\equiv b \pmod{n}$ has a solution if and only if $ \frac{a}{g}x
\equiv \frac{b}{g}\pmod{\frac{n}{g}}$ has a solution. Since $ \gcd(a/g, n/g)=1$ , Proposition 2.1.12 implies this latter equation does have a solution. $ \qedsymbol$

In Chapter 4 we will study quadratic reciprocity, which gives a nice criterion for whether or not a quadratic equation modulo $ n$ has a solution.

William 2007-06-01