Linear congruence

It is like a linear equation, but it works with remainders. The sign ≡ means both sides leave the same remainder on division by n. This is congruence modulo n.

Such a congruence may have no solution. It has a solution exactly when the HCF of a and n divides b. When a and n are co-prime, their HCF is 1. Then there is always exactly one answer among 0, 1, 2 and so on up to n - 1.

A small example

Solve 3x ≡ 2 (mod 5). The HCF of 3 and 5 is 1, so an answer exists. Try x = 0, 1, 2, 3 and 4 in turn:

• 3 × 0 = 0, 3 × 1 = 3, 3 × 2 = 6, which leaves 1.
• 3 × 3 = 9, which leaves 4.
• 3 × 4 = 12, which leaves 2. This works.

So x ≡ 4 (mod 5). The full answer is 4, 9, 14, 19 and so on. Now try 2x ≡ 1 (mod 4). Here 2x is even, so it leaves 0 or 2, never 1. There is no solution. The rule agrees: the HCF of 2 and 4 is 2, and 2 does not divide 1. The HCF decides it.

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