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. /Congruences and their rules

Course 28.1·Lesson 1 of 3

Congruences and their rules

Two integers are congruent modulo mmm when mmm divides their difference, which means that they leave the same remainder on division by mmm. Congruences can be added, subtracted, multiplied and raised to powers like equations. Division is the exception: you may cancel a factor

Lesson 1 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

  • write and read the statement a≡b(modm)a \equiv b \pmod ma≡b(modm);
  • add, subtract, multiply and raise congruences to powers;
  • cancel a common factor correctly;
  • find the remainder of a large power or a large sum.

A clock already does it

A wall clock shows 333 at fifteen hundred hours. It shows 333 again twelve hours later. The clock forgets every full turn and keeps only the remainder. Number theory does the same on purpose.

Let mmm be a positive integer, called the modulus. We say that aaa is congruent to bbb modulo mmm, and we write

a≡b(modm),\displaystyle a \equiv b \pmod m,a≡b(modm),

when mmm divides a−ba - ba−b. For example 38≡3(mod7)38 \equiv 3 \pmod 738≡3(mod7), because 38−3=35=5×738 - 3 = 35 = 5 \times 738−3=35=5×7.

Why is this the same as "the same remainder"? Write a=qm+ra = qm + ra=qm+r and b=q′m+r′b = q'm + r'b=q′m+r′ with 0≤r,r′<m0 \le r, r' < m0≤r,r′<m. Then a−b=(q−q′)m+(r−r′)a - b = (q - q')m + (r - r')a−b=(q−q′)m+(r−r′). This is a multiple of mmm exactly when r−r′r - r'r−r′ is. Since ∣r−r′∣<m|r - r'| < m∣r−r′∣<m, that happens only when r=r′r = r'r=r′.

So every integer is congruent to exactly one of 0,1,…,m−10, 1, \dots, m - 10,1,…,m−1. These mmm numbers form a complete set of residues modulo mmm. Negative numbers fit too: −5≡2(mod7)-5 \equiv 2 \pmod 7−5≡2(mod7), since −5−2=−7-5 - 2 = -7−5−2=−7.

Notation. Books in India and elsewhere use the same sign ≡\equiv≡. Some books and every programming language also use "mod" as an operation: 38 mod 7=338 \bmod 7 = 338mod7=3, written 38 % 7 in Python. The statement a≡b(modm)a \equiv b \pmod ma≡b(modm) is a relation between two numbers. The operation gives one number, the remainder.

A clock face with seven hours, numbered 0 at the top and 1 to 6 clockwise. A red arc winds three full turns and then two more steps, ending on the hour 2. A note beside it says 23 = 3 times 7 + 2, so 23 is congruent to 2 modulo 7. Below, a row of the numbers 2, 9, 16, 23, 30 is shaded the same colour, because they all leave remainder 2 on division by 7.

The rules

Suppose a≡b(modm)a \equiv b \pmod ma≡b(modm) and c≡d(modm)c \equiv d \pmod mc≡d(modm). Then

  • a+c≡b+da + c \equiv b + da+c≡b+d and a−c≡b−d(modm)a - c \equiv b - d \pmod ma−c≡b−d(modm);
  • ac≡bd(modm)ac \equiv bd \pmod mac≡bd(modm);
  • ak≡bk(modm)a^k \equiv b^k \pmod mak≡bk(modm) for every whole number kkk;
  • f(a)≡f(b)(modm)f(a) \equiv f(b) \pmod mf(a)≡f(b)(modm) for every polynomial fff with integer coefficients.

Let us prove the product rule. We have ac−bd=a(c−d)+d(a−b)ac - bd = a(c - d) + d(a - b)ac−bd=a(c−d)+d(a−b). Both terms are multiples of mmm, so their sum is too. The power rule is the product rule used again and again, and the polynomial rule follows from the sum and power rules.

So you may replace any number by its remainder at any point of a calculation. This is the whole trick.

Dividing is different

Look at 14≡4(mod10)14 \equiv 4 \pmod{10}14≡4(mod10). Both sides are 2×2 \times2× something: 2×7≡2×2(mod10)2 \times 7 \equiv 2 \times 2 \pmod{10}2×7≡2×2(mod10). Is 7≡2(mod10)7 \equiv 2 \pmod{10}7≡2(mod10)? No.

The correct rule is this. If ac≡bc(modm)ac \equiv bc \pmod mac≡bc(modm) and d=gcd⁡(c,m)d = \gcd(c, m)d=gcd(c,m), then

a≡b(modmd).\displaystyle a \equiv b \pmod{\dfrac{m}{d}}.a≡b(moddm​).

Here d=2d = 2d=2, and indeed 7≡2(mod5)7 \equiv 2 \pmod 57≡2(mod5). In particular, when gcd⁡(c,m)=1\gcd(c, m) = 1gcd(c,m)=1 you may cancel ccc freely.

Proof. We know m∣(a−b)cm \mid (a - b)cm∣(a−b)c. Write m=dm′m = dm'm=dm′ and c=dc′c = dc'c=dc′, where gcd⁡(m′,c′)=1\gcd(m', c') = 1gcd(m′,c′)=1. Then m′∣(a−b)c′m' \mid (a - b)c'm′∣(a−b)c′, and since m′m'm′ shares no factor with c′c'c′, it divides a−ba - ba−b.

Remainders of large powers

Find the remainder of 72227^{222}7222 on division by 101010, which is its last digit.

  1. Look for a cycle. 71≡77^1 \equiv 771≡7, 72=49≡97^2 = 49 \equiv 972=49≡9, 73≡9×7=63≡37^3 \equiv 9 \times 7 = 63 \equiv 373≡9×7=63≡3, 74≡3×7=21≡1(mod10)7^4 \equiv 3 \times 7 = 21 \equiv 1 \pmod{10}74≡3×7=21≡1(mod10).
  2. Use 74≡17^4 \equiv 174≡1. Write 222=4×55+2222 = 4 \times 55 + 2222=4×55+2. Then 7222=(74)55⋅72≡155⋅49≡9(mod10)7^{222} = (7^4)^{55} \cdot 7^2 \equiv 1^{55} \cdot 49 \equiv 9 \pmod{10}7222=(74)55⋅72≡155⋅49≡9(mod10).
  3. Answer. The last digit is 999.

A small power that gives 111, or −1-1−1, is the key every time. For example 25=32≡−1(mod11)2^5 = 32 \equiv -1 \pmod{11}25=32≡−1(mod11), so 210≡1(mod11)2^{10} \equiv 1 \pmod{11}210≡1(mod11).

Divisibility tests

Every divisibility test is a congruence.

  • By 9 and by 3. Since 10≡1(mod9)10 \equiv 1 \pmod 910≡1(mod9), every power 10k≡110^k \equiv 110k≡1. So a number is congruent to the sum of its digits modulo 999, and also modulo 333.
  • By 11. Since 10≡−1(mod11)10 \equiv -1 \pmod{11}10≡−1(mod11), a number is congruent to the alternating sum of its digits, taken from the units digit.
  • By 7, 11 and 13 together. Since 1001=7×11×131001 = 7 \times 11 \times 131001=7×11×13, we have 1000≡−11000 \equiv -11000≡−1 for all three moduli. Split the number into blocks of three digits from the right and take the alternating sum of the blocks.

For example 123 456 789123\,456\,789123456789 gives 789−456+123=456789 - 456 + 123 = 456789−456+123=456. Since 456=65×7+1456 = 65 \times 7 + 1456=65×7+1, the number leaves remainder 111 on division by 777.

Squares modulo small numbers

A square is 000 or 111 modulo 444: an even number 2k2k2k gives 4k24k^24k2, and an odd number 2k+12k + 12k+1 gives 4k2+4k+14k^2 + 4k + 14k2+4k+1. Modulo 888 an odd square is always 111, because 4k(k+1)4k(k + 1)4k(k+1) is a multiple of 888.

So a sum of two squares is 000, 111 or 222 modulo 444, never 333. The number 4 000 0034\,000\,0034000003 is not a sum of two squares, and we did not try a single pair.

Practise with new numbers

Try it in Python

The program shows the remainder operator %, a cycle of last digits and the two digit tests. The last line uses pow(a, k, m), which finds the remainder of a power without making the big number.

Read it first. Then run it. Do the two numbers on each test line agree?

1. Change n = 987654 to any number you like. Do the tests still agree?

2. Change the cycle to the powers of 3 modulo 10. How long is the cycle now?

Common mistakes

  • Cancelling without the gcd. From 6≡16(mod10)6 \equiv 16 \pmod{10}6≡16(mod10) you may not conclude 3≡8(mod10)3 \equiv 8 \pmod{10}3≡8(mod10). Divide the modulus by gcd⁡(2,10)=2\gcd(2, 10) = 2gcd(2,10)=2: 3≡8(mod5)3 \equiv 8 \pmod 53≡8(mod5).
  • Reducing the exponent by mmm. a≡ba \equiv ba≡b lets you replace the base, never the exponent. 2122^{12}212 is not 222^222 modulo 101010.
  • Forgetting negative remainders. −1-1−1 is often the easiest remainder to use. 10≡−1(mod11)10 \equiv -1 \pmod{11}10≡−1(mod11) is the whole test by 111111.
  • Mixing up the relation and the operation. a≡b(modm)a \equiv b \pmod ma≡b(modm) is true or false. The remainder a mod ma \bmod mamodm is a number from 000 to m−1m - 1m−1.

Remember these

  • a≡b(modm)a \equiv b \pmod ma≡b(modm) means m∣a−bm \mid a - bm∣a−b, the same remainder.
  • Add, subtract, multiply and take powers freely.
  • Cancel ccc only after dividing the modulus by gcd⁡(c,m)\gcd(c, m)gcd(c,m).
  • Look for a small power congruent to 111 or −1-1−1.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Is −17≡13(mod6)-17 \equiv 13 \pmod 6−17≡13(mod6)?
  1. Find the last digit of 3453^{45}345.
  1. From 15x≡25(mod35)15x \equiv 25 \pmod{35}15x≡25(mod35) a student cancels 555 and writes 3x≡5(mod35)3x \equiv 5 \pmod{35}3x≡5(mod35). What should the result be?
  1. Find the remainder of 5205^{20}520 on division by 131313.
  1. Can n2+2n^2 + 2n2+2 be a multiple of 444 for an integer nnn?

References

  • David M. Burton, Elementary Number Theory, Chapter 4, The Theory of 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 (4)

A puzzle card asks for two remainders without a calculator…Hard · High School (11–12) · by StemPy Lab
Show that n⁵ - n is a multiple of 30 for every integer n…Hard · High School (11–12) · by StemPy Lab
A number theorist wants to prove that no integer of the form 8k + 7 is a sum of three squares of…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 2Linear congruences and inverses
← Congruences and the Chinese Remainder Theorem
← PreviousLinear congruences and inverses →

Discussion (0)

Log in to join the discussion.

Loading…

ccc
only if you divide the modulus by
gcd⁡(c,m)\gcd(c, m)gcd(c,m)
. Congruences prove divisibility tests and find the remainders of huge powers.
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.

A twelve-digit serial number is N = 123 456 789 123…Hard · High School (11–12) · by StemPy Lab

Python Labs (1)

Fast powers modulo mPython Lab · by StemPy Lab