Linear Congruences and Their Solvability

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

We study the solvability of linear congruence equations and practice solving them. We also discuss incongruent solutions and characterize solvability using inverses. Then we place significance on using the Euclidean algorithm, solving linear Diophantine methods, and importantly, on using an ad hoc method.

Introduction to Linear Congruences

Linear congruences are the main object of discussion for this article.

Definition. Given integers $a, b$ and a modulus $n,$ a congruence equation of the form $a x\equiv b \pmod{n} $ is called a linear congruence where $x$ is an unknown. 

Solvability of a linear congruence  $a x\equiv b \pmod{n}$ can easily be described by the following: 

(i) if $a$ and $n$ are relatively prime then there is precisely one incongruent solution modulo $n$,

(ii) if the greatest common divisor of $a$ and $n$ does not divide $b$, then the linear congruence has no solution, and

(iii) if the gcd of $a$ and $n$ does divide $b$ then there are exactly $(a,n)$ distinct incongruent solutions modulo $n.$ 

Solvability of Linear Congruences

Knowing whether there are solutions to a given linear congruence is often the first step, but as we will see, the work of computing $(a,n)$ can  be also used in finding solutions, if there are any.

Theorem. Let $x$ be an unknown in the linear congruence equation $a x\equiv b \pmod{n}$ and $d=(a,n).$ 

(1) If $d=1,$ then there is precisely one solution.

(2) If $d|b$ there are exactly $d$ distinct solutions, otherwise there are no solutions.

Proof.  By the Euclidean algorithm there are integers $s$ and $t$ such that $a s+n t=1,$ and then $a (s b)+n(t b)=b$ and thus  we find that $x=s b$ is a solution of the congruence. If $y$ is any other solution, then $a y\equiv b \pmod{n}.$ Thus, $a x\equiv a  y \pmod{n} $ and since $(a,n)=1$ we have $x\equiv y \pmod{n} .$ Since the congruence is equivalent to $a x+n(- y)=b$ in integers $x$ and $y,$ the existence of solutions $x$ and $y$  requires that $d=(a,n)$ divide $b.$ 

Euclid's algorithm

Suppose then that this requirement is satisfied and let $x=x_0+(n/d)t$ and $y=y_0+(a/d)t$ where $x=x_0$  and $y=y_0$ is a particular solution, be all solutions to $a x+n(- y)=b.$ Therefore, for any integer $t,$ $x$ is a solution to $a x\equiv  b \pmod{n}.$  To determine that there are $d$ incongruent solutions, we find the condition that describes when two solutions are congruent modulo $n.$ 

Assume we have two solutions

Suppose we have two solutions, namely,  $$x_0+\left(\frac{n}{d}\right)t_1\equiv x_0+\left(\frac{n}{d}\right)t_2  \pmod{n}.$$  Since $$\left(\frac{n}{d},n\right)=\frac{n}{d}, $$ it follows that $t_1\equiv t_2 \pmod{d}.$ This show that a complete set of incongruent solutions is obtained by taking $x=x_0+\left(\frac{n}{d}\right)t$ and $t$ ranges through a complete system of residues modulo $d;$ one such  set is given by $t=0,1,2, \ldots ,d-1.$

Examples

Example. Solve the linear congruence $131 x\equiv 21 \pmod{77}.$

Solution. Because $1=(131,77)|21$ there is a unique solution modulo 77.  We have $54x\equiv 21 \pmod{77}$ and dividing by $3$  we have $18 x\equiv 7 \pmod{77}.$ Next multiplying by $4$ we have $72 x\equiv 28 \pmod{77}$ and so $-5x\equiv 28\equiv 105 \pmod{77}.$ Therefore, $x\equiv -21\equiv 56 \pmod{77}.$    

Example. Solve the linear congruence $6x\equiv (10)^k \pmod{21}.$ 

Solution. There is no solution because $(6,21)=3$ does not divide $2^k5^k$ for any positive integer $k.$ 

Example. Solve the linear congruence $91 x\equiv 98 \pmod{119}.$

