2.2: Linear Congruences

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

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.

We start with a definition:

Definition: Linear Congruence in One Variable

Given constants \(a,b\in\ZZ\) and \(n\in\ZZ\), a congruence of the form \(ax\equiv b\pmod n\) where \(x\in\ZZ\) is unknown is called a linear congruence in one variable.

If a linear congruence has one solution, then it has infinitely many:

Theorem \(\PageIndex{1}\)

Given constants \(a,b\in\ZZ\), \(n\in\ZZ\), and a solution \(x\in\ZZ\) to the linear congruence \(ax\equiv b\pmod n\), any other \(x^\prime\in\ZZ\) satisfying \(x^\prime\equiv x\pmod n\) is also a solution of the same congruence.

[Note: in the early history of number theory, before Gauss, one talked about:

Definition: Diophantine Equation

An algebraic equation whose constants and variables are all integers is called a Diophantine equation.

Then, the modern linear congruence \(ax\equiv b\pmod n\), for \(a,b\in\ZZ\) and \(n\in\NN\) is equivalent to the linear Diophantine equation \(ax-ny=b\) in the two unknowns \(x\) and \(y\).]

The following gives a fairly complete characterization of solutions of linear congruences:

Theorem \(\PageIndex{2}\)

Let \(a,b\in\ZZ\) and \(n\in\NN\) and consider the linear congruence \[ax\equiv b\pmod n\ .\] Setting \(d=\gcd(a,n)\), we have

1. If \(d\nmid b\), then the congruence has no solutions.
2. If \(d\mid b\), then the congruence has exactly \(d\) solutions which are distinct modulo \(n\).

Proof

For Part 1, we prove its contrapositive. So assume the congruence has solutions, meaning \(\exists x,k\in\ZZ\) such that \(ax-b=kn\), or \(ax-kn=b\). But since \(d=\gcd(a,n)\) is a common divisor of \(a\) and \(n\), it divides the linear combination \(ax-kn=b\). Hence \(d\mid b\).

Now for Part 2, assume \(d\mid b\), so \(\exists k\in\ZZ\) such that \(kd=b\). But from Theorem 1.5.3 we know \(\exists p,q\in\ZZ\) such that \(d=pa+qn\). This means that \(kpa+kqn=kd=b\) or, rearranging, \(a(kp)-b=(-kq)n\). Hence \(n\mid a(kp)=b\), i.e., \(a(kp)\equiv b\pmod n\) and thus \(x=kp\) is one solution to the linear congruence \(ax\equiv b\pmod n\).

Finally, let us prove that there are the correct number of solutions, mod \(n\), of the congruence equation. We have just seen that there is at least one \(x\in\ZZ\) satisfying \(ax\equiv b\pmod n\). Let \(y\in\ZZ\) be any other solution. Then \(ax\equiv b\equiv ay\pmod n\). By part (2) of Theorem 2.1.3, \(x\equiv y\pmod{n/d}\), or \(\delta = y-x\equiv0\pmod{n/d}\). Now by Theorem 2.1.4, there are exactly \(d\) possibilities, modulo \(n\), for this \(\delta\). Thus there are \(d\) solutions of \(ax\equiv b\pmod n\) of the form \(x+\delta\).

Note

Notice that if \(a\in\ZZ\) and \(n\in\NN\) are relatively prime, then \(\forall b\in\ZZ\) there is a unique solution modulo \(n\) to the equation \(ax\equiv b\pmod n\).

Example \(\PageIndex{1}\)

Let us find all the solutions of the congruence \(3x\equiv 12\pmod6\). Notice that \(\gcd(3,6)=3\) and \(3\mid 12\). Thus there are three incongruent solutions modulo \(6\). Using the Euclidean Algorithm to find the solution of the equation \(3x-6y=12\) we get a solution \(x_0=6\). Thus the three incongruent (modulo \(6\)) solutions are given by \(x_1=6\pmod6\), \(x_1=6+2=2\pmod6\) and \(x_2=6+4=4\pmod6\).

As we mentioned in the note above, the congruence \(ax\equiv b\pmod n\) for \(a,b\in\ZZ\) and \(n\in\NN\) has a unique (modulo \(n\)) solution if \(\gcd(a,n)=1\). This will allow us to talk about modular inverses.

Given \(a\in\ZZ\) and \(n\in\NN\), a solution to the congruence \(ax\equiv 1\pmod n\) for \((a,n)=1\) is called the inverse of \(a\) modulo n. We denote such an inverse by \(a^{-1}\), with the \(n\) to be understood from context.

Stating formally what was just recalled from the above note, we have:

Corollary \(\PageIndex{1}\)

Given \(a\in\ZZ\) and \(n\in\NN\) which are relatively prime, the modular inverse \(a^{-1}\) exists and is unique modulo \(n\).

Example \(\PageIndex{2}\)

The modular inverse \(7^{-1}\)of \(7\) modulo \(48\) is \(7\). Notice that a solution of \(7x\equiv 1\pmod{48}\) is \(x\equiv 7\pmod{48}\).

Exercise \(\PageIndex{1}\)

1. Find all solutions of \(3x\equiv 6\pmod9\).
2. Find all solutions of \(3x\equiv 2\pmod7\).
3. Find inverses modulo \(13\) of \(2\) and of \(11\).
4. Given \(a\in\ZZ\) and \(n\in\NN\), show that if \(a^{-1}\) is the inverse of \(a\) modulo \(n\) and \(b^{-1}\) is the inverse of \(b\) modulo \(n\), then \(a^{-1}b^{-1}\) is the inverse of \(ab\) modulo \(n\).