A linear congruence ax≡b(modm) has a solution exactly when
Lesson 2 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
decide whether ax≡b(modm) has a solution, and count the solutions;
find the inverse of a modulo m with the extended Euclidean algorithm;
solve a linear congruence by dividing through by the gcd.
A congruence with an unknown
A frog jumps 6 stones at a time round a ring of 10 stones, numbered 0 to 9. It starts at stone 0. Can it ever land on stone 4? On stone 5?
After x jumps the frog is on stone 6xmod10. We want 6x≡4(mod10) and 6x≡5(mod10). Every 6x is even, and so is every number 10k added to it. So stone 5 is never reached. Stone 4 is reached at x=4, since 24≡4, and also at x=9, since 54≡4.
When is there a solution?
The congruence ax≡b(modm) means ax−b=my for some integer y, that is
ax−my=b.
You met this equation in the chapter on divisibility. Bezout's identity says that the numbers ax−my are exactly the multiples of d=gcd(a,m). So:
if d∤b, there is no solution;
if d∣b, there are exactly d solutions modulo m.
To find them, divide everything by d:
dax≡db(moddm).
Now gcd(da,dm)=1, and there is one solution x0 modulo dm. Modulo m this gives the d solutions x0,x0+dm,…,x0+(d−1)dm.
For the frog, d=gcd(6,10)=2 divides 4. Dividing gives 3x≡2(mod5), so x≡4(mod5), and modulo 10 the solutions are 4 and 9.
Two dot plots side by side, each with x from 0 to 9 across and the remainder of a times x on division by 10 upwards. On the left, a = 3: the ten dots hit every height from 0 to 9 once, and the dot at height 4 sits above x = 8. On the right, a = 6: the dots only reach the even heights 0, 2, 4, 6, 8, each twice, and the two dots at height 4 sit above x = 4 and x = 9. A dashed line at height 4 crosses both plots.
Inverses
When gcd(a,m)=1, there is a number a−1 with a⋅a−1≡1(modm). It is called the inverse of a modulo m. Then ax≡b gives x≡a−1b.
The extended Euclidean algorithm finds it. Take the inverse of 17 modulo 43.
Divide.43=2×17+9, then 17=1×9+8, then 9=1×8+1.
Work back.1=9−8=9−(17−9)=2×9−17=2(43−2×17)−17=2×43−5×17.
Read off. Modulo 43 this says −5×17≡1. So 17−1≡−5≡38(mod43).
Check: 17×38=646=15×43+1. To solve 17x≡5(mod43), multiply by 38: x≡190≡18(mod43).
For a small modulus you can also search: the inverse of 3 modulo 7 is 5, because 15≡1.
Numbers with no inverse
If gcd(a,m)>1, then a has no inverse. For example 4x≡1(mod6) asks for 4x−1 to be a multiple of 6, but 4x−1 is odd. This is why prime moduli are so pleasant: modulo a prime p, every number from 1 to p−1 has an inverse.
A worked example
Solve 21x≡14(mod91).
The gcd.gcd(21,91)=7, and 7∣14. So there are 7 solutions modulo 91.
Divide by 7.3x≡2(mod13).
Invert 3.3×9=27≡1(mod13), so x≡9×2=18≡5(mod13).
List them. Modulo 91: x≡5,18,31,44,57,70,83.
Check.21×5=105=91+14. It works.
Practise with new numbers
Try it in Python
The program runs the extended Euclidean algorithm, finds the inverse of 17 modulo 43 in two ways and solves the congruence.
Common mistakes
Dividing by a as a fraction.ab is not an integer in general. Multiply by the inverse instead.
Dividing a and b by d but not m. All three must be divided.
Giving one solution when there are d. Modulo m there are d different answers.
Looking for an inverse that cannot exist. No inverse exists when gcd(a,m)>1.
Remember these
ax≡b(modm) is solvable exactly when gcd(a,m)∣b.
Then it has gcd(a,m) solutions modulo m.
The inverse of a modulo m exists exactly when gcd(a,m)=1.
The extended Euclidean algorithm finds the inverse.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Does 9x≡6(mod15) have a solution? How many modulo 15?
Find the inverse of 5 modulo 12.
Solve 8x≡3(mod11).
Why has 10x≡3(mod25) no solution?
Find the inverse of 11 modulo 26 with the Euclidean algorithm.
References
David M. Burton, Elementary Number Theory, Chapter 4, section on linear congruences.
Enroll free in Congruences and the Chinese Remainder Theorem
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.