Class Notes (1,100,000)
CA (620,000)
UW (20,000)
MATH (2,000)
MATH135 (400)
Lecture 9

MATH135 Lecture 9: Examples on CRT


Department
Mathematics
Course Code
MATH135
Professor
Roxane Itier Itier
Lecture
9

This preview shows page 1. to view the full 5 pages of the document.
MATH 135, Winter 2015
Examples: Chinese Remainder Theorem
We collect some questions whose solutions involve the Chinese Remainder Theorem, even though
the questions do not explicitly require solving systems of congruences with coprime moduli.
Exercise. Here is a visual interpretation of CRT.
Take m36, and consider two possible factorizations mm1m2.
(a) Take m14 and m29, so that gcdpm1, m2q  1. Consider the following table, to be filled
with the classes rxs36 PZ36 for 0 ¤x¤35.
r0s9r1s9r2s9r3s9r4s9r5s9r6s9r7s9r8s9
r0s4r0s36 r4s36
r1s4r1s36
r2s4r2s36
r3s4r3s36
The rule for successively inserting the classes r0s36,r1s36 ,r2s36,. . . into the table is as follows.
Given an integer xwith 0 ¤x¤35, if xa1pmod m1qand xa2pmod m2qwhere
0¤a14 and 0 ¤a29, we put rxs36 into the slot which belongs to the same row as ra1s4
and the same column as ra2s9. A few classes have been inserted as examples.
(b) Now, play the same game with m13 and m212 (so that gcdpm1, m2q  3¡1).
r0s12 r1s12 r2s12 r3s12 r4s12 r5s12 r6s12 r7s12 r8s12 r9s12 r10s12 r11s12
r0s3
r1s3
r2s3
Summarizing, CRT guarantees that if m1and m2are coprime, then we can fill up the entire table
using the rule
rxsmPZmÞÑ rxsm1,rxsm2PZm1Zm2.
This is not true if gcdpm1, m2q ¡ 1.
(c) Circle all invertible classes of Z36 in the table in part (a). What pattern do you see? Make a
conjecture, and prove your claim if possible.
1
You're Reading a Preview

Unlock to view full version

Only page 1 are available for preview. Some parts have been intentionally blurred.

Example 1. Reduce 1730 pmod 60q. (More precisely, find the unique integer xsuch that
x1730 pmod 60qand 0 ¤x60.)
Solution. (This approach was presented in class on Monday, March 9.)
Note that 60 345 and 3, 4 and 5 are pairwise coprime. According to the (generalized)
Chinese Remainder Theorem, for any xPZ,
x1730 pmod 60q ðñ
$
'
'
'
&
'
'
'
%
x1730 pmod 3q
x1730 pmod 4q
x1730 pmod 5q
We consider reducing 1730 modulo 3, 4 and 5:
1730  p1q30 1pmod 3q
1730 130 1pmod 4q
1730 230  p24q7221744pmod 5q
(In the last congruence, we used Fermat’s Little Theorem: 241pmod 5q.) Thus, the single
congruence x1730 pmod 60qis equivalent to the system of congruences
x1pmod 3q(1)
x1pmod 4q(2)
x4pmod 5q(3)
by applying the standard CRT-type calculations.
From (3) we know (by the definition of congruence) that
x5s4pDsPZq.(4)
The two unused congruences (1) and (2) will restrict the choice of s. Substituting (4) into (2) and
solving for s:
5s41pmod 4q
ðñ s1pmod 4q
so that
s4t1pDtPZq.(5)
2
You're Reading a Preview

Unlock to view full version