The Chinese Remainder Theorem PDF Then w1 w2

Math 127: Chinese Remainder Theorem

Hence we have that x is a solution to the system of congruences if and only if x ? 20 (mod 56). Example 4. Find x

Linear Congruences and the Chinese Remainder Theorem

Solve the congruence 231x ? 228 (mod 345). Solution. We have (231345) = 3 and 3

The Chinese Remainder Theorem

The Chinese Remainder Theorem says that certain systems of simultaneous congruences with dif- For example 6 is relatively prime to 25

THE CHINESE REMAINDER THEOREM We should thank the

Example 3.2. The congruences x ? 1 mod 3 x ? 2 mod 5

Math 3527 (Number Theory 1)

Polynomial Congruences III. Example: Solve the equation x2 ? 0 (mod 12). By the Chinese remainder theorem

MATH10040 Chapter 3: Congruences and the Chinese Remainder

Chapter 3: Congruences and the Chinese Remainder. Theorem. 1. Congruence modulo m. Recall that Rm(a) denotes the remainder of a on division by m. Thus by.

Historical development of the Chinese remainder theorem

There was only a numerical example without a general rule for a system of congruences of type (1). 3. The moduli were restricted to natural

Simultaneous Linear and Non-linear Congruences - CIS002-2

3 Simultaneous Non-linear Congruences. 4 Chinese Remainder Theorem - An Extension Chinese Remainder Theorem. Example: 10x ? 6 mod (14). Example.

Historical Development of the Chinese Remainder Theorem

Historical Development of the. Chinese Remainder Theorem. Shen Kangsheng. Communicated by C. Truesdell. 1. Source of the Problem. Congruences of first

The Chinese Remainder Theorem

Chinese Remainder Theorem: If m

1 , m 2 , .., m k are pairwise relatively prime positive integers, and if a 1 , a 2 , .., a k are any integers, then the simultaneous congruences x a 1 (mod m 1 ), x a 2 (mod m 2 ), ..., x a k (mod m k have a solution, and the solution is unique modulo m, where m = m 1 m 2 m k Proof that a solution exists: To keep the notation simpler, we will assume k = 4. Note the proof is constructive , i.e., it shows us how to actually construct a solution.

Our simultaneous congruences are

x a 1 (mod m 1 , x a 2 (mod m 2 , x a 3 (mod m 3 ), x a 4 (mod m 4

Our goal is to find integers w

1 , w 2 , w 3 , w 4 such that: value mod m 1 value mod m 2 value mod m 3 value mod m 4 w 1

1 0 0 0

w 2

0 1 0 0

w 3

0 0 1 0

w 4

0 0 0 1

Once we have found w

1 , w 2 , w 3 , w 4 , it is easy to construct x: x = a 1 w 1 + a 2 w 2 + a 3 w 3 + a 4 w 4

Moreover, as long as the moduli (m

1 , m 2 , m 3 , m 4 ) remain the same, we can use the same w 1 , w 2 , w 3 , w 4 with any a 1 , a 2 , a 3 , a 4

First define: z

1 = m / m 1 = m 2 m 3 m 4 z 2 = m / m 2 = m 1 m 3 m 4 z 3 = m / m 3 = m 1 m 2 m 4 z 4 = m / m 4 = m 1 m 2 m 3

Note that

i) z 1

0 (mod m

j ) for j = 2, 3, 4. ii) gcd(z 1 ,m 1 ) = 1. (If a prime p dividing m 1 also divides z 1 = m 2 m 3 m 4 , then p divides m 2 , m 3 , or m 4 and likewise for z 2 , z 3 , z 4

Next define: y

1 z 1-1 (mod m 1 y 2 z 2-1 (mod m 2 y 3 z 3-1 (mod m 3 y 4 z 4-1 (mod m 4 The inverses exist by (ii) above, and we can find them by Euclid's extended algorithm. Note that iii) y 1 z 1

0 (mod m

j ) for j = 2, 3, 4. (Recall z 1

0 (mod m

j iv) y 1 z 1

1 (mod m

1 and likewise for y 2 z 2, y 3 z 3 , y 4 z 4

Lastly define: w

1 y 1 z 1 (mod m) w 2 y 2 z 2 (mod m) w 3 y 3 z 3 (mod m) w 4 y 4 z 4 (mod m)

Then w

1 , w 2 , w 3 , and w 4 have the properties in the table on the previous page.

Example: Solve the simultaneous congruences

x 6 (mod 11) , x 13 (mod 16) , x 9 (mod 21) , x 19 (mod 25) Solution: Since 11, 16, 21, and 25 are pairwise relatively prime, the Chinese Remainder Theorem tells us that there is a unique solution modulo m, where m = 11162125 = 92400. We apply the technique of the Chinese Remainder Theorem with k = 4, m 1 = 11, m 2 = 16, m 3 = 21, m 4 = 25, a 1 = 6, a 2 = 13, a 3 = 9, a 4 = 19, to obtain the solution.

We compute

z 1 = m / m 1 = m 2 m 3 m 4 = 162125 = 8400 z 2 = m / m 2 = m 1 m 3 m 4 = 112125 = 5775 z 3 = m / m 3 = m 1 m 2 m 4 = 111625 = 4400 z 4 = m / m 4 = m 1 m 3 m 3 = 111621 = 3696 y 1 z 1-1 (mod m 1 ) 8400 -1 (mod 11) 7 -1 (mod 11) 8 (mod 11) y 2 z 2-1 (mod m 2 ) 5775 -1 (mod 16) 15 -1 (mod 16) 15 (mod 16) y 3 z 3-1 (mod m 3 ) 4400 -1 (mod 21) 11 -1 (mod 21) 2 (mod 21) y 4 z 4-1 (mod mquotesdbs_dbs14.pdfusesText_20

[PDF] The Chinese Remainder Theorem Then w1 w2

The Chinese Remainder Theorem

Chinese Remainder Theorem: If m

Our simultaneous congruences are

Our goal is to find integers w

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

Once we have found w

Moreover, as long as the moduli (m

First define: z

Note that

0 (mod m

Next define: y

0 (mod m

0 (mod m

1 (mod m

Lastly define: w

Then w

Example: Solve the simultaneous congruences

We compute