Modular Arithmetic (residue arithmetic) Definition/Meaning:
Arithmetic based on the concept of the congruence relation defined on
integers and used in computing to circumvent the problem of performing
arithmetic on very large numbers.
Let m1, rn2, ..., mk be integers, no two of which have a common factor greater
than one. Given a large positive integer n it is possible to compute the
remainders or residues r1,. r2, . . . , rk such that
n ≡ r1 (mod m1)
n ≡ r2 (mod m2)
n ≡ rk (mod
Provided n is less than
m1 x m2 x ... x mk
n can be represented by
This can be regarded as an internal representation of n. Addition, subtraction,
and multiplication of two large numbers then involves the addition, subtraction,
and multiplication of corresponding pairs, e.g.
(r1+ s1, ... , rk + sk)
Determining the sign of an integer or comparing
relative magnitudes are less straightforward.