Linear Congruences: Solvability Conditions

Have you ever tried to solve a puzzle where some answers just do not fit the rules? In number theory, linear congruences work the same way. A linear congruence asks whether an equation like $ax \equiv b \pmod n$ has a solution, and if it does, how many solutions it has. In this lesson, students, you will learn the key idea behind solvability conditions: when a linear congruence can actually be solved, and when it cannot. 🧠✨

What a linear congruence means

A linear congruence has the form $ax \equiv b \pmod n$, where $a$, $b$, and $n$ are integers and $n>0$. This statement means that $ax$ and $b$ leave the same remainder when divided by $n$. Another way to say it is that $n$ divides the difference $ax-b$.

For example, $3x \equiv 4 \pmod 7$ means we are looking for integers $x$ such that $3x-4$ is divisible by $7$. If $x=6$, then $3(6)=18$, and $18-4=14$, which is divisible by $7$, so $x=6$ is a solution. If $x=1$, then $3(1)-4=-1$, which is not divisible by $7$, so $x=1$ is not a solution.

The big question in this lesson is not just “How do we solve it?” but “When is it possible to solve it at all?” That is the solvability condition. ✅

The central solvability condition

The most important rule is this:

A linear congruence $ax \equiv b \pmod n$ has a solution if and only if $\gcd(a,n)$ divides $b$.

Here, $\gcd(a,n)$ means the greatest common divisor of $a$ and $n$, the largest positive integer that divides both numbers.

Why does this matter? Think of $a$ and $n$ as creating a pattern of possible values. If $a$ and $n$ share a common factor, that factor limits which values of $ax$ can match $b$ modulo $n$. If $b$ does not fit that pattern, no solution exists.

Example where a solution exists

Consider $6x \equiv 8 \pmod {10}$.

First compute $\gcd(6,10)=2$. Since $2 \mid 8$, the congruence is solvable.

Now divide everything by $2$:

$$3x \equiv 4 \pmod 5$$

This simplified congruence has a solution because $\gcd(3,5)=1$, and $3$ is invertible modulo $5$. We can check values quickly: $x=3$ gives $3(3)=9 \equiv 4 \pmod 5$, so $x=3$ works. 🎯

Example where no solution exists

Consider $6x \equiv 7 \pmod {10}$.

Again, $\gcd(6,10)=2$. But $2 \nmid 7$, so the congruence has no solution.

This is a very important idea: sometimes the equation looks simple, but the arithmetic structure says “no solution.” That is what solvability conditions help us detect quickly.

Why the condition works

Let’s explore the reasoning behind the rule. Suppose $ax \equiv b \pmod n$ has a solution. Then by definition,

$$n \mid (ax-b).$$

If $d=\gcd(a,n)$, then $d$ divides both $a$ and $n$. Because $d$ divides $a$, it also divides $ax$. Because $d$ divides $n$ and $n$ divides $ax-b$, it follows that $d$ must divide $b$ as well. So a necessary condition for solvability is $d \mid b$.

The surprising part is that this condition is also sufficient. If $d \mid b$, then we can write $a=da_1$, $n=dn_1$, and $b=db_1$. The congruence becomes

$$da_1x \equiv db_1 \pmod {dn_1}.$$

Dividing through by $d$ gives

$$a_1x \equiv b_1 \pmod {n_1}.$$

Now $\gcd(a_1,n_1)=1$, so the reduced congruence always has a solution because $a_1$ has a multiplicative inverse modulo $n_1$. That is why the original congruence is solvable exactly when $\gcd(a,n)$ divides $b$.

This logic connects solvability conditions to the broader study of inverses modulo $n$. When $\gcd(a,n)=1$, the coefficient $a$ can be “undone” using its inverse. When $\gcd(a,n)>1$, the equation may still be solvable, but only if the right-hand side fits the divisibility rule.

How to test solvability step by step

When students sees a linear congruence like $ax \equiv b \pmod n$, use this procedure:

Compute $d=\gcd(a,n)$.
Check whether $d \mid b$.
If not, there is no solution.
If yes, divide the whole congruence by $d$ to get a simpler congruence.
Solve the reduced congruence, often by finding an inverse modulo the new modulus.

Worked example

Solve the solvability question for $14x \equiv 30 \pmod {42}$.

First, find $\gcd(14,42)=14$.

Now check whether $14 \mid 30$. It does not, because $30$ is not a multiple of $14$.

So the congruence has no solution. Even though the numbers are large, the test is quick once you know the rule. ⚡

Another worked example

Consider $14x \equiv 28 \pmod {42}$.

