•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)
