## Quick Reference

Arithmetic based on the concept of the congruence relation defined on the integers and used in computing to circumvent the problem of performing arithmetic on very large numbers.

Let *m*_{1}, *m*_{2},…, *m** _{k}* 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

*r*

_{1},

*r*

_{2},…,

*r*

*such that*

_{k}*n*≡

*r*

_{1}(mod

*m*

_{1})

*n*≡

*r*

_{2}(mod

*m*

_{2})…

*n*≡

*r*

*(mod*

_{k}*m*

*) Provided*

_{k}*n*is less than

*m*

_{1}×

*m*

_{2}× … ×

*m*

_{k}*n*can be represented by(

*r*

_{1},

*r*

_{2},…,

*r*

*)This can be regarded as an internal representation of*

_{k}*n*. Addition, subtraction, and multiplication of two large numbers then involves the addition, subtraction, and multiplication of corresponding pairs, e.g.(

*r*

_{1},…,

*r*

*) + (*

_{k}*s*

_{1},…,

*s*

*) = (*

_{k}*r*

_{1}+

*s*

_{1}, …,

*r*

*+*

_{k}*s*

*)Determining the sign of an integer or comparing relative magnitudes are less straightforward.*

_{k}*n* ≡ *r*_{1} (mod *m*_{1})

*n* ≡ *r*_{2} (mod *m*_{2})

…

*n* ≡ *r** _{k}* (mod

*m*

*)*

_{k}*m*_{1} × *m*_{2} × … × *m*_{k}

(*r*_{1},*r*_{2},…,*r** _{k}*)

(*r*_{1},…,*r** _{k}*) + (

*s*

_{1},…,

*s*

*) = (*

_{k}*r*

_{1}+

*s*

_{1}, …,

*r*

*+*

_{k}*s*

*)*

_{k}
*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.