Mathematical System

Applications of Modular
Arithmetic
Applications of Modular Arithmetic
Modular arithmetic is used in many areas. Two
particular areas are error checking and
encryption. Error checking is the study of
methods to determine if there is something
wrong with the information. Encryption is the
study of converting information into “codes” so
that only certain people may receive the
original information.
 Error Checking

Error Checking
There are many ways to check for errors.
One method involves using check digits. Check
digits are typically used to determine if there is
something wrong with a given sequence of
numbers. Thus, these are typically used for
barcodes, credit cards, International Standard
Book Numbers (ISBNs), and International
Standard Serial Numbers (ISSNs).
Note: The check digit is typically the rightmost
digit in the sequence of numbers. Thus, for
123456789, the check digit is 9.
 Universal Product Code-A number
Definition: A UPC-A number
x1x2x3x4x5x6x7x8x9x10x11x12 is valid, if the following
congruence is true:
3x1 + x2 + 3x3 + x4 + 3x5 + x6 + 3x7 + x8 + 3x9 + x10
+ 3x11 + x12 ≡ 0 (mod 10)

Note that the check digit is x12.

 Examples

1) 5734 6219 3387 is a valid UPC-A number. This is

because, by the definition:
3x1 + x2 + 3x3 + x4 + 3x5 + x6 + 3x7 + x8 + 3x9 + x10
+ 3x11 + x12 ≡ 0 (mod 10)
We have,
3×5 + 7 + 3×3 + 4 + 3×6 + 2 + 3×1 + 9 + 3×3 + 3 + 3×8 +
7
= 15 + 7 + 9 + 4 + 18 + 2 + 3 + 9 + 9 + 3 + 24 + 7
= 110
Hence, 110≡ 0 (mod 10). VALID

Note that the check digit is 7.

 Example
2) 2915 3846 7123 is not a valid UPC-A number. This is because
by the definition:
3x1 + x2 + 3x3 + x4 + 3x5 + x6 + 3x7 + x8 + 3x9 + x10 + 3x11 +
x12 ≡ 0 (mod 10)
We have,
3×2 + 9 + 3×1 + 5 + 3×3 + 8 + 3×4 + 6 + 3×7 + 1 + 3×2 + 3
= 6 + 9 + 3 + 5 + 9 + 8 + 12 + 6 + 21 + 1 + 6 + 3
= 89
Hence, 89≡ 9 (mod 10). INVALID

To make it valid, we will add 1 to 9 to make it 10 , since 10 is

congruent to 0 (mod 10).
Hence, since the check digit is 3, we also add 1 to make it 4, then
the number would be valid.
Therefore the check digit should be 4.
 International Standard Book Number-
10 number
Definition: An ISBN-10 number x1x2x3x4x5x6x7x8x9x10
is valid, if the following congruence is true:
10x1 + 9x2 + 8x3 + 7x4 + 6x5 + 5x6 + 4x7 + 3x8 + 2x9 +
x10 ≡ 0 (mod 11)

Note that the check digit is x10.

Note that aside from the usual digits, you may see
an “X” for the check digit. This is used to represent
the number 10.
 Examples

1) 5734 6219 35 is a valid ISBN-10 number. This is

because by the definition,
10x1 + 9x2 + 8x3 + 7x4 + 6x5 + 5x6 + 4x7 + 3x8 + 2x9 + x10
≡ 0 (mod 11)
We have,
10×5 + 9×7 + 8×3 + 7×4 + 6×6 + 5×2 + 4×1 + 3×9 + 2×3
+5
= 50 + 63 + 24 + 28 + 36 + 10 + 4 + 27 + 6 + 5
= 253
Thus, 253≡ 0 (mod 11) VALID

Note that the check digit is 5.

 Example
2) 2915 3846 7X is not a valid ISBN-10 number. This is because
10×2 + 9×9 + 8×1 + 7×5 + 6×3 + 5×8 + 4×4 + 3×6 + 2×7 + 10
=20 + 81 + 8 + 35 + 18 + 40 + 16 + 18 + 14 + 10
= 260
Hence, 260 ≡ 7 (mod 11) INVALID

To make it valid, we will add 4 to 7 to make it 11 , since 11 is

congruent to 0 (mod 11).

Hence, since the check digit is X, we also add 4 and make it to

14. But 14 is congruent to 3 modulo 11.

Therefore, the check digit must be 3 to make it valid.

 ISBN-13 number
