Practice
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}\).