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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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