Cryptography Reference
In-Depth Information
Theorem A.10
(
Modular Arithmetic
)
Let
n
∈
N
and suppose that for any
x
∈
Z
,
x
denotes the congruence class
of
x
modulo
n
. Then for any
a,b,c
∈
Z
the following hold.
(a)
a
±
b
=
a
±
b
.
(Modular additive closure)
(b)
ab
=
ab
.
(Modular multiplicative closure)
(c)
a
+
b
=
b
+
a
.
(Commutativity of modular addition)
(d) (
a
+
b
)+
c
=
a
+(
b
+
c
).
(Associativity of modular addition)
(e) 0+
a
=
a
+ 0=
a
.
(Additive modular identity)
(f)
a
+
−
a
=
−
a
+
a
= 0.
(Additive modular inverse)
(g)
ab
=
ba
.
(Commutativity of modular multiplication)
(h) (
ab
)
c
=
a
(
bc
).
(Associativity of modular multiplication)
(i) 1
·
a
=
a
·
1=
a
.
(Multiplicative modular identity)
(j)
a
(
b
+
c
)=
ab
+
ac
.
(Modular Distributivity)
Proof
. See [169, Theorem 2.7, page 60].
✷
For the notions of rings and fields used in the following, the reader should
consult page 483.
Definition A.20
(
The Ring
Z
/n
Z
)
For
n
∈
N
, the set
Z
/n
Z
=
{
0
,
1
,
2
,...,n
−
1
}
is called the
Ring of Integers Modulo
n
, where
m
denotes the congruence class
of
m
modulo
n
.
A.2
There is a multiplicative property of
Z
that
Z
/n
Z
does not have, namely,
the
Cancellation Law for
Z
, which says that if
ac
=
bc
where
a,b,c
∈
R
, and
c
= 0, then
a
=
b
.
This is not the case for
Z
/n
Z
in general.
For instance,
2
·
3
≡
2
·
8 (mod 10), but 3
≡
8 (mod 10). In other words, 2
·
3=2
·
8in
Z
/
10
Z
,
but 3
. We may ask for conditions on
n
under which a modular
law for cancellation would hold. In other words, for which
n
=8in
Z
/
10
Z
∈
N
does it hold
that:
for any
a,b,c
∈
Z
/n
Z
with
a
=0,
ab
=
ac
if and only if
b
=
c
?
(A.1)
It can be shown that (A.1) cannot hold if gcd(
a,n
)
>
1, but if gcd(
a,n
)=1,
then there is a solution
x
∈
Z
to
ax
≡
1 (mod
n
). This motivates the following.
A.2
Occasionally, when the context is clear and no confusion can arise when talking about
elements of
Z
/n
Z
, we will eliminate the
overline bars
.
Search WWH ::
Custom Search