Back to the on-screen lesson ·
When one equation modulo a number has no solution, one, or several — decided by a greatest common divisor before any solving.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to decide whether $ax \equiv b \pmod n$ has a solution by testing whether the greatest common divisor of the coefficient and the modulus divides the right-hand side, say how many solutions there are and how far apart they lie, reduce the congruence and lift the reduced solution back to every solution of the original, and explain why the solution set is a set of evenly spaced residues rather than a single one.
Lesson 3 said the integer combinations of $a$ and $n$ are exactly the multiples of $\gcd(a, n)$. Lesson 7 said $a$ has an inverse modulo $n$ exactly when that gcd is $1$.
The first of those is more general than the second, and this lesson is what it gives when the gcd is not $1$. A congruence $ax \equiv b \pmod n$ says $ax - b$ is a multiple of $n$, that is $ax + ny = b$ for some $y$ — so the congruence is solvable exactly when $b$ is one of those integer combinations, and that is exactly when the gcd divides $b$.
A linear congruence is $ax \equiv b \pmod n$ with $a$, $b$, $n$ given and $x$ unknown. It is solvable when some integer satisfies it.
Solutions are counted modulo $n$: $x$ and $x + n$ are the same solution. So the count is between $0$ and $n$, and the question how many solutions always means how many residue classes.
Reducing the congruence means dividing $a$, $b$ and the modulus $n$ all by $d = \gcd(a, n)$. Lifting is the reverse move: turning the one solution of the reduced congruence into the $d$ solutions of the original, by adding $n/d$ repeatedly.
Theorem. Let $d = \gcd(a, n)$. Then $ax \equiv b \pmod n$ has a solution if and only if $d \mid b$; and when it does, it has exactly $d$ solutions modulo $n$, spaced $n/d$ apart.
Solvability. The congruence says $ax + ny = b$ for some integer $y$. The left side ranges over exactly the multiples of $d$, so the equation is solvable exactly when $d \mid b$.
Count. Write $a = da'$, $b = db'$, $n = dn'$. Dividing through, $a'x \equiv b' \pmod{n'}$, and now $\gcd(a', n') = 1$, so $a'$ is a unit and there is exactly one solution $x_0$ modulo $n'$. Back at modulus $n$, the residues congruent to $x_0$ modulo $n'$ are $$x_0,\; x_0 + n',\; x_0 + 2n',\; \ldots,\; x_0 + (d-1)n',$$ which is $d$ of them.
The only division performed is by $d$, and it divides all three of $a$, $b$ and $n$ — the modulus included. Forgetting to divide the modulus is the single commonest error here, and it produces a count that is right and solutions that are wrong.
The three outcomes. No solutions, when $d \nmid b$. Exactly one, when $d = 1$. Several — namely $d$ of them — otherwise. There is no other possibility, and which one holds is known after one run of Euclid's algorithm, before any solving.
That is the shape of the whole subject in miniature: a structural question answered by a gcd, and only then a computation.
Another way: steps
Another way: example
$6x \equiv 9 \pmod{15}$. $d = \gcd(6, 15) = 3$, and $3 \mid 9$, so there are three solutions. Divide by $3$: $2x \equiv 3 \pmod 5$. Since $2^{-1} \equiv 3 \pmod 5$, $x \equiv 9 \equiv 4 \pmod 5$. Lift: $x \equiv 4, 9, 14 \pmod{15}$. Check the last: $6 \cdot 14 = 84 = 5 \cdot 15 + 9$.
An ordinary linear equation over the rationals has one solution. A linear congruence can have none or many, and it is worth being clear about why, because the reason is structural rather than arithmetic.
Multiplication by $a$ is a map from $\mathbb{Z}_n$ to itself. When $\gcd(a, n) = 1$ that map is a bijection — it permutes the $n$ residues — so every $b$ is hit exactly once and every congruence has exactly one solution. When $d = \gcd(a, n) > 1$ the map is not injective: $a \cdot (n/d) = (a/d) \cdot n \equiv 0$, so $0$ and $n/d$ have the same image, and the map collapses the residues into groups of $d$.
A map that collapses $d$-to-$1$ has an image of size $n/d$ — the multiples of $d$ — and every value it does hit, it hits $d$ times. That is the theorem, read off the picture: $b$ must be a multiple of $d$ to be in the image at all, and if it is, there are $d$ preimages.
The same picture explains the spacing. The solutions differ by elements of the kernel, the residues $x$ with $ax \equiv 0$, which are exactly the multiples of $n/d$. So the solution set is a coset of the kernel: one solution plus everything the kernel contains.
This is the first place in the course where the answer to a concrete question is a coset rather than a number, and recognising the shape is worth more than the formula. The Chinese remainder theorem in the next lesson is the same observation for several moduli at once, and the same language describes it.
Dividing the coefficient but not the modulus. From $6x \equiv 9 \pmod{15}$ to $2x \equiv 3 \pmod{15}$ is wrong; the modulus divides by $3$ too. The resulting congruence has no solutions and the error looks like a proof of unsolvability.
Reporting one solution when there are several. When $d > 1$ the answer is $d$ residues. Giving only the smallest is giving a fraction of the answer, and it is the fraction an automatic checker most often accepts by accident.
Spacing the solutions by $d$. They are spaced by $n/d$. For $6x \equiv 9 \pmod{15}$ the gap is $5$, not $3$.
Searching before testing. Trying values of $x$ can confirm a solution but can never establish there is none until every residue has been tried. The gcd test settles it in one run of Euclid.
Assuming the count depends on $b$. It does not. $b$ decides whether there are any solutions; the count, once there are, is $\gcd(a, n)$ whatever $b$ is.
$12x \equiv 8 \pmod{18}$. Compute $d = \gcd(12, 18) = 6$.
The gcd before anything else.
$6 \nmid 8$, so there is no solution — and nothing further needs doing.
One divisibility test replaces eighteen substitutions.
The reason, if it helps: $12x$ is always a multiple of $6$ and so is $18$, so $12x - 8$ is $8$ short of a multiple of $6$, which no multiple of $18$ can be.
The structural reason and the test are the same fact.
Modulo $12$ with coefficient $8$: $d = \gcd(8, 12) = 4$, so solutions exist exactly when $4 \mid b$, and there are then four of them.
The count is fixed before $b$ is named.
$8x \equiv 4 \pmod{12}$: divide by $4$ to get $2x \equiv 1 \pmod 3$, so $x \equiv 2 \pmod 3$, lifting to $x \equiv 2, 5, 8, 11 \pmod{12}$.
Four solutions, spaced by $12/4 = 3$.
$8x \equiv 6 \pmod{12}$ has none, since $4 \nmid 6$; $8x \equiv 8 \pmod{12}$ has four, namely $1, 4, 7, 10$. Same map, three different fibres.
Changing $b$ changes everything or nothing, never the count.
$d = \gcd(10, 35) = 5$, so solutions exist exactly when $5 \mid b$.
The condition is on $b$ alone.
When $5 \mid b$ there are $5$ solutions modulo $35$, spaced $35/5 = 7$ apart.
The count and the spacing come from the same gcd.
For instance $b = 15$: divide by $5$ to get $2x \equiv 3 \pmod 7$, and $2^{-1} \equiv 4$, so $x \equiv 12 \equiv 5 \pmod 7$, lifting to $5, 12, 19, 26, 33$.
Solve $15x \equiv 9 \pmod{24}$. There are three solutions in the range $0$ to $24 - 1$; give them in increasing order.
| Value | |
|---|---|
| Smallest solution | |
| Next | |
| Next |
$21x \equiv b \pmod{24}$ is solvable for a certain $b$. How many solutions does it then have modulo $24$?
Answer:
Is $10x \equiv 15 \pmod{25}$ solvable?
Give the set of solutions of $3x \equiv 21 \pmod{30}$ lying in the range $0$ to $30 - 1$, as a set of separate values.
This task has no paper form; do it on a device.
Solve $7x \equiv 3 \pmod{16}$. Give the inverse of the coefficient and the solution, both as least residues.
inverse a, solution c
You are handed $6x \equiv b \pmod{27}$ with $b$ unknown. Put the steps of solving it into the order you carry them out.
Number the steps in order (write the number in the box):
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Solve $15x \equiv 9 \pmod{24}$. There are three solutions in the range $0$ to $24 - 1$; give them in increasing order.
| Value | |
|---|---|
| Smallest solution | |
| Next | |
| Next |
You can decide, count and find the solutions of any linear congruence. Say in your own words why the modulus must be divided along with the coefficient, and what the spacing between the solutions is. Next: several congruences at once.
9. Your turn: for which $b$ does $10x \equiv b \pmod{35}$ have a solution, and how many?, step 3