Modular Arithmetic Properties

When you think about arithmetic what comes to mind? Arithmetic is the study of numbers primarily dealing with the properties of the traditional operations on numbers, which we know as addition, subtraction, multiplication, and division. Thus, modular arithmetic is arithmetic, but using modules mathematics. Let's take a look at some operations found in modular arithmetic:

Here is the general form for adding in the modules system: (a + b) mod c = (a mod c + a mod c) mod c

Here is the general form for adding in the modules system: (a - b) mod c = (a mod c - b mod c) mod c

Addition in modular arithmetic has the following properties:

1. Addition is closed in Z_n: (a+b) mod n = c implies that c ∈ Z_n
2. Addition is Commutative: (a+b) mod n = (b+a) mod n
3. Addition is Associative (a+b)+c mod n = a+(b+c) mod n
4. [0] is the additive identity: (a+0) mod n = a mod n
5. For every [a] ∈ Z_n there exist an additive inverse [-a] ∈ Z_n

For example, let a=22 b=17 and c=3 then We have (22 + 17) mod 3 = (22 mod 3 + 17 mod 3) mod 3
Looking at the right-hand side (RHS) we know:
22 mod 3 = [1]
17 mod 3= [2]
so (22 mod 3 + 17 mod 3) mod 3 => (1 + 2) mod 3 => 3 mod 3=[0]
Looking at the left hand side (LHS) we know:
(22 + 17) mod 3 => 39 mod 3 since 39=13(3)+0 we know by Definition 1 39 mod 3=[0]
We have now shown that the RHS = LHS thus (22 ⊕ 17) mod 3 = (22 mod 3 ⊕ 17 mod 3) mod 3
*Note that the same idea is true for subtraction* You may find it useful to use an operation table when doing addition in modular arithmetic here is an example of an addition operation table in mod 6 :

⊕	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

The first column and the first row tell you what numbers to add and the section of their intersect is the sum of the column space and the row space. For example, find 3 mod 6 + 4 mod 6 . Using the table we use the first column and go to the space that has 3 then move across the to where the first row has four the intersection of the 3 from the first column and the 4 from the first row is the answer. Thus, 3 mod 6 + 4 mod 6=[1]

Here is the general form for adding in the modules system: (a ⋅ b) mod C = (a mod c ⋅ b mod c) mod c

Multiplication in modular arithmetic has the following properties:

1. Multiplication is closed in Z_n: (a ⋅ b) mod n = c implies that c ∈ Z_n
2. Addition is Commutative: (a ⋅ b) mod n = (b ⋅ a) mod n
3. Addition is Associative (a ⋅ b) ⊗ c mod n = a ⋅ (b ⋅ c) mod n
4. [1] is the multiplicative identity: (a ⋅ 1) mod n = a mod n

For example, let a=22 b=17 and c=3 then We have (22 ⋅ 17) mod 3 = (22 mod 3 ⋅ 17 mod 3) mod 3
Looking at the right-hand side (RHS) we know:
22 mod 3 = [1]
17 mod 3= [2]
so (22 mod 3 ⋅ 17 mod 3) mod 3 => (1 ⋅ 2) mod 3 => 2 mod 3=[2]
Looking at the left-hand side (LHS) we know:
(22 ⋅ 17) mod 3 => 374 mod 3 since 374=124(3)+2 we know by Definition 1 374 mod 3=[2]
We have now shown that the RHS = LHS thus (22 ⋅ 17) mod 3 = (22 mod 3 ⋅ 17 mod 3) mod 3

You may find it useful to use an operation table when doing multiplication in modular arithmetic here is an example of an addition operation table in mod 6 :

⊙	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	1	2	3	4	5
2	0	2	4	0	2	4
3	0	3	0	3	0	3
4	0	4	2	0	4	2
5	0	5	4	3	2	1

The first column and the first row tell you what numbers to add and the section of their intersect is the sum of the column space and the row space. For example, find 3 mod 6 ⋅ 4 mod 6 . Using the table we use the first column and go to the space that has 3 then move across the row to the space that has 4. The intersection of the row for 3 and the column for 4 is the answer. Thus, 3 mod 6 ⋅ 4 mod 6=[0]

Here is the general form for modular inverse (a ⋅ a^-1) ≡ 1 (mod C) or equivalently (a ⋅ a^-1) mod C = 1

*Please note that only numbers coprime to C, which are numbers that share no prime factors with C, have a modular inverse mod C*
For example, let a=3 b=7 and c=5 then We have (3 ⋅ 7) mod 5 => 21 mod 5 = 1
So 3 and 7 are inverses in mod 5

Ready for some practice? Check out this applet from Khan Academy

Need a more in-depth explanation check out the modular arithmetic section at Kahn Academy.

References for this page: Pinter, Charles C. (1990). A Book of Abstract Algebra. Retrieved from http://www2.math.umd.edu/~jcohen/402/Pinter%20Algebra.pdf
Khan, Sal. (n.d.) Journey into cryptography. Retrieved from https://www.khanacademy.org/computing/computer-science/cryptography