Definition: An ISBN-13 number
x1x2x3x4x5x6x7x8x9x10x11x12x13 is valid, if the
following congruence is true:
x1 + 3x2 + x3 + 3x4 + x5 + 3x6 + x7 + 3x8 + x9 + 3x10 +
x11 + 3x12 + x13 ≡ 0 (mod 10)

Note that the check digit is x13.

 Examples
1) 7573 4621 9338 0 is a valid ISBN-13 number. This
because by the definition,
x1 + 3x2 + x3 + 3x4 + x5 + 3x6 + x7 + 3x8 + x9 + 3x10 + x11 +
3x12 + x13 ≡ 0 (mod 10)
We have,
7 + 3×5 + 7 + 3×3 + 4 + 3×6 + 2 + 3×1 + 9 + 3×3 + 3 +
3×8 + 0
= 7 + 15 + 7 + 9 + 4 + 18 + 2 + 3 + 9 + 9 + 3 + 24 + 0
= 110
Hence, 110≡ 0 (mod 10) VALID

Note that the check digit is 0.

 Example
2) 9291 5384 6712 3 is not a valid ISBN-13 number. This is because

9 + 3×2 + 9 + 3×1 + 5 + 3×3 + 8 + 3×4 + 6 + 3×7 + 1 + 3×2 + 3

= 9 + 6 + 9 + 3 + 5 + 9 + 8 + 12 + 6 + 21 + 1 + 6 + 3
= 98
Thus, 98≡ 8 (mod 10) INVALID

To make it valid, we will add 2 to 8 to make it 10 , since 10 is

congruent to 0 (mod 10).

Hence, since the check digit is 3, we also add 2 to make it 5.

Therefore, the check digit must be 5, to make the ISBN-13 valid.

 International Standard Serial Number
Definition: An ISSN x1x2x3x4 x5x6x7x8 is valid, if the
following congruence is true:
8x1 + 7x2 + 6x3 + 5x4 + 4x5 + 3x6 + 2x7 + x8 ≡ 0 (mod
11)

Note that the check digit is x8.

Note that aside from the usual digits, you may see
an “X” for the check digit. This is used to represent
the number 10.
 Examples
1) 3462 192X is a valid ISSN. This is because by the
definition,
8x1 + 7x2 + 6x3 + 5x4 + 4x5 + 3x6 + 2x7 + x8 ≡ 0 (mod 11)
We have,
8×3 + 7×4 + 6×6 + 5×2 + 4×1 + 3×9 + 2×2 + 10
= 24 + 28 + 36 + 10 + 4 + 27 + 4 + 10
= 143
Hence, 143≡ 0 (mod 11) VALID

Note that “X” is the check digit, which represents the

number 10.
 Example
2) 1538 4673 is not a valid ISSN. This is because

8×1 + 7×5 + 6×3 + 5×8 + 4×4 + 3×6 + 2×7 + 3

= 8 + 35 + 18 + 40 + 16 + 18 + 14 + 3
= 152
Hence, 152≡ 9 (mod 11) INVALID

To make it valid, we will add 2 to 9 to make it 11 , since 11

is congruent to 0 (mod 11).

Hence, since the check digit is 3, we also add 2 to make it 5.

Therefore, the check digit must be 5.

 16 digit credit card number
Definition: A 16 digit credit card number can be
checked for validity by doing the following:

(1) List the numbers in the same order as given.

(2) Starting with the first number on the list, double
every other number.
(3) If there are any 2 digit numbers, list them as two
separate single digits.
(4) Add the numbers in the list.
(5) The 16 digit credit card number is valid if the
resulting sum is congruent to zero modulo ten.
Otherwise, it is invalid.
 Examples
1) 5734 6219 3387 0912 is a valid credit card number. This can be verified
by following the steps.
(1) List the numbers in the same order as given.
5734 6219 3387 0912
5, 7, 3, 4, 6, 2, 1, 9, 3, 3, 8, 7, 0, 9, 1, 2

(2) Starting with the first number on the list, double every other number.
5, 7, 3, 4, 6, 2, 1, 9, 3, 3, 8, 7, 0, 9, 1, 2
⇒ 2×5, 7, 2×3, 4, 2×6, 2, 2×1, 9, 2×3, 3, 2×8, 7, 2×0, 9, 2×1, 2
⇒ 10, 7, 6, 4, 12, 2, 2, 9, 6, 3, 16, 7, 0, 9, 2, 2