Solution. Because $7=(91,119)|98$ there are $7$ incongruent solutions modulo $119.$ We use cancellation to simplify the congruence  to $13 x\equiv 14 \pmod{17}.$ We have $-4x\equiv -3\equiv -20 \pmod{17}.$ Therefore, in terms of the original modulus, the solutions are  $$x\equiv 5, 22, 39, 56, 73, 90, 107 \pmod{199}.$$

Solving More Linear Congruence Equations

Example. Solve the linear congruence $31 x\equiv 12 \pmod{24}.$

Solution. Since $(31,24)=1$ and $1|12$ there is exactly one incongruent solution modulo $24.$ To find this solution we use $31\equiv  7 \pmod{24}$ so $31 x\equiv 7x \pmod{24}$ which means we now solve the linear congruence $7x\equiv 12 \pmod{24}.$ Next we  multiply by 7, to obtain $49x\equiv 84 \pmod{24}.$ Then since $49\equiv 1 \pmod{24}$ and $84\equiv 12 \pmod{24}$ we now have  $x\equiv 12 \pmod{24}$ as our solution to the linear congruence $31 x\equiv 12 \pmod{24}.$    

Example. Solve the linear congruence $987 x\equiv 610 \pmod{1597}.$

Solution. Solving the linear congruence equation is equivalent to solving the linear Diophantine equation $987 x+1597 (-y)=610$ for $x$  and $y.$ There is a solution because $(987,1597)=1$ and it is unique modulo $1597.$ A particular solution is $x=-1$ and $y=-1.$ Thus all  solutions to the Diophantine equations are $$ x=-1+\frac{1597}{1}t \qquad \text{and}\qquad y=-1+\frac{987}{1}t.$$ Suppose that $$-1+\frac{1597}{1}t_1\equiv -1+\frac{1597}{1}t_2  \pmod{1597}$$  are two solutions to the congruence equation. Then clearly, $t_1\equiv t_2 \pmod{1597}.$ This show that a complete set of incongruent solutions is obtained by taking $x=-1+1597t$ and $t=0.$  Therefore, the unique solution is $x\equiv 1596 \pmod{1597}.$

Example. Solve the linear congruence $42 x\equiv 50 \pmod{76}.$

Solution. Solving the linear congruence equation is equivalent to solving the linear Diophantine equation $42 x+76(- y)=50$ for $x$ and  $y.$ There is a solution because $(42,76)=2$ and $2|50;$ and so there are exactly two solutions modulo $76.$ A particular solution is $x=-35$  and $y=20.$  Thus all solutions for $42 x+76(- y)=50$ are $$x=-35+\frac{76}{2}t \qquad \text{and} \qquad y=20+\frac{42}{2}t.$$ Suppose that  $-35+38t_1\equiv -35+38t_2\pmod{76}$ are two solutions.  Since $(38,76)=38,$ we have, $t_1\equiv t_2 \pmod{2}.$  This show that a complete set of incongruent solutions  is obtained by taking $x=-35+38t$ and $t=0,1,2, \ldots ,d-1$ where $d=(42,76)=2.$  Therefore, the solutions are $x\equiv 3 \pmod{76}$ and $x\equiv 41 \pmod{76}.$ 

The Inverse of a Integer Modulo $n$

Notice that to solve a linear congruence equation $a x\equiv b \pmod{n}$ we find, (if possible) an integer $h$ such that $a h\equiv 1 \pmod{n}$ and then using $h$ we solve by multiplying by $h$, obtaining $x\equiv h b \pmod{n}.$

Definition. Let $a$ be an integer with $(a,n)=1.$  Then a solution of the linear congruence $a x\equiv 1 \pmod{n}$ is called an inverse of $a.$  

Theorem. Let $p$ be a prime. The positive integer $a$ is its own inverse modulo $p$ if and only if $a\equiv  1 \pmod{p}$ or $a\equiv -1 \pmod{p}.$

Proof. If $a$ is its own inverse modulo $p,$ then $a^2\equiv 1 \pmod{p}.$ Thus, $p\left|\left(a^2-1\right)\right.$ and so either  $p|(a-1)$ or $p|(a+1).$ Therefore, $a\equiv 1 \pmod{p}$ or $a\equiv -1 \pmod{p}.$ Conversely, if $a\equiv 1 \pmod{p}$  or $a\equiv -1 \pmod{p},$ then $a^2\equiv 1 \pmod{p},$ so that $a$ is its own inverse modulo $p.$