Here, $\gcd(14,42)=14$, and $14 \mid 28$, so solutions exist.

Divide by $14$:

$$x \equiv 2 \pmod 3$$

This means the solutions are all integers of the form

$$x=2+3k$$

for any integer $k$.

If you check: $14(2)=28$, and $28 \equiv 28 \pmod {42}$, so $x=2$ is a solution. Then $x=5$, $x=8$, and so on are also solutions because they differ by multiples of $3$.

How many solutions are there?

Solvability conditions tell us whether solutions exist, but they also lead to a counting rule.

If $d=\gcd(a,n)$ and $d \mid b$, then the congruence $ax \equiv b \pmod n$ has exactly $d$ incongruent solutions modulo $n$.

“Incongruent solutions” means solutions that are different modulo $n$. They are not just repeated versions of the same answer.

For example, consider

$$6x \equiv 8 \pmod {10}.$$

We found that $d=2$, so there should be exactly $2$ incongruent solutions modulo $10$.

We already found one solution, $x=3$. Another solution is $x=8$, because $6(8)=48 \equiv 8 \pmod {10}$. These two are not congruent modulo $10$ since $3 \not\equiv 8 \pmod {10}$.

This pattern is useful because it shows that solvability and solution count are connected. If the congruence is solvable, the gcd tells you how many distinct solution classes exist. 📌

Connection to reduced residue systems

A reduced residue system modulo $n$ is a list of integers that represent all numbers relatively prime to $n$, with no repeats modulo $n$. This idea matters because the invertible numbers modulo $n$ are exactly those with gcd $1$ with $n$.

When $\gcd(a,n)=1$, the congruence $ax \equiv b \pmod n$ always has a unique solution modulo $n$. That is because multiplication by $a$ permutes the reduced residue system modulo $n$.

For example, modulo $7$, the reduced residue system can be

$$\{1,2,3,4,5,6\}$$

because every nonzero class is relatively prime to $7$.

If you solve $3x \equiv 4 \pmod 7$, you can think of multiplying each residue by $3$ until you find the one that matches $4$. Since $3$ is relatively prime to $7$, it has an inverse modulo $7$, and the solution exists and is unique. This is the cleanest case of a linear congruence.

Common mistakes to avoid

A common mistake is assuming every linear congruence has a solution. That is false. Always check $\gcd(a,n)$ first.

Another mistake is dividing by a number without checking whether it is allowed. In ordinary algebra, dividing both sides by $2$ is usually fine. In modular arithmetic, you can only divide by a number if it is invertible modulo the modulus, or if you have first justified dividing by a common gcd.

For example, from $6x \equiv 8 \pmod {10}$, you cannot simply “cancel the $6$” because $6$ is not invertible modulo $10$. But you can divide the whole congruence by $2$, the common gcd of $6$ and $10$, because the divisibility condition is satisfied.

A final mistake is forgetting that a congruence can have more than one solution modulo $n$. A solvable linear congruence may have several incongruent solutions, not just one. 🔍

Conclusion

Solvability conditions are the gateway to solving linear congruences. The key rule is simple and powerful: $ax \equiv b \pmod n$ has a solution if and only if $\gcd(a,n) \mid b$. This criterion tells us quickly whether a problem is possible, how to simplify it, and how many solutions to expect.

This lesson connects directly to inverses modulo $n$ and reduced residue systems. If $\gcd(a,n)=1$, then $a$ has an inverse and the congruence has exactly one solution modulo $n$. If $\gcd(a,n)>1$, the congruence may still be solvable, but only when the right-hand side is compatible with that gcd. Knowing this helps students work smarter, not just harder, when solving number theory problems. ✅

Study Notes

A linear congruence has the form $ax \equiv b \pmod n$.
The meaning of $ax \equiv b \pmod n$ is that $n \mid (ax-b)$.
The solvability condition is: $ax \equiv b \pmod n$ has a solution if and only if $\gcd(a,n) \mid b$.
If $\gcd(a,n)$ does not divide $b$, there is no solution.
If $d=\gcd(a,n)$ divides $b$, divide the congruence by $d$ to get a simpler one.
When $\gcd(a,n)=1$, the coefficient $a$ has an inverse modulo $n$.
If a linear congruence is solvable and $d=\gcd(a,n)$, then there are exactly $d$ incongruent solutions modulo $n$.
Reduced residue systems help explain why numbers with gcd $1$ are invertible modulo $n$.
Always check solvability before trying to solve a congruence directly.
Solvability conditions are a core part of Linear Congruences in Number Theory.