# A beautiful example of use of theory of congruences in engineering

The theory of congruences created by Gauss long ago is used in error control coding or error correction. The theory of congruences is frequently used to append an extra check digit to identification numbers, in order to recognize transmission errors or forgeries. Personal identification numbers of some kind appear in passports, credit cards, bank accounts, and a variety of other settings.

Some banks use (perhaps) an eight-digit identification number $a_{1}a_{2}\ldots a_{8}$ together with a final check digit $a_{0}$. The check digit is usually obtained by multiplying the digits $a_{i}$ for $1 \leq i \leq 8$ by certain “weights” and calculating the sum of the weighted products modulo 10. For instance, the check digit might be chosen to satisfy:

$a_{0} \equiv 7a_{1} + 3a_{2} + 9a_{3} + 7a_{4} + 3a_{5} + 9a_{6} + 7a_{7} + 3a_{8} {\pmod 10}$

The identification number 815042169 would be printed on the cheque.

This weighting scheme for assigning cheque digits detects any single digit error in the identification number. For suppose that the digit $a_{i}$ is replaced by a different $a_{i}$. By the manner in which the check digit is calculated, the difference between the correct $a_{9}$ and the new $a_9^{'}$ is

$a_{9} - a_9^{'} \equiv k(a_{i} - a_{i}^{'}) \pmod {10}$

where k is 7, 3, or 9 depending on the position of $a_{i}^{'}$. Because $k(a_{i}-a_{i}^{'}) \not\equiv 0 \pmod {10}$, it follows that $a_{9} \neq a_{9}^{'}$ and the error is apparent. Thus, if the valid number 81504216 were incorrectly entered as 81504316 into a computer programmed to calculate check digits, an 8 would come up rather than the expected 9.

The modulo 10 approach is not entirely effective, for it does not always detect the common error of transposing distinct adjacent entries a and b within the string of digits. To illustrate, the identification numbers 81504216 and 81504261 have the same check digit 9 when our example weights are used. (The problem occurs when $|a-b|=5$). More sophisticated methods are available, with larger moduli and different weights, that would prevent this possible error.

-Nalin Pithwa.

This site uses Akismet to reduce spam. Learn how your comment data is processed.