Cryptography Reference
In-Depth Information
Proof.
Clearly, if the product
p
= (
a
1
a
2
...
a
n
) divides
c
, then each
a
i
,
i
= 1, 2, . . . ,
n
likewise divides
c
, since each
a
i
|
p
, and
p
|
c
. Conversely, suppose each
a
i
divides
c
. Then
the prime factorization of
c
must contain the prime factorization of each
a
i
, and since
these are pairwise relatively prime, no
a
i
can have a prime factor in common with any
other. Thus, the prime factorization of
c
contains the prime factorization of the product
p
, and so
p
|
c
.
The next proposition is what we really need for the Chinese Remainder Theorem, and
using the previous result makes its proof very simple. You are requested to do this.
PROPOSITION 26.
Let
a
b
(mod
m
1
),
a
b
(mod
m
2
), . . . ,
a
b
(mod
m
n
) where
a
1
,
a
2
, . . . ,
a
n
are pairwise relatively prime. Then we have
a
b
(mod
m
1
m
2
...
m
n
).
PROPOSITION 27. (THE CHINESE REMAINDER THEOREM.)
Suppose
m
1
,
m
2
, . . . ,
m
n
are pairwise relatively prime. Then the system of congruences
x
a
1
(mod
m
1
)
x
a
2
(mod
m
2
)
...
x
a
n
(mod
m
n
)
has a unique solution modulo
M
=
m
1
m
2
...
m
n
; namely,
x
a
1
M
1
M
1
+
a
2
M
2
M
2
+ . . . +
a
n
M
n
M
n
(mod
M
)
where
M
i
=
M
/
m
i
and
M
i
is an inverse of
M
i
modulo
m
i
∀ i
= 1, 2, . . . ,
n
.
Proof.
Let all the quantities be defined as stated in the proposition. First, note that
M
i
=
m
1
m
2
...
m
i
1
m
i
1
...
m
n
and
m
i
are relatively prime for any
i
. To see this, note that each
m
i
is relatively prime to
m
k
∀ i ≠ k
, and so if we have an integer
p
greater than 1 which
divides
m
i
, it cannot divide any other
m
k
, and hence cannot divide the product
m
1
m
2
...
m
i
1
m
i
1
...
m
n
=
M
i
. Thus, proposition 22 says that an inverse
M
i
of
M
i
modulo
m
i
exists.
Then the integer given by
x
=
a
1
M
1
M
1
+
a
2
M
2
M
2
+ . . . +
a
n
M
n
M
n
simultaneously solves the system of congruences
x
a
1
(mod
m
1
)
x
a
2
(mod
m
2
)
...
x
a
n
(mod
m
n
).
m
k
|
M
i
when
i k
M
i
m
k
). Thus, all terms
To see this, note that
, hence giving us
0 (mod
x
m
k
vanish except the
k
of
modulo
th term, and so we have
x
a
k
M
k
M
k
a
k
1
a
k
(mod
m
k
)
Search WWH ::
Custom Search