Number theory · laboratory
From clocks to congruences, from power cycles to the Chinese remainder theorem.
A 12-hour clock does not stop at 12: five hours after 10, it shows 3. This laboratory uses that idea to explore remainders, divisibility and increasingly rich problems. Open “Why does it work?” at each step, then try the tools.
Step 1 / 15
After a full turn, we return to the same point. Only the distance beyond complete turns matters.
10+5=15 ≡ 3 (mod 12)
Example: 17, 29 and 41 all leave remainder 5 on division by 12.
The differences between these numbers are multiples of 12: the number of turns changes, but not the position.
Step 2 / 15
Two integers are congruent when they belong to the same residue class.
a ≡ b (mod n) ⇔ n divides a−b
Example: 23 ≡ 3 (mod 10), because 23−3=20.
If a−b=kn, then a and b differ by k complete turns of size n.
Step 3 / 15
Use Euclidean division and always choose a nonnegative remainder.
a=nq+r, 0≤r<n
Example: −17=5×(−4)+3, so −17 mod 5=3.
The quotient can be negative; the condition 0≤r<n makes the remainder unique. Modulo 1, it is always 0.
Step 4 / 15
We may reduce each term before adding or subtracting.
a≡b, c≡d ⇒ a±c≡b±d (mod n)
Example: 17+29 ≡ 5+5 ≡ 10 (mod 12).
The sum or difference of multiples of n is again a multiple of n.
Step 5 / 15
Multiplication also preserves congruence.
a≡b, c≡d ⇒ ac≡bd (mod n)
Example: 123×456 mod 7 = 4×1 mod 7 = 4.
If a=b+kn and c=d+hn, the difference ac−bd contains n as a factor.
Step 6 / 15
Powers visit finitely many residues, so eventually a residue repeats.
7¹,7²,7³,7⁴ ≡ 7,9,3,1 (mod 10)
Example: 2026 mod 4=2, so the last digit of 7^2026 is 9.
Once a state repeats, multiplication by the same base reproduces the path. Some cycles have a preperiod.
Step 7 / 15
The last decimal digit is simply the residue modulo 10.
last digit of a^b = a^b mod 10
Example: 3^25: cycle 3,9,7,1; 25 mod 4=1, so the digit is 3.
Two integers have the same last digit exactly when they are congruent modulo 10.
Step 8 / 15
Use modulo 100 for the last two digits and always write two characters.
last two digits of a^b = a^b mod 100
Example: 3^100 mod 100=1, so the last two digits are 01.
Repeated squaring avoids constructing the enormous power.
Step 9 / 15
Each decimal place is a power of 10; replace 10 with its residue.
10≡1 (mod 9); 10≡−1 (mod 11)
Example: For 5724 the digit sum is 18, so it is divisible by 9. For 11, 2728 gives 2−7+2−8=−11, so it is divisible by 11.
Modulo 9 every power of 10 is 1; modulo 11 they alternate between 1 and −1.
Step 10 / 15
Hours cycle modulo 12 or 24; weekdays cycle modulo 7.
22+17≡15 (mod 24); 100≡2 (mod 7)
Example: One hundred days after Monday is Wednesday.
Each full cycle returns the indicator to its starting position.
Step 11 / 15
The equation ax≡b (mod n) may have no solution, one solution or several.
d=GCD(a,n); solutions exist ⇔ d divides b
Example: 6x≡4 (mod 8): d=2 and the solutions are 2 and 6.
Divide by d to get one solution modulo n/d; this yields d classes modulo n.
Step 12 / 15
The inverse of a is a number whose product with a has residue 1.
a⁻¹ exists (mod n) ⇔ GCD(a,n)=1, n>1
Example: 7×3=21≡1 (mod 10), hence 7⁻¹≡3.
Bézout’s identity expresses 1 as a combination of a and n exactly when their GCD is 1.
Step 13 / 15
Find one integer satisfying several remainder conditions at once.
x≡2 (mod 3); x≡3 (mod 5)
Example: The smallest positive solution is x=8.
From the first condition x=2+3t; substituting into the second gives t≡2 (mod 5).
Step 14 / 15
With pairwise coprime moduli there is one solution class modulo their product.
x≡2 (mod 3), x≡3 (mod 5), x≡2 (mod 7) ⇒ x≡23 (mod 105)
Example: Dividing 23 by 3, 5 and 7 leaves 2, 3 and 2 respectively.
Each new congruence fixes the parameter in the previous solution; coprimality makes this possible and unique.
Step 15 / 15
Remainders become tools for final digits, impossible squares, clock puzzles and systems.
7^(7^7) mod 10: first reduce the exponent modulo 4
Example: 7^7≡3 (mod 4), so the last digit of 7^(7^7) is 3.
A huge question breaks into smaller, nested moduli. The 25 challenges below let you practise.
Enter integers. The modulus must be positive; modulo 1 is allowed for remainders, but it has no modular inverse.
Compare all squares or cubes modulo n (up to 60) and observe the distinct residues.
Answer before opening a hint or solution. Attempts and solved problems are stored only in this browser, even when you switch languages.
1 / 25 · Easy
Compute 37 mod 5.
How many times does 5 fit into 37?
2 / 25 · Easy
Is 47≡5 (mod 7) true? Answer yes or no.
Subtract 5 from 47.
3 / 25 · Easy
It is 9 o’clock. What time will it be in 17 hours on a 12-hour clock?
Add, then remove full turns of 12.
4 / 25 · Easy
Today is Monday. What day will it be in 100 days?
Reduce 100 modulo 7.
5 / 25 · Easy
What is the last digit of 3^25?
The cycle modulo 10 is 3,9,7,1.
6 / 25 · Easy
What is the last digit of 7^2026?
The cycle is 7,9,3,1.
7 / 25 · Easy
Is 123456789 divisible by 9? Answer yes or no.
Add the digits.
8 / 25 · Medium
Is 2728 divisible by 11? Answer yes or no.
Alternate the signs of the digits.
9 / 25 · Medium
Compute (1234567+9876543) mod 9.
Reduce the addends separately.
10 / 25 · Medium
Compute 123×456 mod 7.
Reduce each factor before multiplying.
11 / 25 · Medium
Compute 2^100 mod 7.
The cycle is 2,4,1.
12 / 25 · Medium
Compute 5^2025 mod 13.
Compute the first four powers of 5 modulo 13.
13 / 25 · Medium
Solve 3x≡1 (mod 7): give x modulo 7.
Find what you must multiply by 3 to get remainder 1.
14 / 25 · Medium
Solve 7x≡3 (mod 10): give x modulo 10.
The inverse of 7 modulo 10 is 3.
15 / 25 · Hard
Solve 6x≡5 (mod 8). Write “none” if there is no solution.
Compute GCD(6,8).
16 / 25 · Hard
Solve 6x≡4 (mod 8). Give both solutions separated by a comma.
Divide by GCD(6,8)=2.
17 / 25 · Hard
Find the least positive x with x≡2 (mod 3) and x≡3 (mod 5).
Write x=2+3t.
18 / 25 · Hard
Find the least positive x with residues 2 mod 3, 3 mod 5 and 2 mod 7.
Start with x=8 from the first two conditions.
19 / 25 · Hard
Find the least positive number leaving remainders 1,2,3,4 when divided by 2,3,4,5.
It is −1 modulo each of the four moduli.
20 / 25 · Hard
What are the last two digits of 3^100? Write two digits.
3^20≡1 (mod 100).
21 / 25 · Challenge
Compute (10^1000+3) mod 7.
10≡3 (mod 7) and 3^6≡1 (mod 7).
22 / 25 · Challenge
Can an integer x satisfy x²≡3 (mod 4)? Answer yes or no.
Try the four residues 0,1,2,3.
23 / 25 · Challenge
Which distinct residues can x³ have modulo 9? Separate them with commas.
Try x=0,1,…,8.
24 / 25 · Challenge
Explain why n³−n is divisible by 6 for every integer n.
Factor n³−n=n(n−1)(n+1).
25 / 25 · Challenge
Find the last digit of 7^(7^7).
Powers of 7 modulo 10 have period 4: first reduce 7^7 modulo 4.
From coins and soldiers to calendars: solve systems of congruences, check the bounds, and discover when no answer exists. Solutions sit below each problem but stay closed until you choose to look.
Read the article: Sunzi and the Chinese remainder theorem →
The classical problem in the Sunzi Suanjing asks for a number leaving remainders 2, 3 and 2 on division by 3, 5 and 7. The blocks 70, 21 and 15 give 2×70 + 3×21 + 2×15 = 233; subtracting 105 twice gives 23.
1 / 30 · Beginner
Find the smallest positive integer satisfying every condition.
x ≡ 1 (mod 3) · x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
2 / 30 · Beginner
Find the smallest positive integer satisfying every condition.
x ≡ 2 (mod 3) · x ≡ 2 (mod 5) · x ≡ 2 (mod 7)
If all the remainders match, subtract that remainder and look for a multiple of the LCM.
3 / 30 · Beginner
Find the smallest positive integer satisfying every condition.
x ≡ 2 (mod 3) · x ≡ 4 (mod 5) · x ≡ 6 (mod 7)
Each remainder is one less than its modulus: reason about x+1.
4 / 30 · Beginner
Find the smallest positive integer satisfying every condition.
x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
5 / 30 · Beginner
Find the smallest positive integer satisfying every condition.
x ≡ 1 (mod 4) · x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
7 / 30 · Beginner
A merchant groups coins in threes, fives and sevens; 2, 4 and 6 coins remain. What is the smallest total?
x ≡ 2 (mod 3) · x ≡ 4 (mod 5) · x ≡ 6 (mod 7)
Each remainder is one less than its modulus: reason about x+1.
16 / 30 · Beginner
A merchant groups bags of rice in fours, fives or sixes; each time one fewer bag remains than the group size.
x ≡ 3 (mod 4) · x ≡ 4 (mod 5) · x ≡ 5 (mod 6)
Each remainder is one less than its modulus: reason about x+1.
6 / 30 · Intermediate
Find the smallest positive integer satisfying every condition.
x ≡ 1 (mod 5) · x ≡ 2 (mod 7) · x ≡ 3 (mod 8)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
8 / 30 · Intermediate
A general arranges soldiers in rows of 4, 5 and 7; respectively 1, 2 and 4 soldiers are left over.
x ≡ 1 (mod 4) · x ≡ 2 (mod 5) · x ≡ 4 (mod 7)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
10 / 30 · Intermediate
Find the smallest positive integer satisfying every condition.
x ≡ 3 (mod 5) · x ≡ 4 (mod 7) · x ≡ 5 (mod 9)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
11 / 30 · Intermediate
Find the smallest positive integer satisfying every condition.
x ≡ 1 (mod 2) · x ≡ 2 (mod 3) · x ≡ 3 (mod 5) · x ≡ 4 (mod 7)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
13 / 30 · Intermediate
What remainders does 47 leave when divided by 3, 5 and 7? Enter the three remainders in order, separated by commas.
47 mod 3, 5, 7
Divide 47 by each modulus and write down the three remainders in order.
17 / 30 · Intermediate
Rows of 5, 7 or 8 soldiers leave respectively 1, 3 or 4 soldiers outside.
x ≡ 1 (mod 5) · x ≡ 3 (mod 7) · x ≡ 4 (mod 8)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
19 / 30 · Intermediate
Find the smallest positive integer satisfying every condition.
x ≡ 1 (mod 6) · x ≡ 2 (mod 7) · x ≡ 3 (mod 8)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
20 / 30 · Intermediate
Three periodic events repeat every 5, 7 and 9 days. Their next occurrences are in 1, 3 and 4 days. When will all three occur together?
x ≡ 1 (mod 5) · x ≡ 3 (mod 7) · x ≡ 4 (mod 9)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
21 / 30 · Intermediate
Pouring a whole number of litres into containers of 8, 9 or 13 litres leaves 3, 5 or 7 litres.
x ≡ 3 (mod 8) · x ≡ 5 (mod 9) · x ≡ 7 (mod 13)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
22 / 30 · Intermediate
Find the smallest positive integer satisfying every condition.
x ≡ 2 (mod 6) · x ≡ 5 (mod 9)
For moduli that are not coprime, their remainders must agree modulo their GCD.
25 / 30 · Intermediate
Find the smallest positive integer satisfying every condition.
x ≡ 1 (mod 5) · x ≡ 2 (mod 6) · x ≡ 3 (mod 7)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
9 / 30 · Advanced
Find the smallest positive integer satisfying every condition.
x ≡ 3 (mod 8) · x ≡ 5 (mod 9) · x ≡ 7 (mod 11)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
12 / 30 · Advanced
Find the smallest positive integer satisfying every condition.
x ≡ 5 (mod 8) · x ≡ 7 (mod 9) · x ≡ 9 (mod 11)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
15 / 30 · Advanced
Find the smallest positive integer satisfying every condition.
x ≡ 2 (mod 7) · x ≡ 4 (mod 9) · x ≡ 6 (mod 11)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
26 / 30 · Advanced
The required number lies between 100 and 500 inclusive.
x ≡ 2 (mod 7) · x ≡ 3 (mod 8) · x ≡ 4 (mod 9)
Look for an answer within the stated bound; if none exists, write “none”. From 100 · Up to 500
Solve without bounds first; then compare the smallest positive candidate with the required interval.
28 / 30 · Advanced
Find the smallest positive integer satisfying every condition.
x ≡ 1 (mod 3) · x ≡ 2 (mod 4) · x ≡ 3 (mod 5) · x ≡ 4 (mod 7)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
30 / 30 · Advanced
Find the smallest positive integer satisfying every condition.
x ≡ 4 (mod 7) · x ≡ 5 (mod 8) · x ≡ 6 (mod 9) · x ≡ 7 (mod 11)
Combine the congruences one at a time: write x as the first remainder plus a multiple of the first modulus.
14 / 30 · Trick questions with no answer under the stated conditions
Find the smallest positive integer satisfying every condition.
x ≡ 1 (mod 4) · x ≡ 2 (mod 6)
For moduli that are not coprime, their remainders must agree modulo their GCD.
18 / 30 · Trick questions with no answer under the stated conditions
A treasure holds fewer than 500 coins; division by 7, 9 and 11 leaves 2, 4 and 6.
x ≡ 2 (mod 7) · x ≡ 4 (mod 9) · x ≡ 6 (mod 11)
Look for an answer within the stated bound; if none exists, write “none”. Less than 500
Solve without bounds first; then compare the smallest positive candidate with the required interval.
23 / 30 · Trick questions with no answer under the stated conditions
Find the smallest positive integer satisfying every condition.
x ≡ 2 (mod 6) · x ≡ 4 (mod 9)
For moduli that are not coprime, their remainders must agree modulo their GCD.
24 / 30 · Trick questions with no answer under the stated conditions
A warehouse holds fewer than 1,000 boxes; grouping by 11, 13 and 17 leaves 4, 6 and 10.
x ≡ 4 (mod 11) · x ≡ 6 (mod 13) · x ≡ 10 (mod 17)
Look for an answer within the stated bound; if none exists, write “none”. Less than 1000
Solve without bounds first; then compare the smallest positive candidate with the required interval.
27 / 30 · Trick questions with no answer under the stated conditions
The required number lies between 200 and 400 inclusive.
x ≡ 1 (mod 7) · x ≡ 1 (mod 9) · x ≡ 1 (mod 11)
Look for an answer within the stated bound; if none exists, write “none”. From 200 · Up to 400
Solve without bounds first; then compare the smallest positive candidate with the required interval.
29 / 30 · Trick questions with no answer under the stated conditions
Find the smallest positive integer satisfying every condition.
x ≡ 2 (mod 4) · x ≡ 3 (mod 6) · x ≡ 4 (mod 8)
For moduli that are not coprime, their remainders must agree modulo their GCD.
Each challenge is generated on the spot: the answer is computed, not taken from a fixed list.