Linear Congruences

Linear Congruences#

KaTeX $\renewcommand{\c}[1]{\textcolor{#1}}$

Linear Congruence#

$Definition$ [Humphreys & Prest pp. 50]

A linear congruence is an equation of the form

\[ ax \equiv b \mod n \]

where $x$ is an integer variable; or an equation of the form

\[ [a]_n x = [b]_n \]

where $x$ is a congruence class.

This equation may have no solution; exactly one solution; or more than one solution.

If $k$ is a solution for $x$ in $ax \equiv b \mod n$ then

$n \mid ak - b \iff ak - b = ns \iff ak + nt = b$ for some integer $s = -t$

and $t$ can be computed from known $a, k, n, b$.

Therefore, solving $ak + nt = b$ for $k, t$ is equivalent to solving $ax \equiv b \mod n$ for $x$.

Brahmagupta gave the criterion for solvability of and the general solution of

\[ ak + nt = b \]

where $a, n, b$ are fixed integers and $k, t$ are integer unknowns.

An equation of the form $ak + nt = b$ is indeterminate in the sense that since it is just one equation with two unknowns it has infinitely many solutions if it has any at all and those solutions form themselves into complete congruence classes.

Solutions to linear congruences#

How do we distinguish between linear congruences that have no solution, exactly one solution, or more than one solution?

How do we find all solutions to a linear congruence if they exist?

$Theorem$ [Humphreys & Prest 1.5.1 pp. 50]

The linear congruence $ax \equiv b \mod n$ has solutions iff the greatest common divisor $d$ of $a$ and $n$ divides $b$.

If $d$ divides $b$ then there are $d$ solutions up to congruence modulo $n$ and these solutions are all congruent modulo $\frac{n}{d}$.

$Proof$ [Humphreys & Prest pp. 50-51]

If the linear congruence $ax \equiv b \mod n$ has solutions then the greatest common divisor $d$ of $a$ and $n$ divides $b$.

Let $c$ be a solution to $ax \equiv b \mod n$.

$ac \equiv b \mod n \iff n \mid ac - b \iff ac - b = nk \iff b = ac - nk$ for some integer $k$.

$gcd(a, n) = d$

$d \mid a$

$d \mid n$

$\therefore d \mid b = ac - nk$

If the greatest common divisor $d$ of $a$ and $n$ divides $b$ then the linear congruence $ax \equiv b \mod n$ has solutions.

Let $d \mid b \iff b = de$ for some integer $e$.

Write $d$ as a linear combination of $a$ and $n$: $d = ak + nt \iff de = b = ake + nte \iff ake - b = n(-te) \iff a(ke) \equiv b \mod n$.

Let $c$ be a solution to $ax \equiv b \mod n$.

$ac \equiv b \mod n \iff n \mid ac - b \iff ac - b = nk \iff ac = b + nk$ for some integer $k$.

Since $d \mid b$ we may divide this equation by $d$ to get the equation in integers.

$(\frac{a}{d}) c = \frac{b}{d} + (\frac{n}{d}) k \iff (\frac{a}{d}) c \equiv \frac{b}{d} \mod (\frac{n}{d})$

Every solution of the original congruence $ax \equiv b \mod n$ is also a solution of the congruence $(\frac{a}{d}) x \equiv \frac{b}{d} \mod (\frac{n}{d})$.

Conversely every solution to this second congruence is also a solution to the original one. So the solution is really a congruence class modulo $\frac{n}{d}$. Such a congruence class splits into $d$ distinct congruence classes modulo $n$. Namely if $c$ is a solution then the congruence classes of

\[ c, c + \left( \frac{n}{d} \right), c + 2 \left( \frac{n}{d} \right), c + 3 \left( \frac{n}{d} \right), \dots, c + (d - 1) \left( \frac{n}{d} \right) \]

are distinct solutions modulo $n$ and are all the solutions modulo $n$.

$\blacksquare$

A method for solving linear congruences#

To find all solutions of the linear congruence

\[ ax \equiv b \mod n \]

Calculate $d = gcd(a, n)$.
Test whether $d$ divides $b$.

a. If $d$ does not divide $b$ then there is no solution.

b. If $d$ divides $b$ then there are $d$ solutions modulo $n$. To find the solutions in (b) divide the congruence throughout by $d$ to get $(\frac{a}{d}) x \equiv (\frac{b}{d}) \mod (\frac{n}{d})$. Notice that since $gcd(\frac{a}{d}, \frac{n}{d}) = 1$ this congruence will have a unique solution.
Calculate the inverse $[e]_{\frac{n}{d}}$ of $[\frac{a}{d}]_{\frac{n}{d}}$ (either by inspection or by the matrix method).
Multiply to get $[x]_{\frac{n}{d}} = [e]_{\frac{n}{d}} [\frac{b}{d}]_{\frac{n}{d}}$ and calculate a solution $c$ for $x$.
The solutions to the original congruence will be the classes modulo $n$ of

\[ c, c + \left( \frac{n}{d} \right), c + 2 \left( \frac{n}{d} \right), c + 3 \left( \frac{n}{d} \right), \dots, c + (d - 1) \left( \frac{n}{d} \right) \]

Some examples of solving linear congruences#

Solve the linear congruence $6x \equiv 5 \mod 17$.

$gcd(6, 17) = 1$
There is $1$ solution since $1 \mid 5$.
$6x \equiv 5 \mod 17 \iff \frac{6}{1}x \equiv \frac{5}{1} \mod \frac{17}{1}$
$6x \equiv 1 \mod 17 \iff 17 \mid 6x - 1 \iff 6x - 1 = 17k \iff x = \frac{17(k = 1) + 1}{6} = 3$
$6x \equiv 5 \mod 17 \iff 6 \times 3 \times x \equiv x \equiv 5 \times 3 = 15 \mod 17$
$[15]_{17}$

Solve the linear congruence $6x \equiv 5 \mod 15$.

$gcd(6, 15) = 3$
There is no solution since $3 \nmid 5$.

Solve the linear congruence $6x \equiv 9 \mod 15$.

$gcd(6, 15) = 3$
There are $3$ solutions since $3 \mid 9$.
$6x \equiv 9 \mod 15 \iff 2x \equiv 3 \mod 5$
$2x \equiv 1 \mod 5 \iff 5 \mid 2x - 1 \iff 2x - 1 = 5k \iff x = \frac{5(k = 1) + 1}{2} = 3$
$2x \equiv 3 \mod 5 \iff 2 \times 3 \times x \equiv x \equiv 3 \times 3 = 9 \equiv 4 \mod 5$
$[4]_{15}, [9]_{15}, [14]_{15}$

Solve the linear congruence $432x \equiv 12 \mod 546$.

$gcd(432, 546) = 6$
There are $6$ solutions since $6 \mid 12$.
$432x \equiv 12 \mod 546 \iff 72x \equiv 2 \mod 91$
$72x \equiv 1 \mod 91 \iff 91 \mid 72x - 1 \iff 72x - 1 = 91k \iff x = \frac{91(k = 53) + 1}{72} = 67$
$72x \equiv 2 \mod 91 \iff 72 \times 67 \times x \equiv x \equiv 2 \times 67 = 134 \equiv 43 \mod 91$
$[43]_{546}, [134]_{546}, [225]_{546}, [316]_{546}, [407]_{546}, [498]_{546}$

$ \begin{aligned} 546 &=& 432 &\times 1 + 114 \\ 432 &=& 114 &\times 3 + 90 \\ 114 &=& 90 &\times 1 + 24 \\ 90 &=& 24 &\times 3 + 18 \\ 24 &=& 18 &\times 1 + 6 \\ 18 &=& \c{green}{6} &\times 3 + 0 \\ \end{aligned} $

$ \begin{aligned} 432 &= 2^4 \times 3^2 \\ 546 &= 2^1 \times 3^1 \times 7 \times 13 \\ gcd(432, 546) &= \c{green}{2^1 \times 3^1} \\ \end{aligned} $

$ \left( \begin{array}{cc|c} 1 & 0 & 546 \\ 0 & 1 & 432 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 1 & -1 & 114 \\ 0 & 1 & 432 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 1 & -1 & 114 \\ -3 & 4 & 90 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 4 & -5 & 24 \\ -3 & 4 & 90 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 4 & -5 & 24 \\ -15 & 19 & 18 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 19 & -24 & 6 \\ -15 & 19 & 18 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 19 & -24 & 6 \\ -72 & 91 & 0 \\ \end{array} \right) $

$19 \times 546 + (-24) \times 432 = 6$

$ \left( \begin{array}{cc|c} 1 & 0 & 91 \\ 0 & 1 & 72 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 1 & -1 & 19 \\ 0 & 1 & 72 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 1 & -1 & 19 \\ -3 & 4 & 15 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 4 & -5 & 4 \\ -3 & 4 & 15 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 4 & -5 & 4 \\ -15 & 19 & 3 \\ \end{array} \right) \underset{}{\to} \left( \begin{array}{cc|c} 19 & -24 & 1 \\ -15 & 19 & 3 \\ \end{array} \right) $

$19 \times 91 + (-24) \times 72 = 1 \iff (-24) \times 72 \equiv 1 \mod 91$

print(19*546 + (-24)*432)
print(19* 91 + (-24)* 72)

6
1

Solving systems of linear congruences#

Is there an integer whose remainder is $3$ when divided by $7$ and whose remainder is $6$ when divided by $25$? If so, how does one find it?

In other words, is there an integer $x$ that satisfies the following system of linear congruences?

\[\begin{split} \begin{align*} x &\equiv 3 \mod 7 \\ x &\equiv 6 \mod 25 \\ \end{align*} \end{split}\]

Chinese Remainder Theorem#

$Theorem$ [Humphreys & Prest 1.5.2 pp. 54]

Let $m \ge 2$ and $n \ge 2$ be relatively prime integers and let $a, b$ be integers.

There is a simultaneous solution to the system of linear congruences

\[\begin{split} \begin{align*} x &\equiv a \mod m \\ x &\equiv b \mod n \\ \end{align*} \end{split}\]

The solution is unique up to congruence modulo $mn$.

$Proof$ [Humphreys & Prest pp. 54-55]

There are integers $k, t$ s.t. $mk + nt = 1$ since $m, n$ are relatively prime.

$c = bmk + ant$ is a simultaneous solution to the system of linear congruences.

$c - ant = m(bk) \iff c \equiv ant \mod m$
$nt - 1 = m(-k) \iff 1 \equiv nt \mod m$
$c \equiv a \times nt \equiv a \times 1 \equiv a \mod m$

$c - bmk = n(at) \iff c \equiv bmk \mod n$
$mk - 1 = n(-t) \iff 1 \equiv mk \mod n$
$c \equiv b \times mk \equiv b \times 1 \equiv b \mod m$

Let $c, d$ be solutions to the system of linear congruences.

$m \mid c - d \iff c - d \equiv a - a \equiv 0 \mod m$ since $c \equiv a \mod m$ and $d \equiv a \mod m$
$n \mid c - d \iff c - d \equiv b - b \equiv 0 \mod n$ since $c \equiv b \mod n$ and $d \equiv b \mod n$
$mn \mid c - d$ since $m, n$ are relatively prime and so $c, d$ lie in the same congruence class modulo $mn$.

Let $c$ be a solution to the system of linear congruences and let $d \equiv c \mod mn$.

$d - c = kmn \iff d = c + kmn$

$\blacksquare$

$Example$ [Humphreys & Prest pp. 55-56]

$ \begin{aligned} x &\equiv 3 \mod & 7 \\ x &\equiv 6 \mod &25 \\ \end{aligned} $

First method

Express the relative primes $m$ and $n$ as a linear combination equal to unity: $7 \times (-7) + 25 \times 2 = 1$
$6 \times 7 \times (-7) + 3 \times 25 \times 2 = -144 \equiv 31 \mod 175$
$[31]_{175}$

Second method

Take the first congruence and solve for $x$: $x \equiv 3 \mod 7 \iff x - 3 = 7k \iff x = 7k + 3$
Substitute the result into the second congruence: $7k + 3 \equiv 6 \mod 25 \iff 7k \equiv 3 \mod 25$
Find the inverse of $7 \mod 25$: $7k \equiv 1 \mod 25 \iff 7k - 1 = 25t \iff k = \frac{25(t = 5) + 1}{7} = 18$
$18 \times 7 \times k \equiv k \equiv 18 \times 3 = 54 \equiv 4 \mod 25$
$k \equiv 4 \mod 25 \iff k - 4 = 25r \iff k = 4 + 25r$
$x = 3 + 7(4 + 25r) = 31 + 175r \iff x \equiv 31 \mod 175 \iff [x]_{175} = [31]_{175}$

$Example$ [Humphreys & Prest pp. 56-57]

Is there an integer whose remainder is $2$ when divided by $7$; $0$ when divided by $9$; and $6$ when doubled and then divided by $8$?

Solve the system of linear congruences.

$ \begin{aligned} x &\equiv 2 \mod 7 \\ x &\equiv 0 \mod 9 \\ 2x &\equiv 6 \mod 8 \\ \end {aligned} $

$2x \equiv 6 \mod 8 \iff 8 \mid 2x - 6 \iff 2x - 6 = 8k \iff x = 4k + 3 \iff x - 3 = 4k \iff x \equiv 3 \mod 4$

The system of linear congruences becomes

$ \begin{aligned} x &\equiv 2 \mod 7 \\ x &\equiv 0 \mod 9 \\ x &\equiv 3 \mod 4 \\ \end {aligned} $

The moduli are pairwise relative primes.

$gcd(7, 9) = 1 = gcd(7, 4) = gcd(9, 4)$

$ \left ( \begin{array}{cc|c} 1 & 0 & 7 \\ 0 & 1 & 9 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & 0 & 7 \\ -1 & 1 & 2 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 4 & -3 & 1 \\ -1 & 1 & 2 \\ \end {array} \right) $

$\underset{b}{0} \times \underset{m}{7} \times \underset{k}{4} + \underset{a}{2} \times \underset{n}{9} \times \underset{t}{(-3)} = \underset{c}{-54} \equiv 9 \mod \underset{m}{7} \times \underset{n}{9} = 63$

The system of linear congruences becomes

$ \begin{aligned} x &\equiv 9 \mod 63 \\ x &\equiv 3 \mod 4 \\ \end {aligned} $

$ \left ( \begin{array}{cc|c} 1 & 0 & 63 \\ 0 & 1 & 4 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -15 & 3 \\ 0 & 1 & 4 \\ \end {array} \right) \to \left ( \begin{array}{cc|c} 1 & -15 & 3 \\ -1 & 16 & 1 \\ \end {array} \right) $

$\underset{b}{3} \times \underset{m}{63} \times \underset{k}{(-1)} + \underset{a}{9} \times \underset{n}{4} \times \underset{t}{16} = \underset{c}{387} \equiv 135 \mod \underset{m}{63} \times \underset{n}{4} = 252$

$[135]_{252}$

for c in [135, 135 + 252, 135 + 2*252]:
  print(    c % 7)
  print(    c % 9)
  print(2 * c % 8)

Nonlinear congruences#

$Example$ [Humphreys & Prest pp. 57-58]

Consider the quadratic equation $$x^2 + 1 \equiv 0 \mod n$$

The existence and number of solutions depends on $n$.

$x^2 + 1 \equiv 0 \mod 2$

Solutions: $[1]_2$

$ \begin{aligned} 0^2 + 1 &=& 1 & &\not\equiv&& 0 \mod 2 \\ 1^2 + 1 &=& 2 & & \equiv&& 0 \mod 2 \\ \end {aligned} $

$x^2 + 1 \equiv 0 \mod 3$

$ \begin{aligned} 0^2 + 1 &=& 1 & &\not\equiv&& 0 \mod 3 \\ 1^2 + 1 &=& 2 & &\not\equiv&& 0 \mod 3 \\ 2^2 + 1 &=& 5 &\equiv 2 &\not\equiv&& 0 \mod 3 \\ \end {aligned} $

$x^2 + 1 \equiv 0 \mod 4$

$ \begin{aligned} 0^2 + 1 &=& 1 & &\not\equiv&& 0 \mod 4 \\ 1^2 + 1 &=& 2 & &\not\equiv&& 0 \mod 4 \\ 2^2 + 1 &=& 5 &\equiv 1 &\not\equiv&& 0 \mod 4 \\ 3^2 + 1 &=& 10 &\equiv 2 &\not\equiv&& 0 \mod 4 \\ \end {aligned} $

$x^2 + 1 \equiv 0 \mod 5$

Solutions: $[2]_5, [3]_5$

$ \begin{aligned} 0^2 + 1 &=& 1 & &\not\equiv&& 0 \mod 5 \\ 1^2 + 1 &=& 2 & &\not\equiv&& 0 \mod 5 \\ 2^2 + 1 &=& 5 & & \equiv&& 0 \mod 5 \\ 3^2 + 1 &=& 10 & & \equiv&& 0 \mod 5 \\ 4^2 + 1 &=& 17 &\equiv 2 &\not\equiv&& 0 \mod 5 \\ \end {aligned} $

$x^2 + 1 \equiv 0 \mod 65$

Solutions: $[8]_{65}, [-8]_{65}, [18]_{65}, [-18]_{65}$

$ \begin{aligned} 0 ^2 + 1 &=& 1 & &\not\equiv&& 0 \mod 65 \\ 1 ^2 + 1 &=& 2 & &\not\equiv&& 0 \mod 65 \\ 2 ^2 + 1 &=& 5 & &\not\equiv&& 0 \mod 65 \\ 3 ^2 + 1 &=& 10 & &\not\equiv&& 0 \mod 65 \\ 4 ^2 + 1 &=& 17 & &\not\equiv&& 0 \mod 65 \\ 5 ^2 + 1 &=& 26 & &\not\equiv&& 0 \mod 65 \\ 6 ^2 + 1 &=& 37 & &\not\equiv&& 0 \mod 65 \\ 7 ^2 + 1 &=& 50 & &\not\equiv&& 0 \mod 65 \\ 8 ^2 + 1 &=& 65 & & \equiv&& 0 \mod 65 \\ (-8)^2 + 1 &=& 17 & & \equiv&& 0 \mod 65 \\ \vdots \end {aligned} $

$x^2 + 1 \equiv (x + 8)(x - 8) = x^2 - 64 \mod 65$

$x^2 + 1 \equiv (x + 18)(x - 18) = x^2 - 324 \mod 65 \iff x^2 \equiv -325 \mod 65$

print(( 8**2 + 1) % 65)
print((18**2 + 1) % 65)
print((47**2 + 1) % 65)
print((57**2 + 1) % 65)

$Example$ [Humphreys & Prest pp. 58]

Consider the polynomial $$x^3 - x^2 + x + 1$$

Does it have any integer roots?

Suppose that it had an integer root $k$. Then we would have $$k^3 - k^2 + k + 1 = 0$$

Let $n$ be an integer greater than $1$ and reduce this equation modulo $n$ to obtain $$[k]_n^3 - [k]_n^2 + [k]_n + [1]_n = [0]_n$$

The polynomial $X^3 - X^2 + X + [1]_n$ with coefficients from $\mathbb{Z}_n$ has a root in $\mathbb{Z}_n$. This would be true for every $n$.

In other words, if the equation reduced modulo $n$ has no roots modulo $n$ for at least one $n$, then the original equation has no integer roots.

$n = 2$

Reduce the equation $x^3 - x^2 + x + 1 = 0$ modulo $2$: $X^3 - X^2 + X + [1]_2 = [0]_2$

$ \begin{aligned} x^3 - x^2 + x + 1 & & \equiv 0 \mod 2 \\ \hline 0^3 - 0^2 + 0 + 1 &= 1 &\not\equiv 0 \mod 2 \\ 1^3 - 1^2 + 1 + 1 &= 2 & \equiv 0 \mod 2 \\ \end {aligned} $

$n = 3$

Reduce the equation $x^3 - x^2 + x + 1 = 0$ modulo $3$: $X^3 - X^2 + X + [1]_3 = [0]_3$

$ \begin{aligned} x^3 - x^2 + x + 1 & & & \equiv 0 \mod 3 \\ \hline 0^3 - 0^2 + 0 + 1 &= 1 & &\not\equiv 0 \mod 3 \\ 1^3 - 1^2 + 1 + 1 &= 2 & &\not\equiv 0 \mod 3 \\ 2^3 - 2^2 + 2 + 1 &= 7 &\equiv 1 &\not\equiv 0 \mod 3 \\ \end {aligned} $

Therefore, the equation $x^3 - x^2 + x + 1 = 0$ has no integer roots.

Linear Congruences

Contents

Linear Congruences#