Chapter
Theory
A linear congruence \(ax\equiv b\pmod m\) resembles a linear equation, but division is not always allowed. The main question is whether the coefficient \(a\) is compatible with the modulus \(m\).
If \(\gcd(a,m)=1\), then \(a\) has an inverse modulo \(m\). If \(\gcd(a,m)>1\), the congruence may have no solutions or several residue classes of solutions.
If the statement gives several remainders, write a system of congruences immediately. If \(ax\equiv b\pmod m\) appears, first compute \(\gcd(a,m)\), rather than trying to divide by \(a\).
For systems with non-coprime moduli, first check compatibility modulo the common divisor of the moduli.
Examples
If the coefficient is coprime to the modulus, it can be inverted.
Problem. Solve \(3x\equiv5\pmod7\).
The inverse of \(3\) modulo \(7\) is \(5\), because \(3\cdot5\equiv1\). Multiply: \(x\equiv5\cdot5=25\equiv4\pmod7\).
Comment. This is the correct replacement for division.
Before dividing, check the GCD.
Problem. Solve \(6x\equiv5\pmod9\).
\(\gcd(6,9)=3\), but \(3\nmid5\). Therefore the congruence has no solutions.
Comment. One GCD check settles the problem.
If the common divisor divides the right side, several solutions appear.
Problem. Solve \(6x\equiv12\pmod{18}\).
Divide \(6,12,18\) by \(6\): \(x\equiv2\pmod3\). Modulo \(18\), this gives \(x\equiv2,5,8,11,14,17\pmod{18}\).
Comment. The modulus changed; this is the main source of mistakes.
For coprime moduli, the solution is unique modulo their product.
Problem. Solve \(x\equiv2\pmod3\), \(x\equiv3\pmod5\).
The numbers \(2,5,8,11,\ldots\) have residue \(2\) modulo \(3\). Among them, \(8\equiv3\pmod5\). Hence \(x\equiv8\pmod{15}\).
Comment. One may search within one residue class.
Non-coprime moduli require a common-divisor check.
Problem. Prove that the system \(x\equiv2\pmod6\), \(x\equiv3\pmod9\) has no solutions.
If \(x\equiv2\pmod6\), then \(x\equiv2\pmod3\). If \(x\equiv3\pmod9\), then \(x\equiv0\pmod3\). One number cannot have two different residues modulo \(3\). No solutions exist.
Comment. This is compatibility modulo \(\gcd(6,9)=3\).
If residues agree modulo the common divisor, the system can be solved.
Problem. Solve \(x\equiv4\pmod6\), \(x\equiv10\pmod{15}\).
Both residues are \(1\) modulo \(3\), so the system is compatible. Let \(x=6k+4\). Then \(6k+4\equiv10\pmod{15}\), so \(6k\equiv6\pmod{15}\). Divide by \(3\): \(2k\equiv2\pmod5\), hence \(k\equiv1\pmod5\). Thus \(x\equiv10\pmod{30}\).
Comment. The answer is written modulo \(\operatorname{lcm}(6,15)=30\).
Sometimes the conditions already contain a hidden contradiction.
Problem. Find all \(x\pmod{84}\) such that \(x\equiv2\pmod3\), \(x\equiv3\pmod7\), \(x\equiv4\pmod{12}\).
From \(x\equiv4\pmod{12}\), we get \(x\equiv1\pmod3\). But the first condition requires \(x\equiv2\pmod3\). Contradiction, so there are no solutions.
Comment. Check compatibility before computing.
A variable divisor can be forced to divide a small number.
Problem. Find all positive \(n\) such that \(2n+1\mid n^2+n+7\).
If \(2n+1\mid n^2+n+7\), then it divides \(4(n^2+n+7)=(2n+1)^2+27\). Hence \(2n+1\mid27\). Since \(n>0\), \(2n+1\in\{3,9,27\}\). Thus \(n=1,4,13\), and all three values work.
Comment. This is not a direct congruence, but it leads to a linear restriction.
Problems
Solve \(x+3\equiv1\pmod7\).
Subtract \(3\) from both sides.
\(x\equiv1-3\equiv-2\equiv5\pmod7\).
Solve \(3x\equiv1\pmod7\).
Find a number whose product with \(3\) is \(1\) modulo \(7\).
\(3\cdot5=15\equiv1\pmod7\). Hence \(x\equiv5\pmod7\).
Find the inverse of \(5\) modulo \(12\).
Check \(5\cdot5\).
\(5\cdot5=25\equiv1\pmod{12}\). Therefore the inverse of \(5\) modulo \(12\) is \(5\).
Solve the system \(x\equiv2\pmod3\), \(x\equiv1\pmod5\).
Search among \(2,5,8,11,\ldots\).
Numbers congruent to \(2\) modulo \(3\) are \(2,5,8,11,\ldots\). Among them, \(11\equiv1\pmod5\). Hence \(x\equiv11\pmod{15}\).
Prove that \(2x\equiv1\pmod4\) has no solutions.
The left side is always even.
The number \(2x\) is even, so modulo \(4\) it can have residue \(0\) or \(2\). Residue \(1\) is impossible. Also \(\gcd(2,4)=2\nmid1\), so there are no solutions.
Solve \(4x\equiv6\pmod{10}\).
Divide \(4,6,10\) by their common divisor \(2\).
\(\gcd(4,10)=2\), and \(2\mid6\). Divide by \(2\): \(2x\equiv3\pmod5\). The inverse of \(2\) modulo \(5\) is \(3\), so \(x\equiv9\equiv4\pmod5\). Modulo \(10\): \(x\equiv4\) or \(9\).
Solve \(6x\equiv12\pmod{18}\).
After reduction, the modulus becomes \(3\).
Divide \(6,12,18\) by \(6\): \(x\equiv2\pmod3\). Modulo \(18\), these are the classes \(2,5,8,11,14,17\).
Solve \(9x\equiv6\pmod{15}\).
Reduce by \(\gcd(9,15)=3\).
We get \(3x\equiv2\pmod5\). The inverse of \(3\) modulo \(5\) is \(2\), so \(x\equiv4\pmod5\). Modulo \(15\): \(x\equiv4,9,14\).
Solve the system \(x\equiv3\pmod4\), \(x\equiv2\pmod5\).
Search among \(3,7,11,15,19,\ldots\).
Among \(3,7,11,15,19,\ldots\), which are congruent to \(3\) modulo \(4\), the number \(7\) has residue \(2\) modulo \(5\). The answer is \(x\equiv7\pmod{20}\).
Prove that the system \(x\equiv2\pmod6\), \(x\equiv3\pmod9\) has no solutions.
Compare both conditions modulo \(3\).
The first condition gives \(x\equiv2\pmod3\). The second gives \(x\equiv0\pmod3\). These cannot hold simultaneously. No solutions exist.
Solve \(x\equiv4\pmod6\), \(x\equiv1\pmod9\).
Let \(x=6k+4\).
Substitute: \(6k+4\equiv1\pmod9\), so \(6k\equiv6\pmod9\). Divide by \(3\): \(2k\equiv2\pmod3\), hence \(k\equiv1\pmod3\). Then \(x=6(3t+1)+4=18t+10\). The answer is \(x\equiv10\pmod{18}\).
Find the smallest positive number that leaves remainder \(2\) modulo \(5\) and remainder \(3\) modulo \(7\).
Check \(2,7,12,17,\ldots\).
Numbers of the form \(5k+2\) are \(2,7,12,17,\ldots\). The first one with residue \(3\) modulo \(7\) is \(17\). The answer is \(17\).
Prove that \(ax\equiv b\pmod m\) has a solution if and only if \(\gcd(a,m)\mid b\).
Rewrite the congruence as \(ax-b=my\).
The congruence is equivalent to the integer equation \(ax-my=b\). All numbers of the form \(ax-my\) are divisible by \(d=\gcd(a,m)\), so \(d\mid b\) is necessary. Conversely, if \(d\mid b\), Bezout's identity gives \(u,v\) with \(au+mv=d\). Multiplying by \(\frac bd\), we represent \(b\) as \(aX+mY\), giving a solution to the congruence.
Find all positive \(n\) such that \(2n+1\mid n^2+n+7\).
Multiply the expression by \(4\).
If \(2n+1\mid n^2+n+7\), then \(2n+1\mid4(n^2+n+7)\). But \(4(n^2+n+7)=(2n+1)^2+27\). Hence \(2n+1\mid27\). For positive \(n\), \(2n+1=3,9,27\), so \(n=1,4,13\). All three work.
Find all \(x\pmod{84}\) such that \(x\equiv2\pmod3\), \(x\equiv3\pmod7\), \(x\equiv4\pmod{12}\).
Compare the first and third conditions modulo \(3\).
From \(x\equiv4\pmod{12}\), we get \(x\equiv1\pmod3\). But the first condition requires \(x\equiv2\pmod3\). Contradiction. Therefore there are no solutions.
Solve \(x\equiv5\pmod8\), \(x\equiv2\pmod9\), \(x\equiv1\pmod5\).
First combine the first two congruences.
Let \(x=8a+5\). Modulo \(9\): \(8a+5\equiv2\), so \(-a\equiv-3\), hence \(a\equiv3\pmod9\). Thus \(x\equiv29\pmod{72}\). Now \(x=29+72t\), and modulo \(5\): \(4+2t\equiv1\), so \(2t\equiv2\), \(t\equiv1\pmod5\). We obtain \(x\equiv101\pmod{360}\).
Find all \(x\pmod{60}\) such that \(4x\equiv8\pmod{12}\) and \(x\equiv3\pmod5\).
First solve \(4x\equiv8\pmod{12}\).
The congruence \(4x\equiv8\pmod{12}\), after division by \(4\), gives \(x\equiv2\pmod3\). Combine with \(x\equiv3\pmod5\). Among \(3,8,13,\ldots\) modulo \(5\), the number \(8\equiv2\pmod3\). Hence \(x\equiv8\pmod{15}\). Modulo \(60\), this gives \(x\equiv8,23,38,53\).
Find the smallest positive \(n\) such that \(n\equiv1\pmod2\), \(n\equiv2\pmod3\), \(n\equiv3\pmod5\).
First combine the conditions modulo \(2\) and \(3\).
The conditions \(n\equiv1\pmod2\), \(n\equiv2\pmod3\) give \(n\equiv5\pmod6\). Checking \(5,11,17,23,\ldots\), the first number congruent to \(3\) modulo \(5\) is \(23\). The answer is \(23\).
Find all solutions of \(12x\equiv18\pmod{30}\).
\(\gcd(12,30)=6\).
Since \(6\mid18\), divide by \(6\): \(2x\equiv3\pmod5\). The inverse of \(2\) modulo \(5\) is \(3\), so \(x\equiv9\equiv4\pmod5\). Modulo \(30\): \(x\equiv4,9,14,19,24,29\).
Find all \(x\pmod{100}\) such that \(x\equiv3\pmod4\) and \(x\equiv7\pmod{25}\).
Check the number \(7\).
The number \(7\) has residue \(3\) modulo \(4\) and residue \(7\) modulo \(25\). Since \(4\) and \(25\) are coprime, the solution is unique modulo \(100\). The answer is \(x\equiv7\pmod{100}\).
Prove: the system \(x\equiv r\pmod m\), \(x\equiv s\pmod n\) has a solution if and only if \(r\equiv s\pmod{\gcd(m,n)}\).
Necessity follows from \(x-r\) being divisible by \(m\) and \(x-s\) by \(n\). For sufficiency, reduce to a linear congruence.
Let \(d=\gcd(m,n)\). If a solution \(x\) exists, then \(x-r\) is divisible by \(m\), and \(x-s\) is divisible by \(n\), so both are divisible by \(d\). Then \(r-s=(x-s)-(x-r)\) is divisible by \(d\).
Conversely, suppose \(d\mid r-s\). Look for \(x=r+mk\). We need \(r+mk\equiv s\pmod n\), i.e. \(mk\equiv s-r\pmod n\). This linear congruence has a solution exactly because \(\gcd(m,n)=d\mid s-r\). Hence the original system is compatible.
Find all positive \(n\) such that \(3n+2\mid n^2+5n+9\).
Force \(3n+2\) to divide a constant.
If \(3n+2\mid n^2+5n+9\), then it divides \(9(n^2+5n+9)=9n^2+45n+81\). Subtract \((3n+2)^2=9n^2+12n+4\): we get \(3n+2\mid33n+77\). Now \(3(33n+77)-33(3n+2)=165\), so \(3n+2\mid165\). The positive divisors of \(165\) congruent to \(2\) modulo \(3\) are \(5\) and \(11\). Thus \(3n+2=5\) or \(11\), giving \(n=1\) or \(3\). Both values check.
Find the smallest positive \(n\) such that \(n\equiv-1\pmod2\), \(n\equiv-1\pmod3\), \(n\equiv-1\pmod5\), but \(n\equiv0\pmod7\).
The first three conditions mean \(n\equiv-1\pmod{30}\).
The first three conditions give \(n\equiv29\pmod{30}\). Let \(n=7k\). Then \(7k\equiv29\pmod{30}\). The inverse of \(7\) modulo \(30\) is \(13\), so \(k\equiv29\cdot13\equiv17\pmod{30}\). The smallest positive \(k\) is \(17\), hence \(n=119\).
Find all \(x\pmod{420}\) satisfying \(x\equiv1\pmod4\), \(x\equiv2\pmod5\), \(x\equiv3\pmod7\), \(6x\equiv12\pmod9\).
First solve the last linear congruence.
Reduce \(6x\equiv12\pmod9\) by \(3\): \(2x\equiv4\pmod3\), so \(-x\equiv1\pmod3\), hence \(x\equiv2\pmod3\). Now solve the system with coprime moduli \(3,4,5,7\): \(x\equiv2\pmod3\), \(x\equiv1\pmod4\), \(x\equiv2\pmod5\), \(x\equiv3\pmod7\).
Combine \(x\equiv1\pmod4\) and \(x\equiv2\pmod5\): this gives \(x\equiv17\pmod{20}\). The number \(17\) also satisfies \(17\equiv2\pmod3\) and \(17\equiv3\pmod7\). Since \(3,4,5,7\) are pairwise coprime, the answer is unique modulo \(420\): \(x\equiv17\pmod{420}\).
Ladders