ExampleBy finding an inverse, solve the linear congruence $37x\equiv b \pmod{53}.$

Solution. First we solve, $37 x\equiv 1 \pmod{53}.$ We have  $-16x\equiv 1\equiv 54   \pmod{53}.$ Now dividing by $2$ and simplifying, we have $   8x\equiv -27\equiv 26\equiv 132   \pmod{53}$ Again dividing by $2$ and simplifying, we have $   2x\equiv 33\equiv 86   \pmod{53}$ Therefore, $x\equiv 43  \pmod{53}.$ Now to solve $37 x\equiv b  \pmod{53}$ we multiply by $43$ and we have $(43) 37 x\equiv  43  b  \pmod{53}.$ Thus $x\equiv 43 b  \pmod{53}$ is the solution.   

Solving Linear Congruence by Finding an Inverse

Example. By finding an inverse, solve the linear congruence $31 x\equiv 12 \pmod{24}.$

Solution. Recall that since $(31,24)=1$ and $1|12$ there is exactly one incongruent solution modulo $24.$ To find this solution let’s  use the definition of congruence, namely $24|(31x-12)$ which means there exists an integer $y$ such that $31x-12=24y$ and so we will solve  the linear Diophantine equation $31x+24(-y)=12.$ Now notice that we merely need the $x$ solutions because of our original linear congruence involves  only $x.$ But first we need a particular solution to this linear Diophantine equation, which can be found using the Euclidean algorithm,

$31=1(24)+7$ with $0\leq  7<24$

$24=3(7)+3,$ with $0\leq 2<7 $

$7=2(3)+1$, with $0\leq 1<2$ 

so $(31,24)=1$ which we already knew but now we can use back substitution to find 1 as a linear combination of $31$ and $24,$  namely,

$1=7-2(3)$,

$1=7-2(24-3(7))$, 

$1=(7)7+(-2)(24)$,  

$1=(7)(31-1(24))+(-2)(24)$, 

$1=(7)(31)+(-9)(24).$ 

Then multiplying by 12 yields a particular solution with $x_0=84$ since, ${12=(31)(84)+(24)(-108)}$. So all solutions to the linear Diophantine equation $31x+24(-y)=12$ are given $x=84+24t$ where $t\in \mathbb{Z}.$ In particular when $t=-3$  we find the solution $x\equiv 12 \pmod{24}.$

Example. Solve the linear congruence ${78 x\equiv 12 \pmod{240}},$ by finding an inverse. 

Solution.  Since $(78,240)=6$ and $6|12$ there are exactly six incongruent solution modulo $240.$ To find these solutions let’s use  the definition of congruence, namely $240|(78x-12)$ which means there exists an integer $y$ such that $78x-12=240y$ and so we will solve the  linear Diophantine equation $78x+240(-y)=12.$ Using the Euclidean algorithm,  $$ 240=3(78)+6,  \text{with} 0\leq  7<2 $$ and now we can write 6 as a linear combination of $78$ and $240,$ namely, ${6=(-3)(78)+(1)(240)}$.  Then multiplying by 2 yields a particular solution with $x_0=-6$ since, $12=(-6)(78)+(2)(240)$. So all solutions to the linear Diophantine equation $78x-12=240y$ are given $$ x=-6+\frac{240}{6}t=-6+40t $$ where $t\in \mathbb{Z}.$ In particular, when $t=1,2,3,4,5,6,7$ we find the six incongruent solutions modulo 240, $x\equiv 34,74,114,154,194 ,234 \pmod{240}.$

Example. For which integers $c,$ $0\leq c\leq 1001,$ does the congruence $154x\equiv c \pmod{1001}$ have solutions? When there are solutions, how many incongruent solutions are there?

Exercises on Linear Congruences

Exercise. For which integers $c,$ $0\leq c\leq 1001,$ does the congruence $154x\equiv c \pmod{1001}$ have solutions? When there are solutions,  how many incongruent solutions are there?   

Exercise. Solve the linear congruence equation 

$(1) \quad a x\equiv b \pmod{n}.$ $a=1348,b=123, n=45 $

$(2) \quad a=341123, b=325, n=234 $