(3) If there are any 2 digit numbers, list them as two separate single digits.
10, 7, 6, 4, 12, 2, 2, 9, 6, 3, 16, 7, 0, 9, 2, 2
⇒ 1, 0, 7, 6, 4, 1, 2, 2, 2, 9, 6, 3, 1, 6, 7, 0, 9, 2, 2
The 10 becomes a 1 and 0; the 12 becomes a 1 and 2; and the 16
becomes a 1 and 6.
 Example
4) Add the numbers in the list.
1, 0, 7, 6, 4, 1, 2, 2, 2, 9, 6, 3, 1, 6, 7, 0, 9, 2, 2
1+0+7+6+4+1+2+2+2+9+6+3+1+6+7+0+9+
2+2
= 70

(5) The 16 digit credit card number is valid if the resulting

sum is congruent to zero modulo ten. Otherwise, it is
invalid.
Since, 70 ≡ 0 (mod 10) VALID

Therefore, 5734 6219 3387 0912 is a valid credit card

number.
Note that the check digit is 2.
 Example 2
2) 2915 3846 7123 5734 is not a valid credit card
number. This can be verified by following the steps.
(1) List the numbers in the same order as given.
2915 3846 7123 5734
2, 9, 1, 5, 3, 8, 4, 6, 7, 1, 2, 3, 5, 7, 3, 4

(2) Starting with the first number on the list, double

every other number.
2, 9, 1, 5, 3, 8, 4, 6, 7, 1, 2, 3, 5, 7, 3, 4
⇒ 2×2, 9, 2×1, 5, 2×3, 8, 2×4, 6, 2×7, 1, 2×2, 3, 2×5, 7, 2×3, 4
⇒ 4, 9, 2, 5, 6, 8, 8, 6, 14, 1, 4, 3, 10, 7, 6, 4
 Example
(3) If there are any 2 digit numbers, list them as two separate single digits.
4, 9, 2, 5, 6, 8, 8, 6, 14, 1, 4, 3, 10, 7, 6, 4
⇒ 4, 9, 2, 5, 6, 8, 8, 6, 1, 4, 1, 4, 3, 1, 0, 7, 6, 4
*The 14 becomes a 1 and 4; and the 10 becomes a 1 and 0.

(4) Add the numbers in the list.

4, 9, 2, 5, 6, 8, 8, 6, 1, 4, 1, 4, 3, 1, 0, 7, 6, 4
4+9+2+5+6+8+8+6+1+4+1+4+3+1+0+7+6+4
= 79

(5) The 16 digit credit card number is valid if the resulting sum is congruent to zero
modulo ten. Otherwise, it is invalid.
Since, 79 ≡ 9 (mod 10) INVALID
The credit card number 2915 3846 7123 5734 is not valid .
To make it valid, we will add 1 to 9 to make it 10 , since 10 is congruent to 0 (mod
10).

Note that the check digit is 4, we add 1 to make it 5. Then the number would be
valid. So, the check digit should be 5.
 Try This!

1) Determine if the following are valid UPC-A numbers. If the number is not
valid, indicate what the check digit should be to make it valid. 5392 4040 6038

2) Determine if the following are valid ISBN-10 numbers. If the number is not
valid, indicate what the check digit should be to make it valid. 6597 9380 2X

3) Determine if the following are valid ISSNs. If the number is not valid, indicate
what the check digit should be to make it valid. 8348 7622

4) Determine if the following are valid credit card numbers. If the number is not
valid, indicate what the check digit should be to make it valid. 0241 6683 9099
2596
Mathematical System

Encryption
 Encryption
• Encryption involves converting information into
another form so that it is not easily understood. The
purpose of this is to try and ensure that only the
intended recipients understand the original
information.
• This section will go over two methods of
encryption, which are the Caesar cipher (or shift
cipher), and the affine cipher
 Definition
The shift cipher transforms messages by shifting the
alphabets.
• Example
The following table is a shift cipher that uses a shift of
6 letters to encrypt a message.

A B C D E F G H I J K L MNO P Q R S T U VWX Y Z

G H I J K L MNO P Q R S T U VWX Y Z A B C D E F
A B C D E F G H I J K L MNO P Q R S T U VWX Y Z

G H I J K L MNO P Q R S T U VWX Y Z A B C D E F

Thus, if the original message is “DAYLIGHT”, the encrypted

message would be “JGEROMNZ”.

Note: Making a table for each possible shift is allowed, but

modular arithmetic makes life a bit easier. To make use of
modular arithmetic, the alphabets are converted to numbers
as shown in the following tables.
 A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
