HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Congruences and the Chinese Remainder Theorem
  1. 1Congruences and their rules
  2. 2Linear congruences and inverses
  3. 3The Chinese remainder theorem
  1. Mathematics
  2. /Congruences and the Chinese Remainder Theorem
  3. /Linear congruences and inverses

Course 28.1·Lesson 2 of 3

Linear congruences and inverses

A linear congruence ax≡b(modm)ax \equiv b \pmod max≡b(modm) has a solution exactly when

Lesson 2 of 3Show all lessonsHide
Congruences and the Chinese Remainder Theorem
  1. 1Congruences and their rules
  2. 2Linear congruences and inverses
  3. 3The Chinese remainder theorem

Try the code and the simulations beside the lesson.

What you will be able to do

  • decide whether ax≡b(modm)ax \equiv b \pmod max≡b(modm) has a solution, and count the solutions;
  • find the inverse of aaa modulo mmm with the extended Euclidean algorithm;
  • solve a linear congruence by dividing through by the gcd.

A congruence with an unknown

A frog jumps 666 stones at a time round a ring of 101010 stones, numbered 000 to 999. It starts at stone 000. Can it ever land on stone 444? On stone 555?

After xxx jumps the frog is on stone 6x mod 106x \bmod 106xmod10. We want 6x≡4(mod10)6x \equiv 4 \pmod{10}6x≡4(mod10) and 6x≡5(mod10)6x \equiv 5 \pmod{10}6x≡5(mod10). Every 6x6x6x is even, and so is every number 10k10k10k added to it. So stone 555 is never reached. Stone 444 is reached at x=4x = 4x=4, since 24≡424 \equiv 424≡4, and also at x=9x = 9x=9, since 54≡454 \equiv 454≡4.

When is there a solution?

The congruence ax≡b(modm)ax \equiv b \pmod max≡b(modm) means ax−b=myax - b = myax−b=my for some integer yyy, that is

ax−my=b.\displaystyle ax - my = b.ax−my=b.

You met this equation in the chapter on divisibility. Bezout's identity says that the numbers ax−myax - myax−my are exactly the multiples of d=gcd⁡(a,m)d = \gcd(a, m)d=gcd(a,m). So:

  • if d∤bd \nmid bd∤b, there is no solution;
  • if d∣bd \mid bd∣b, there are exactly ddd solutions modulo mmm.

To find them, divide everything by ddd:

ad x≡bd(modmd).\displaystyle \dfrac{a}{d}\,x \equiv \dfrac{b}{d} \pmod{\dfrac{m}{d}}.da​x≡db​(moddm​).

Now gcd⁡(ad,md)=1\gcd\big(\tfrac{a}{d}, \tfrac{m}{d}\big) = 1gcd(da​,dm​)=1, and there is one solution x0x_0x0​ modulo md\tfrac{m}{d}dm​. Modulo mmm this gives the ddd solutions x0, x0+md, …, x0+(d−1)mdx_0,\ x_0 + \tfrac{m}{d},\ \dots,\ x_0 + (d - 1)\tfrac{m}{d}x0​, x0​+dm​, …, x0​+(d−1)dm​.

For the frog, d=gcd⁡(6,10)=2d = \gcd(6, 10) = 2d=gcd(6,10)=2 divides 444. Dividing gives 3x≡2(mod5)3x \equiv 2 \pmod 53x≡2(mod5), so x≡4(mod5)x \equiv 4 \pmod 5x≡4(mod5), and modulo 101010 the solutions are 444 and 999.

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\gcd(a, m) = 1gcd(a,m)=1, there is a number a−1a^{-1}a−1 with a⋅a−1≡1(modm)a \cdot a^{-1} \equiv 1 \pmod ma⋅a−1≡1(modm). It is called the inverse of aaa modulo mmm. Then ax≡bax \equiv bax≡b gives x≡a−1bx \equiv a^{-1}bx≡a−1b.

The extended Euclidean algorithm finds it. Take the inverse of 171717 modulo 434343.

  1. Divide. 43=2×17+943 = 2 \times 17 + 943=2×17+9, then 17=1×9+817 = 1 \times 9 + 817=1×9+8, then 9=1×8+19 = 1 \times 8 + 19=1×8+1.
  2. Work back. 1=9−8=9−(17−9)=2×9−17=2(43−2×17)−17=2×43−5×171 = 9 - 8 = 9 - (17 - 9) = 2 \times 9 - 17 = 2(43 - 2 \times 17) - 17 = 2 \times 43 - 5 \times 171=9−8=9−(17−9)=2×9−17=2(43−2×17)−17=2×43−5×17.
  3. Read off. Modulo 434343 this says −5×17≡1-5 \times 17 \equiv 1−5×17≡1. So 17−1≡−5≡38(mod43)17^{-1} \equiv -5 \equiv 38 \pmod{43}17−1≡−5≡38(mod43).