$(3) \quad a=809834,b=239, n=112 $

$(4) \quad a=20934,b=198, n=29 $

$(5) \quad a=20034,b=314, n=23 $

$(6) \quad a=3407,b=349, n=128 $

$(7) \quad a=29976,b=276, n=134 $

$(8) \quad a=34534,b=39, n=93 $

$(9) \quad a=345996,b=967, n=238 $

$(10) \quad a=88629,b=865, n=34 $

$(11) \quad a=929001,b=229, n=222 $

$(12) \quad a=987559,b=143, n=367 $

Exercise. Determine which integers $a,$ where $1\leq a\leq 14,$ have an inverse modulo 14 and for each one find its inverse. 

Exercise. Determine which integers $a,$ where $1\leq a\leq 30,$ have an inverse modulo 30 and for each one find its inverse.    

Exercise. Show that if $\bar{a}$ is an inverse of $a$ modulo $m$ and $\bar{b}$ is an inverse of $b$ modulo $m,$ then $\bar{a} \bar{b}$ is  an inverse of $a b$ modulo $m.$   

Exercise. Find all solutions to the following linear congruence equations.

$(1) \quad 3x\equiv 2 \pmod{7}$

$(2) \quad 6x\equiv 3 \pmod{9}$

$(3) \quad 17x\equiv 14 \pmod{21}$

$(4) \quad 15x\equiv 9 \pmod{25}$

$(5) \quad 128x\equiv 833 \pmod{1001}$

$(6) \quad 987x\equiv 610 \pmod{1597}$

$(7) \quad 36x\equiv 30 \pmod{42}$

$(8) \quad 143x\equiv 169 \pmod{110}$

$(9) \quad 51 x\equiv 0 \pmod{17}$

$(10) \quad 52 x\equiv 0 \pmod{17}$      

$(11) \quad 253 x\equiv 341 \pmod{299}$      

$(12) \quad 441 x\equiv 465 \pmod{640}$

$(13) \quad 36x\equiv 8 \pmod{102}$   

$(14) \quad 34x\equiv 60 \pmod{98}$     

$(15) \quad 140 x\equiv 133 \pmod{30}$

$(16) \quad 140 x\equiv 133 \pmod{31}$

Exercise. Find all solutions of the linear congruence $$3x-7y\equiv 11 \pmod{13}.$$ 

Exercise. What can you conclude if $a^2\equiv b^2 \pmod{p}$, where $a$ and $b$ are integers and $p$ is prime?

More Exercises on Linear Congruences

Exercise. Show that if $n$ is an odd positive integer, then $$1+2+3+\cdots +(n-1)\equiv 0 \pmod{n}. $$ Is this statement true of $n$ is even?

Exercise. Show that if $n$ is an odd integer or if $n$ is a positive integer divisible by $4$, then $$1^3+2^3+3^3+\cdots +(n-1)^3\equiv 0 \pmod{n}.$$ Is this statement true if $n$ is not divisible by $4$?

Exercise. For which positive integers $n$ is it true that $$1^2+2^2+3^2+\cdots +(n-1)^2\equiv 0 \pmod{n}.$$

Exercise. Show by mathematical induction that if $n$ is a positive integer, then $5^n\equiv 1+4n \pmod{16}.$

Exercise. Give a complete system of residues modulo 13 consisting of entirely odd integers.

Exercise. An astronomer knows that a satellite orbits the Earth in a period that is an exact multiple of 1 hour that is less than 1 day. If the astronomer notes that the satellite completes 11 orbits in an interval that starts when a 24-hour clock reads 0 hours and ends when the clock reads 17 hours, how long is the orbital period of the satellite?

Exercise. Solve the linear congruence equation $987x\equiv 610 \pmod{1597}.$

Exercise. Solve the linear congruence equation $987x\equiv 610 \pmod{1597}.$  If you find solutions explain why you have found them all.

Exercise. Suppose $p\equiv 3 \pmod{4}.$ Show that $(p+1)/4$ is an integer and is the multiplicative inverse of 4 modulo $p.$

Exercise. Explain why the linear congruence equation $3x\equiv 81 \pmod{910}$ is solvable or not solvable. If possible solve it.

Leave a Comment