Class Notes (1,100,000)

CA (620,000)

UW (20,000)

MATH (2,000)

MATH135 (400)

Roxane Itier Itier (10)

Lecture 9

School

University of WaterlooDepartment

MathematicsCourse Code

MATH135Professor

Roxane Itier ItierLecture

9This

**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 ﬁlled

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 ﬁll 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, ﬁnd 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 p1q30 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 deﬁnition 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