Cryptography: Properties of Modular Arithmetic: Set Zn

•For arithmetic modulo n, let Zn denote the set

    Zn = {0, 1, 2, 3, ....., n−1}

Zn is the set of remainders in arithmetic modulo n. It is officially called the set of residues.

•Let’s now consider the set Zn along with the following two binary operators defined for the set:

1.modulo n addition; and

2.modulo n multiplication.

The elements of Zn obey the following properties:

 

•For every element of Zn, there exists an additive inverse in Zn. But there does not exist a multiplicative inverse for every non-zero element of Zn.

•The multiplicative inverses exist for only those elements of Zn that are relatively prime to n.

–Two integers are relatively prime to each other if the integer 1 is their only common positive divisor.

–More formally, two integers a and b are relatively prime to each other if gcd(a, b) = 1 where gcd denotes the Greatest Common Divisor.

•The following property of modulo n addition is the same as for ordinary addition:

  (a + b) ≡ (a + c)(mod n) implies b ≡ c (mod n)

•  ((-a) + a + b) ≡ ((-a) + a + c)(mod n)

     b ≡ c (mod n)

–(5 + 23) ≡ (5 + 7)(mod8); 23 ≡ 7(mod8)

•But a similar property is NOT obeyed by modulo n multiplication. That is

(a × b) ≡ (a × c)(mod n) does not imply b ≡ c(mod n)

unless a and n are relatively prime to each other.

  ((a-1)ab) ≡ ((a-1)ac)(mod n)

    b ≡ c(mod n)

•The integers 6 and 8 are not relatively prime, since they have the common factor 2.

•6 * 3 = 18 ≡ 2(mod 8)

•6 * 7 = 42 ≡ 2(mod 8)

•Yet 3 ≢ 7 (mod 8)