Last updated on July 23rd, 2020 at 05:49 am
If it is the month of November now, and I ask you to tell me what month will it be 25 months from now, what would your approach be?
Of course, one method is to count all the way till the 25th month. But what we are essentially doing, is applying the division algorithm.
i.e. 25= (12*2) + 1; And we obtain the answer as December in no time.
So, the division algorithm states: If we have two integers, ‘a’ and ‘n’, then there always exist integers q and r, such that:
a= (q*n) + r,
where q is the quotient, and r is the remainder upon dividing a by n.
We can also write this as:
a ≡ r (mod n),
which means, if a, n and r are positive integers, then (a-r) exactly divides n.
Now let’s look at a USPS (United States Postal Service) Money order slip.
When we look closely, we find that on the left hand side, is a 11 digit number. The first 10 digits is the identification number of the Money order, and the last number is the “cheque number”. Now the postal services’ job is to find whether the 10-digit number matches that specific cheque number or not. This is carried on with a simple algorithm, and that is :
11—digit number ≡ cheque digit (mod 9)
Suppose here we have an identification number from the above money order is ‘46174018418’. Just divide this number by 9 we will get the remainder as 8.
I.e. 46174018418 ≡ 8 (mod 9)
Suppose the serviceman enters a wrong ID number, for example, he entered the 4th digit as 8 instead of 7, then the machine would calculate the digit as 4, whereas the entered cheque digit would be 8, hence the error can be detected.
One thing to keep in mind though is that no error will be detected if any two digits are interchanged by mistake (transposition error). That is if instead of 46174018418, which is the correct sequence, the number is entered as 46174014818 (notice the 8th and 9th digits are interchanged),
46174014818 ≡ 8 (mod 9) is still equal to 46174018418 ≡ 8 (mod 9), (please check for yourself)
and hence no error will be detected.
This is because divisibility by 9 demands that the sum of all digits must be divisible by 9. This also means that if the entering is done so badly that most of the digits are erroneous, but still if the new number is divisible by 9, then it will be passed on as valid.
Now, to avoid this and make the system more error-free, we take another example, the one of UPC code,(ie. Universal Product Code), or as we are all familiar with, the bar codes which can be found on almost all products in any supermarket.
Image source: en.wikipedia.org
A UPC identification number has 12 digits. The first six digits identity the manufacturer, the next five uniquely determine the identity of the product ,and the last digit is a check digit.(for many items, the 12th digit is not printed ,but it is always bar-coded.)
To define how the check digit is calculated, it is convenient to introduce the dot product notation for two k-tuples:
A= (a1,a2,a3….,ak)
W= (w1,w2,w3,…,wk)
A*W= (a1,a2,a3,a4,….,ak)*(w1,w2,w3,w4,…,wk) = a1*w1 + a2*w2 + a3*w3 + ….. + ak*wk
Now W= (3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1)
An item with the UPC identification number a1,a2,….,ak satisfies the condition:
(a1,a2,…..,ak)*(3,1,3,1,3,1,3,1,3,1, 3, 1) ≡ 0 (mod 10)
Now suppose a single error is made in entering the number in above given figure into a computer. Say, for instance, that instead of 036000291452, 036000391452 is entered (notice that the seventh digit is incorrect); then the computer calculates:
0.3+3.1+6.3+0.1+0.3+0.1+3.3+9.1+1.3+4.1+5.3+2.1= 73
Since 73≡0 (mod 10) is incorrect, hence the entered number is incorrect.
Suppose, the identification number in the above figure entered as 03600092145 i.e. 7th and 8th digit is transposed.
Then we will get 72≡0 (mod 10), which is incorrect, so, we detect an error.
Now, it can’t detect any error in transposition of any two integers a and b if a-b=5
Let’s try to show this above statement:
Suppose my UPC ID no is A1,A2,A3,A4,….,A12
I took a transposition of Ai and Ai+1 number of my id number
i.e. A1, A2, A3, …, Ai, Ai+1, …, A12 →A1, A2, A3, …, Ai+1, Ai, …, A12
is undetected if and only if
(A1, A2, A3, …, Ai, Ai+1, …A12).(3,1,3,1,3,1,3,1,3,1,3,1)≡0 (mod 10)
(A1 ,A2, A3, …,Ai+1, Ai, …,A12).(3,1,3,1,3,1,3,1,3,1,3,1)≡0 (mod10)
Then, (3Ai+Ai+1 )≡0 (mod10)=(3Ai+1 + Ai) ≡ 0 (mod10)
Depending on whether ‘i’ is even or odd. both cases reduce to 2(Ai+1 – Ai) ≡0 (mod 10), if Ai+1 is not equal to Ai.
Of course, this method is much better than the one we saw initially in the postal system example. Also, here for a transposition error to go unnoticed, a digit must be swapped with a digit not immediately next to it, but with its second closest neighbor.
Do you have more ideas to make the second system better? Please share them in the comments section below.
Besides this, you can view our video and blog collections in the Video Section & Blog Section of the website.
 + r, where q is the quotient, and r is the remainder upon dividing a by n.){kind=link}