Problem
Debit and credit cards contain account numbers which consist of many digits. When purchasing items online, you are often asked to type in your account number. Because there are so many digits, it is easy to type the number incorrectly. The last digit of the number is a specially generated check digit which can be used to quickly verify the validity of the number. A common algorithm used for verifying numbers is called the Luhn Algorithm. A series of operations are performed on the number and a final result is produced. If the final result ends in zero, the number is valid. Otherwise, the number is invalid.
The steps performed in the Luhn Algorithm are outlined in the flowchart below. Two examples are provided.
Example 1:
Number: \(135792\)
Reversal: \(\textcolor{red}{2}9\textcolor{red}{7}5\textcolor{red}{3}1\)
\(\begin{aligned} A&=\textcolor{red}{2+7+3}\\ &=12\\ \end{aligned}\)
\(\begin{aligned} 2\times9&=18\\ 2\times5&=10\\ 2\times1&=2\\ \end{aligned}\)
\(\begin{aligned} B&=(1+8)+(1+0)+2\\ &=9+1+2\\ &=12\\ \end{aligned}\)
\(C=12+12=24\)\(C\) does not end in zero.
The number is not valid.
Example 2:
Number: \(1357987\)
Reversal: \(\textcolor{red}{7}8\textcolor{red}{9}7\textcolor{red}{5}3\textcolor{red}{1}\)
\(\begin{aligned} A&=\textcolor{red}{7+9+5+1}\\ &=22\\ \end{aligned}\)
\(\begin{aligned} 2\times8&=16\\ 2\times7&=14\\ 2\times3&=6\\ \end{aligned}\)
\(\begin{aligned} B&=(1+6)+(1+4)+6\\ &=7+5+6\\ &=18\\ \end{aligned}\)
\(C=22+18=40\)
\(C\) ends in zero.
The number is valid.
The number \(1953\,R8T9\,467\) is a valid card number when verified by the Luhn Algorithm.
\(R\) and \(T\) are each single digits of the number such that \(R\) is less than \(T\). Determine all possible values of \(R\) and \(T\).
Solution
When the digits of the card number are reversed the resulting number is \(764\,9T8R\,3591\). The sum of the digits in the odd positions is \(A=7+4+T+R+5+1=17+R+T\).
When the digits in the remaining positions are doubled, the following products are obtained:
\[6\times 2=12;~ 9\times 2=18;~ 8\times 2=16;~ 3\times 2=6;~ \text{ and }9\times 2=18\]
When the digit sums from each of the products are added, the sum is: \[B=(1+2)+(1+8)+(1+6)+6+(1+8)=3+9+7+6+9=34\]
Since \(C= A+B\), we have \(C=17+R+T+34=51+R+T\).
For the card to be valid, the units digit of \(C\) must be zero. The closest number greater than 51 ending in a zero is 60. It follows that \(R+T=60-51=9\). We want values of \(R\) and \(T\) that sum to 9 with \(R\) less than \(T\). The only possible combinations are \(R=0\) and \(T=9\), \(R=1\) and \(T=8\), \(R=2\) and \(T=7\), \(R=3\) and \(T=6\), and \(R=4\) and \(T=5\).
The next closest number greater than 51 ending in a zero is 70. It follows that \(R+T=70-51=19\). But the largest value possible for \(T\) is 9 and the largest value for \(R\) would then be 8. It follows that the largest possible value for \(R+T=8+9=17\). This means that there are no values of \(R\) and \(T\) so that \(C\) could equal 70.
Therefore, there are only 5 possible pairs of digits for \(R\) and \(T\) so that \(1953\ R8T9\ 467\) is a valid card number. The possibilities are \(R=0\) and \(T=9\), \(R=1\) and \(T=8\), \(R=2\) and \(T=7\), \(R=3\) and \(T=6\), and \(R=4\) and \(T=5\).
The card numbers are \(1953\,0899\,467\), \(1953\,1889\,467\), \(1953\,2879\,467\), \(1953\,3869\,467\), and \(1953\,4859\,467\), which are indeed valid by the Luhn Algorithm.