Two integers are congruent modulo m when m divides their difference, which means that they leave the same remainder on division by m. 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
Try the code and the simulations beside the lesson.
What you will be able to do
write and read the statement a≡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 3 at fifteen hundred hours. It shows 3 again twelve hours later. The clock forgets every full turn and keeps only the remainder. Number theory does the same on purpose.
Let m be a positive integer, called the modulus. We say that a is congruent to b modulo m, and we write
a≡b(modm),
when m divides a−b. For example 38≡3(mod7), because 38−3=35=5×7.
Why is this the same as "the same remainder"? Write a=qm+r and b=q′m+r′ with 0≤r,r′<m. Then a−b=(q−q′)m+(r−r′). This is a multiple of m exactly when r−r′ is. Since ∣r−r′∣<m, that happens only when r=r′.
So every integer is congruent to exactly one of 0,1,…,m−1. These m numbers form a complete set of residues modulo m. Negative numbers fit too: −5≡2(mod7), since −5−2=−7.
Notation. Books in India and elsewhere use the same sign ≡. Some books and every programming language also use "mod" as an operation: 38mod7=3, written 38 % 7 in Python. The statement a≡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) and c≡d(modm). Then
a+c≡b+d and a−c≡b−d(modm);
ac≡bd(modm);
ak≡bk(modm) for every whole number k;
f(a)≡f(b)(modm) for every polynomial f with integer coefficients.
Let us prove the product rule. We have ac−bd=a(c−d)+d(a−b). Both terms are multiples of m, 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). Both sides are 2× something: 2×7≡2×2(mod10). Is 7≡2(mod10)? No.
The correct rule is this. If ac≡bc(modm) and d=gcd(c,m), then
a≡b(moddm).
Here d=2, and indeed 7≡2(mod5). In particular, when gcd(c,m)=1 you may cancel c freely.
Proof. We know m∣(a−b)c. Write m=dm′ and c=dc′, where gcd(m′,c′)=1. Then m′∣(a−b)c′, and since m′ shares no factor with c′, it divides a−b.
Remainders of large powers
Find the remainder of 7222 on division by 10, which is its last digit.
Look for a cycle.71≡7, 72=49≡9, 73≡9×7=63≡3, 74≡3×7=21≡1(mod10).
Use 74≡1. Write 222=4×55+2. Then 7222=(74)55⋅72≡155⋅49≡9(mod10).
Answer. The last digit is 9.
A small power that gives 1, or −1, is the key every time. For example 25=32≡−1(mod11), so 210≡1(mod11).
Divisibility tests
Every divisibility test is a congruence.
By 9 and by 3. Since 10≡1(mod9), every power 10k≡1. So a number is congruent to the sum of its digits modulo 9, and also modulo 3.
By 11. Since 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×13, we have 1000≡−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 123456789 gives 789−456+123=456. Since 456=65×7+1, the number leaves remainder 1 on division by 7.
Squares modulo small numbers
A square is 0 or 1 modulo 4: an even number 2k gives 4k2, and an odd number 2k+1 gives 4k2+4k+1. Modulo 8 an odd square is always 1, because 4k(k+1) is a multiple of 8.
So a sum of two squares is 0, 1 or 2 modulo 4, never 3. The number 4000003 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.
Common mistakes
Cancelling without the gcd. From 6≡16(mod10) you may not conclude 3≡8(mod10). Divide the modulus by gcd(2,10)=2: 3≡8(mod5).
Reducing the exponent by m.a≡b lets you replace the base, never the exponent. 212 is not 22 modulo 10.
Forgetting negative remainders.−1 is often the easiest remainder to use. 10≡−1(mod11) is the whole test by 11.
Mixing up the relation and the operation.a≡b(modm) is true or false. The remainder amodm is a number from 0 to m−1.
Remember these
a≡b(modm) means m∣a−b, the same remainder.
Add, subtract, multiply and take powers freely.
Cancel c only after dividing the modulus by gcd(c,m).
Look for a small power congruent to 1 or −1.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Is −17≡13(mod6)?
Find the last digit of 345.
From 15x≡25(mod35) a student cancels 5 and writes 3x≡5(mod35). What should the result be?
Find the remainder of 520 on division by 13.
Can n2+2 be a multiple of 4 for an integer n?
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.