The Central Idea
A linear congruence in one variable has the form
\[ \boxed{ax\equiv b\pmod n}, \]where \(a\), \(b\), and \(n\) are integers with \(n>0\).
A solution is an integer \(x\) whose substitution makes the congruence true.
A First Example
Solve
\[ x+3\equiv1\pmod5. \]Subtract \(3\) from both sides:
\[ x\equiv-2\pmod5. \]Since
\[ -2\equiv3\pmod5, \]the solution is
\[ \boxed{x\equiv3\pmod5}. \]Linear Congruences as Divisibility Statements
The congruence
\[ ax\equiv b\pmod n \]is equivalent to
\[ n\mid(ax-b). \]Therefore there must be an integer \(k\) such that
\[ ax-b=kn. \]Rearranging,
\[ \boxed{ax-kn=b}. \]This connects linear congruences directly to integer linear combinations.
Why Ordinary Division Can Fail
Consider
\[ 2x\equiv2\pmod6. \]In ordinary algebra, we might divide both sides by \(2\). But modular division is not automatically valid.
Testing values shows that
\[ x\equiv1\pmod3 \]solves the congruence. Modulo \(6\), this gives two distinct solutions:
\[ \boxed{x\equiv1,4\pmod6}. \]Simply writing \(x\equiv1\pmod6\) would lose a valid solution.
When a Unique Modular Inverse Exists
If
\[ \gcd(a,n)=1, \]then \(a\) has a multiplicative inverse modulo \(n\).
That means there is an integer \(a^{-1}\) satisfying
\[ aa^{-1}\equiv1\pmod n. \]Multiplying
\[ ax\equiv b\pmod n \]by \(a^{-1}\) gives
\[ \boxed{x\equiv a^{-1}b\pmod n}. \]Example: Solving with an Inverse
Solve
\[ 3x\equiv4\pmod7. \]Since
\[ 3\cdot5=15\equiv1\pmod7, \]the inverse of \(3\) modulo \(7\) is \(5\).
Multiply both sides by \(5\):
\[ x\equiv5\cdot4=20\pmod7. \]Reduce:
\[ \boxed{x\equiv6\pmod7}. \]Checking the Solution
Substitute \(x=6\):
\[ 3(6)=18. \]Since
\[ 18\equiv4\pmod7, \]the solution is correct.
The Solvability Criterion
Consider
\[ ax\equiv b\pmod n. \]Let
\[ d=\gcd(a,n). \]The congruence has a solution exactly when
\[ \boxed{d\mid b}. \]Thus the greatest common divisor determines whether the target value \(b\) is compatible with the modular equation.
Why the GCD Must Divide \(b\)
If
\[ ax\equiv b\pmod n, \]then
\[ ax-b=kn \]for some integer \(k\). Therefore,
\[ b=ax-kn. \]Since \(d=\gcd(a,n)\) divides both \(a\) and \(n\), it divides every integer linear combination of them. Hence
\[ \boxed{d\mid b}. \]Why the Condition Is Also Sufficient
Suppose
\[ d=\gcd(a,n) \]and
\[ d\mid b. \]Bézout's identity gives integers \(u\) and \(v\) such that
\[ au+nv=d. \]If \(b=dc\), multiply by \(c\):
\[ a(uc)+n(vc)=b. \]Therefore,
\[ a(uc)\equiv b\pmod n, \]so a solution exists.
Example: A Congruence with No Solution
Solve
\[ 6x\equiv5\pmod9. \]Compute
\[ \gcd(6,9)=3. \]But
\[ 3\nmid5. \]Therefore,
\[ \boxed{\text{there is no solution}}. \]Example: A Congruence with Several Solutions
Solve
\[ 6x\equiv12\pmod{18}. \]Since
\[ \gcd(6,18)=6 \]and
\[ 6\mid12, \]solutions exist.
Divide the coefficients and modulus by \(6\):
\[ x\equiv2\pmod3. \]Modulo \(18\), the distinct solutions are
\[ \boxed{x\equiv2,5,8,11,14,17\pmod{18}}. \]How Many Solutions Are There?
If
\[ d=\gcd(a,n) \]and \(d\mid b\), then
\[ ax\equiv b\pmod n \]has exactly
\[ \boxed{d} \]distinct solutions modulo \(n\).
If \(d=1\), the solution is unique modulo \(n\).
Reducing a Solvable Congruence
Let
\[ d=\gcd(a,n) \]and suppose \(d\mid b\).
Divide
\[ ax\equiv b\pmod n \]by \(d\) to obtain
\[ \boxed{ \frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{n}{d}} }. \]The reduced coefficient and modulus are relatively prime, so the reduced congruence has a unique solution modulo \(n/d\).
Example: Reduce Before Solving
Solve
\[ 8x\equiv12\pmod{20}. \]Compute
\[ d=\gcd(8,20)=4. \]Since \(4\mid12\), divide by \(4\):
\[ 2x\equiv3\pmod5. \]The inverse of \(2\) modulo \(5\) is \(3\), so
\[ x\equiv9\equiv4\pmod5. \]Therefore, modulo \(20\),
\[ \boxed{x\equiv4,9,14,19\pmod{20}}. \]Lifting the Reduced Solution
Suppose the reduced congruence gives
\[ x\equiv x_0\pmod{n/d}. \]The \(d\) distinct solutions modulo \(n\) are
\[ \boxed{ x\equiv x_0+ k\frac{n}{d} \pmod n, \qquad k=0,1,\ldots,d-1. }. \]These values represent the different lifts of the single reduced solution back to modulus \(n\).
Example: Lifting Explicitly
From
\[ 8x\equiv12\pmod{20}, \]we found
\[ x\equiv4\pmod5. \]Here
\[ d=4 \qquad\text{and}\qquad \frac{n}{d}=5. \]Thus
\[ x\equiv4+5k\pmod{20}, \qquad k=0,1,2,3. \]This gives
\[ \boxed{4,9,14,19}. \]Finding an Inverse by Inspection
For small moduli, a modular inverse can often be found by testing small products.
Find the inverse of \(4\) modulo \(7\).
Compute:
\[ 4\cdot1\equiv4, \] \[ 4\cdot2\equiv1\pmod7. \]Therefore,
\[ \boxed{4^{-1}\equiv2\pmod7}. \]Finding an Inverse with the Euclidean Algorithm
For larger values, use the Extended Euclidean Algorithm.
Find the inverse of \(17\) modulo \(43\).
The Euclidean Algorithm gives
\[ 43=17(2)+9, \] \[ 17=9(1)+8, \] \[ 9=8(1)+1. \]Therefore,
\[ \gcd(17,43)=1. \]Back-Substituting for the Inverse
From
\[ 1=9-8 \]and
\[ 8=17-9, \]we obtain
\[ 1=2(9)-17. \]Since
\[ 9=43-2(17), \]substitute:
\[ 1=2(43)-5(17). \]Therefore,
\[ -5(17)\equiv1\pmod{43}. \]Hence
\[ \boxed{17^{-1}\equiv-5\equiv38\pmod{43}}. \]Using the Inverse to Solve
Solve
\[ 17x\equiv7\pmod{43}. \]Multiply by the inverse \(38\):
\[ x\equiv38\cdot7=266\pmod{43}. \]Since
\[ 266=43(6)+8, \]we obtain
\[ \boxed{x\equiv8\pmod{43}}. \]Cancellation When the Factor Is Relatively Prime to the Modulus
If
\[ ac\equiv bc\pmod n \]and
\[ \gcd(c,n)=1, \]then \(c\) has an inverse modulo \(n\). Multiplying by that inverse gives
\[ \boxed{a\equiv b\pmod n}. \]Thus cancellation is valid when the cancelled factor is a unit modulo \(n\).
General Cancellation Rule
If
\[ ac\equiv bc\pmod n \]and
\[ d=\gcd(c,n), \]then one may conclude
\[ \boxed{ a\equiv b\pmod{n/d} }. \]The modulus may shrink when the cancelled factor shares divisors with the original modulus.
Example: Cancellation with a Reduced Modulus
Suppose
\[ 6x\equiv6y\pmod{15}. \]Since
\[ \gcd(6,15)=3, \]cancellation gives
\[ x\equiv y\pmod5, \]not necessarily modulo \(15\).
Therefore,
\[ \boxed{x\equiv y\pmod5}. \]Solving by Testing Residue Classes
When the modulus is small, direct testing can be useful.
Solve
\[ 4x\equiv3\pmod5. \]Test \(x=0,1,2,3,4\):
\[ 4(0)\equiv0, \] \[ 4(1)\equiv4, \] \[ 4(2)\equiv3\pmod5. \]Thus
\[ \boxed{x\equiv2\pmod5}. \]Testing Is a Verification Method
Direct testing is reliable for a small modulus because there are only finitely many residue classes.
However, systematic inverse and GCD methods scale much better and explain why a solution exists.
Testing is therefore especially useful as a check after a symbolic solution.
Example: No Solution by Residue Behavior
Consider
\[ 4x\equiv3\pmod6. \]The values \(4x\pmod6\) cycle through
\[ 0,\ 4,\ 2,\ 0,\ 4,\ 2,\ldots \]and never produce \(3\).
This agrees with the GCD test:
\[ \gcd(4,6)=2 \]but
\[ 2\nmid3. \]Example: Exactly Two Solutions
Solve
\[ 4x\equiv2\pmod6. \]Here
\[ d=\gcd(4,6)=2 \]and \(2\mid2\), so there are exactly two solutions modulo \(6\).
Divide by \(2\):
\[ 2x\equiv1\pmod3. \]Since \(2^{-1}\equiv2\pmod3\),
\[ x\equiv2\pmod3. \]Lifting to modulus \(6\) gives
\[ \boxed{x\equiv2,5\pmod6}. \]Linear Congruences and Residue Classes
A solution such as
\[ x\equiv4\pmod7 \]represents an entire residue class:
\[ x\in[4]_7. \]Therefore all integers of the form
\[ \boxed{x=4+7k,\qquad k\in\mathbb Z} \]solve the congruence.
From Congruences to Ordinary Integer Equations
Solving
\[ ax\equiv b\pmod n \]means finding integers \(x\) and \(k\) satisfying
\[ ax-b=kn. \]Equivalently,
\[ \boxed{ax-nk=b}. \]This is a linear equation in integers, which foreshadows the next lesson on Diophantine equations.
Common Error: Dividing Without Checking the GCD
From
\[ 6x\equiv12\pmod{18}, \]dividing the coefficient and right side by \(6\) while keeping modulus \(18\) would be incorrect.
The correct reduction divides the modulus as well:
\[ \boxed{x\equiv2\pmod3}. \]That reduced congruence represents six solutions modulo \(18\).
Common Error: Assuming Every Linear Congruence Has a Solution
The equation
\[ 6x\equiv5\pmod9 \]has no solution because
\[ \gcd(6,9)=3 \]and
\[ 3\nmid5. \]Always test solvability before trying to isolate \(x\).
Common Error: Reporting Only One Lifted Solution
Suppose reduction gives
\[ x\equiv2\pmod3 \]from an original congruence modulo \(18\) with
\[ d=6. \]The original problem has six distinct solutions modulo \(18\), not just \(x\equiv2\pmod{18}\).
The complete set is
\[ \boxed{2,5,8,11,14,17\pmod{18}}. \]Common Error: Using a Number That Is Not an Inverse
To invert \(a\) modulo \(n\), verify
\[ aa^{-1}\equiv1\pmod n. \]For example, \(3^{-1}\pmod7\) is \(5\) because
\[ 3\cdot5=15\equiv1\pmod7. \]A number producing any other remainder is not an inverse.
A Reliable Procedure for Solving \(ax\equiv b\pmod n\)
- Compute \(d=\gcd(a,n)\).
- Check whether \(d\mid b\).
- If \(d\nmid b\), conclude that there is no solution.
- If \(d\mid b\), divide \(a\), \(b\), and \(n\) by \(d\).
- Find the inverse of the reduced coefficient modulo the reduced modulus.
- Multiply by that inverse to find one reduced solution.
- Lift the reduced solution back to the original modulus.
- List all \(d\) distinct solutions modulo \(n\).
- Substitute representative values to verify when useful.
Example: Full Workflow
Solve
\[ 14x\equiv8\pmod{30}. \]First,
\[ d=\gcd(14,30)=2. \]Since
\[ 2\mid8, \]solutions exist, and there will be exactly two modulo \(30\).
Divide by \(2\):
\[ 7x\equiv4\pmod{15}. \]Completing the Full Workflow
The inverse of \(7\) modulo \(15\) is \(13\), because
\[ 7\cdot13=91\equiv1\pmod{15}. \]Therefore,
\[ x\equiv13\cdot4=52\equiv7\pmod{15}. \]Lift to modulus \(30\):
\[ x\equiv7+15k\pmod{30}, \qquad k=0,1. \]Thus
\[ \boxed{x\equiv7,22\pmod{30}}. \]Checking Both Solutions
For \(x=7\),
\[ 14(7)=98\equiv8\pmod{30}. \]For \(x=22\),
\[ 14(22)=308\equiv8\pmod{30}. \]Both residue classes satisfy the original congruence.
Practice 1: Unique Solution
Solve
\[ 5x\equiv3\pmod7. \]Practice 2: No Solution
Determine whether
\[ 8x\equiv3\pmod{12} \]has a solution.
Practice 3: Multiple Solutions
Solve
\[ 6x\equiv9\pmod{15}. \]Practice 4: Find an Inverse
Find the multiplicative inverse of
\[ 7 \]modulo \(11\).
Practice 5: Solve with an Inverse
Solve
\[ 7x\equiv5\pmod{11}. \]Practice 6: Reduce and Lift
Solve
\[ 10x\equiv15\pmod{25}. \]Practice 7: Count the Solutions
Without solving completely, determine how many distinct solutions modulo \(28\) the congruence
\[ 12x\equiv8\pmod{28} \]has.
Practice 8: Cancellation
From
\[ 10a\equiv10b\pmod{35}, \]what congruence between \(a\) and \(b\) follows from the general cancellation rule?
Practice 9: Convert to an Integer Equation
Rewrite
\[ 9x\equiv4\pmod{13} \]as an equation involving integers \(x\) and \(k\).
Practice 10: Identify the Error
A student solves
\[ 4x\equiv8\pmod{12} \]by dividing by \(4\) and writing
\[ x\equiv2\pmod{12}. \]Explain the error and give the correct solutions.
Practice Answers
Practice 1
The inverse of \(5\) modulo \(7\) is \(3\), since
\[ 5\cdot3=15\equiv1\pmod7. \]Therefore,
\[ x\equiv3\cdot3=9\equiv2\pmod7. \]Thus
\[ \boxed{x\equiv2\pmod7}. \]Practice 2
\[ \gcd(8,12)=4. \]Since
\[ 4\nmid3, \]we conclude
\[ \boxed{\text{no solution}}. \]Practice 3
\[ \gcd(6,15)=3. \]Since \(3\mid9\), divide by \(3\):
\[ 2x\equiv3\pmod5. \]The inverse of \(2\) modulo \(5\) is \(3\), so
\[ x\equiv9\equiv4\pmod5. \]Lift to modulus \(15\):
\[ \boxed{x\equiv4,9,14\pmod{15}}. \]Practice 4
\[ 7\cdot8=56\equiv1\pmod{11}. \]Therefore,
\[ \boxed{7^{-1}\equiv8\pmod{11}}. \]Practice 5
Multiply by \(8\):
\[ x\equiv8\cdot5=40\equiv7\pmod{11}. \]Therefore,
\[ \boxed{x\equiv7\pmod{11}}. \]Practice 6
\[ \gcd(10,25)=5. \]Divide by \(5\):
\[ 2x\equiv3\pmod5. \]Thus
\[ x\equiv4\pmod5. \]Lifting to modulus \(25\) gives
\[ \boxed{x\equiv4,9,14,19,24\pmod{25}}. \]Practice 7
\[ d=\gcd(12,28)=4. \]Since
\[ 4\mid8, \]there are exactly
\[ \boxed{4} \]distinct solutions modulo \(28\).
Practice 8
\[ d=\gcd(10,35)=5. \]Therefore the modulus reduces to
\[ \frac{35}{5}=7. \]Hence
\[ \boxed{a\equiv b\pmod7}. \]Practice 9
The congruence means
\[ 13\mid(9x-4). \]Therefore there is an integer \(k\) such that
\[ \boxed{9x-13k=4}. \]Practice 10
Here
\[ \gcd(4,12)=4. \]Dividing the coefficient and right side by \(4\) requires dividing the modulus by \(4\) as well:
\[ x\equiv2\pmod3. \]Modulo \(12\), this gives four solutions:
\[ \boxed{x\equiv2,5,8,11\pmod{12}}. \]What to Remember
- A linear congruence has the form \(ax\equiv b\pmod n\).
- It is equivalent to the integer equation \(ax-nk=b\).
- If \(d=\gcd(a,n)\), a solution exists exactly when \(d\mid b\).
- When solutions exist, there are exactly \(d\) distinct solutions modulo \(n\).
- If \(\gcd(a,n)=1\), the coefficient \(a\) has a modular inverse and the solution is unique modulo \(n\).
- For \(d>1\), divide \(a\), \(b\), and \(n\) by \(d\), solve the reduced congruence, and lift the solution back.
- Cancellation is valid modulo the original modulus only when the cancelled factor is relatively prime to that modulus.
- The Extended Euclidean Algorithm provides a systematic way to find modular inverses.
The central workflow is: check the GCD first, reduce when necessary, use an inverse when available, and account for every distinct lifted solution.
Where We Go Next
Linear congruences are modular versions of integer linear equations. The next lesson, Diophantine Equations, studies equations whose solutions are required to be integers and develops the connection between greatest common divisors, Bézout identities, and complete families of integer solutions.