Number Theory and its Applications

4Theory of Congruences

“Number theorists are like lotus-eaters—having tasted this food they can never give it up.”

– Leopold Kronecker

4.1 Introduction

If two numbers a and b be such that the difference a−b is divisible by an integer n, then a and b are said to be “Congruent modulo n”. The number n is called the modulus and the statement “a is congruent to b(mod n)” is analytically written as

$a\equiv b\left(\mathrm{mod}n\right).$

The quantity a is often said to be the base and the quantity b is called the residue or remainder. There are several types of residues. The common residue defined to be the non-negative and smaller than n while the minimal residue is b or b − n, whichever is smaller than absolute terms.

Perhaps, congruence arithmetic is mostly treated ...