Congruence modulo n

This is also called modular arithmetic, or clock arithmetic. A clock shows 5 o'clock both 5 hours and 17 hours after midnight. That is because 17 and 5 leave the same remainder when divided by 12. So 17 ≡ 5 (mod 12).

Another way to say it: a ≡ b (mod n) when n divides a - b. The useful part is that you can add, subtract and multiply using remainders alone. The final remainder comes out the same. This keeps huge numbers small.

A small example

Find the remainder when 2¹⁰ is divided by 7. Start small: 2³ = 8, and 8 leaves remainder 1. So 2³ ≡ 1 (mod 7).

• Write 2¹⁰ as 2³ × 2³ × 2³ × 2.
• Replace each 2³ by 1. That gives 1 × 1 × 1 × 2 = 2.
• So 2¹⁰ ≡ 2 (mod 7). The remainder is 2.

Check: 2¹⁰ = 1024, and 1024 = 7 × 146 + 2. The method never needed the big number. For larger powers, Fermat's little theorem gives a shortcut.

Where it fits

This goes beyond the Class 10 board syllabus. HBCSE's syllabus for the Mathematical Olympiad names it under number theory. The Mathematics Teachers' Association (India), MTA(I), conducts IOQM, the first stage of the Mathematical Olympiad Programme that HBCSE organises for NBHM.

About the author

Mohit Sardana

Chief Architect

An engineer (B.Tech, Computer Science) with over 20 years of preparing students for entrance exams, including as Dean at FIITJEE and Vice-President at Aakash. He is the chief architect of the TRUpreBoards evaluation engine.

Mohit Sardana on LinkedIn