Solve 6x≡9 modulo fifteen. Writing 6x−15y=9 reveals gcd(6, 15)=3, which divides nine. Divide the entire divisibility statement by three to obtain 2x≡3 modulo five. The inverse of two modulo five is three, so x≡4 modulo five. Modulo fifteen this gives three classes: 4, 9 and 14. Substitute all three into the original congruence.
Predict
Predict the most common cancellation error: dividing 6x≡9 by three while keeping modulus fifteen. That would assert 2x≡3 modulo fifteen, which loses valid solutions. Dividing a congruence by a common gcd changes the modulus too. The reduced equation has one class in a smaller residue system; lifting it back creates exactly as many classes as the gcd.
Experiment
Inspect the lifts explicitly.
Reduced class representative
Lift modulo 15
6x modulo 15
4
4
9
4+5
9
9
4+10
14
9
Change the right side from nine to ten. The gcd no longer divides it, so no solution exists. This comparison separates a failed inverse calculation from a genuine impossibility certificate.
Understand
Let m>0 and d=gcd(a, m). The equation ax≡b mod m means ax−my=b for some integer y. It is solvable precisely when d|b. In the solvable case divide by d: (a/d)x≡b/d modulo m/d. The coefficient is coprime to the reduced modulus, so it has an inverse and determines a unique class x₀ modulo m/d. Every lift x₀+k(m/d) solves the original congruence. Taking k=0,…, d−1 gives distinct classes modulo m: equality of two lifts would imply d divides their index difference. Every integer solution belongs to one of those classes. Thus the number is exactly d, not merely at most d.
Apply
Modular inversion is an extended Euclidean task. If ua+vm=1, the class of u is the inverse of a, and any two inverses differ by a multiple of m. An inverse does not mean the real reciprocal 1/a has been rounded into an integer. It is a multiplicative identity within the residue ring. For a product congruence ac≡bc mod m, the valid general cancellation result is a≡b modulo m/gcd(c, m). Only when the gcd is one can the original modulus be retained.
The solution count can also be seen through a homomorphism. Multiplication by a on the additive residues modulo n has kernel consisting of exactly gcd(a, n) classes. Every solvable target has a solution set obtained by adding that kernel to one particular solution, so all nonempty fibers have equal size. This viewpoint does not change the algorithm, but explains why the number of solutions depends on a and n rather than on which compatible target b was chosen. Verify the kernel directly for multiplication by four modulo twelve.
Continue
Use this theorem to solve modular scheduling or divisibility constraints, but distinguish a residue class from additional inequalities such as nonnegative time or a finite deadline. A robust solver should return either the gcd obstruction or the reduced class and all lifts, with an independent substitution check. Next, the Chinese remainder theorem combines several congruences and explains both the coprime construction and compatibility when moduli share factors.
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Find the least positive inverse of 5 modulo 17.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
How many classes modulo 18 solve 6x≡12?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
List all solutions to 8x≡12 modulo 20.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove ax≡b modulo m is solvable exactly when d=gcd(a, m) divides b.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove the solvable congruence has exactly d solution classes modulo m.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
State the correct conclusion from ac≡bc modulo m when gcd(c, m)=d.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