“DAYLIGHT” is first converted to its numerical equivalent using the table,
so it becomes “3, 0, 24, 11, 8, 6, 7, 19”. The shift value is then added to
each number. In the example, the shift value was 6, thus “3, 0, 24, 11, 8,
6, 7, 19” becomes “9, 6, 30, 17, 14, 12, 13, 25”. Next, determine the
residues with respect to modulo 26. Thus, “9, 6, 30, 17, 14, 12, 13, 25”
becomes “9, 6, 4, 17, 14, 12, 13, 25”. Finally, get the letters
corresponding to the numbers. Thus, “9, 6, 4, 17, 14, 12, 13, 25”
becomes “JGEROMNZ”.
• In summary, if E is the number for the encrypted
letter, O the number for the original letter, and S the
shift value, then:
• E ≡ O + S (mod 26)
• Similarly, to decrypt a message, the following
congruence can be used:
• O ≡ E – S (mod 26)
 Example
Encrypt the following messages using a shift cipher with the
indicated shift value.
1) “LOVE”; S = 9

A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Solution. E ≡ O + S (mod 26)

L : 11 + 9 = 20 ≡20(mod 26) U Hence, the encrypted letter

O : 14 + 9 = 23 ≡ 23(mod 26) X for LOVE is UXEN.
V : 21 + 9 = 30 ≡ 4 (mod 26) E
E : 4 + 9 = 13 ≡ 13(mod 26) N
 To decrypt the message
Decrypt the word “UXEN” to obtain the original message using shift cipher
with shift value s = 9.

A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Solution. O ≡ E – S (mod 26)

U : 20 - 9 = 11 ≡ 11 (mod 26) L Hence, the original message is

X : 23 - 9 = 14 ≡ 14 (mod 26) O LOVE.
E : 4 - 9 = - 5 ≡ 21 (mod 26) V
N : 13 - 9 = 4 ≡ 4 (mod 26) E
Definition: The affine cipher is similar to the shift cipher, but
also makes use of a multiplier.

• Let E be the number for the encrypted letter, O the

number for the original letter, S the shift value, and M
the multiplier value (which can only be 1, 3, 5, 7, 9, 11,
15, 17, 19, 21, 23, and 25).
• To encrypt a letter, use the following:
E ≡ M×O + S (mod 26)
• To decrypt a message, use the following:
O ≡ (E – S) ÷ M (mod 26)
 Example
To encrypt “DAYLIGHT” using an affine cipher that has a shift
value of 12 and a multiplier of 11, you first convert it to its
numerical equivalent. This was previously done and is “3, 0, 24,
11, 8, 6, 7, 19”.

According to the formula, we first multiply the numbers by the

multiplier, then add the shift value, and finally get the residue
modulo 26.
• Thus, “3, 0, 24, 11, 8, 6, 7, 19” becomes “19, 12, 16,
3, 22, 0, 11, 13”.
• Converting this back to its alphabet equivalent
yields an encrypted message that is “TMQDWALN”.

A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
 Example
Encrypt the following messages using affine cipher with the
indicated shift value.
1) “LOVE”; S = 9 ; M = 15
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Solution. E ≡ (O x M) + S (mod 26)

L : (11 x 15) + 9 = 174 ≡ 18 (mod 26) S Hence, the encrypted message

O : (14 x 15) + 9 = 219 ≡ 11 (mod 26) L for LOVE is SLMR.
V : (21 x 15) + 9 = 324 ≡ 12 (mod 26) M
E : (4 x 15) + 9 = 69 ≡ 17(mod 26) R
 Decrypt using Affine cipher
Decrypt the word “SLMR” to obtain the original message using
affine cipher with shift value s = 9 , M=15

A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Solution. O ≡ (E – S ) ÷ 15 (mod 26) ⇒ O ≡ (E – S ) × 7 (mod 26)

S : (18 - 9) × 7 = 63 ≡ 11 (mod 26) L

L : (11 - 9) × 7 = 14 ≡ 14 (mod 26) O
M : (12 - 9) × 7 = 21 ≡ 21 (mod 26) V
R : (17 - 9) × 7 = 56 ≡ 4 (mod 26) E
 Try This!
I. Encrypt the following messages using the indicated method.
1) CORONAVIRUS: use shift cipher with s = 17
2) PANDEMIC : use affine cipher with s = 7; m = 9

II. Decrypt the message using shift cipher.

1) QFGFS QFSL; S = 5
2) PIOJWVO SI OM NWCZ; S = 8

III. Decrypt the message using affine cipher.

SAA WYC TARX SAO : with s = 6; m = 5