Check: 17×38=646=15×43+117 \times 38 = 646 = 15 \times 43 + 117×38=646=15×43+1. To solve 17x≡5(mod43)17x \equiv 5 \pmod{43}17x≡5(mod43), multiply by 383838: x≡190≡18(mod43)x \equiv 190 \equiv 18 \pmod{43}x≡190≡18(mod43).

For a small modulus you can also search: the inverse of 333 modulo 777 is 555, because 15≡115 \equiv 115≡1.

Numbers with no inverse

If gcd⁡(a,m)>1\gcd(a, m) > 1gcd(a,m)>1, then aaa has no inverse. For example 4x≡1(mod6)4x \equiv 1 \pmod 64x≡1(mod6) asks for 4x−14x - 14x−1 to be a multiple of 666, but 4x−14x - 14x−1 is odd. This is why prime moduli are so pleasant: modulo a prime ppp, every number from 111 to p−1p - 1p−1 has an inverse.

A worked example

Solve 21x≡14(mod91)21x \equiv 14 \pmod{91}21x≡14(mod91).

  1. The gcd. gcd⁡(21,91)=7\gcd(21, 91) = 7gcd(21,91)=7, and 7∣147 \mid 147∣14. So there are 777 solutions modulo 919191.
  2. Divide by 7. 3x≡2(mod13)3x \equiv 2 \pmod{13}3x≡2(mod13).
  3. Invert 3. 3×9=27≡1(mod13)3 \times 9 = 27 \equiv 1 \pmod{13}3×9=27≡1(mod13), so x≡9×2=18≡5(mod13)x \equiv 9 \times 2 = 18 \equiv 5 \pmod{13}x≡9×2=18≡5(mod13).
  4. List them. Modulo 919191: x≡5,18,31,44,57,70,83x \equiv 5, 18, 31, 44, 57, 70, 83x≡5,18,31,44,57,70,83.

Check. 21×5=105=91+1421 \times 5 = 105 = 91 + 1421×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 171717 modulo 434343 in two ways and solves the congruence.

Read it first. Then run it. Does the check line print 111?

1. Change a, b, m = 17, 5, 43 to a, b, m = 12, 7, 30. What goes wrong, and why?

2. In the last line, change 4 to 5. Explain the empty list.

Common mistakes

  • Dividing by aaa as a fraction. ba\dfrac{b}{a}ab​ is not an integer in general. Multiply by the inverse instead.
  • Dividing aaa and bbb by ddd but not mmm. All three must be divided.
  • Giving one solution when there are ddd. Modulo mmm there are ddd different answers.
  • Looking for an inverse that cannot exist. No inverse exists when gcd⁡(a,m)>1\gcd(a, m) > 1gcd(a,m)>1.

Remember these

  • ax≡b(modm)ax \equiv b \pmod max≡b(modm) is solvable exactly when gcd⁡(a,m)∣b\gcd(a, m) \mid bgcd(a,m)∣b.
  • Then it has gcd⁡(a,m)\gcd(a, m)gcd(a,m) solutions modulo mmm.
  • The inverse of aaa modulo mmm exists exactly when gcd⁡(a,m)=1\gcd(a, m) = 1gcd(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.

  1. Does 9x≡6(mod15)9x \equiv 6 \pmod{15}9x≡6(mod15) have a solution? How many modulo 151515?
  1. Find the inverse of 555 modulo 121212.
  1. Solve 8x≡3(mod11)8x \equiv 3 \pmod{11}8x≡3(mod11).
  1. Why has 10x≡3(mod25)10x \equiv 3 \pmod{25}10x≡3(mod25) no solution?
  1. Find the inverse of 111111 modulo 262626 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.
No payment. You can leave at any time.

Problems (3)

A machine prints a code x from 0 to 37 that must satisfy 14x ≡ 22 pmod38…Hard · High School (11–12) · by StemPy Lab
A ring has 89 cells, numbered 0 to 88 clockwise…Advanced · High School (11–12) · by StemPy Lab
Prove the cancellation rule: if ac ≡ bc pmod m and d = gcd(c, m), then a ≡ b pmodm/d…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 3The Chinese remainder theorem
← Congruences and the Chinese Remainder Theorem
← Congruences and their rulesThe Chinese remainder theorem →

Discussion (0)

Log in to join the discussion.

Loading…

d=gcd⁡(a,m)d = \gcd(a, m)d=gcd(a,m)
divides
bbb
, and then it has exactly
ddd
solutions modulo
mmm
. When
gcd⁡(a,m)=1\gcd(a, m) = 1gcd(a,m)=1
the number
aaa
has an inverse modulo
mmm
, found with the extended Euclidean algorithm. Multiplying by the inverse is how you divide modulo
mmm
.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.