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

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

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

Proof. By definition

$$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

$$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,

$$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

$$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

$$\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.