The chinese remainder theorem.

**orbit** · June 12th 2011, 01:26 PM

Hello,I need to solve this system using the chinese remainder theorem, the problem is that I don´t know how to use it.

$x \equiv 1\left( 8 \right),x \equiv 2\left( {25} \right),x \equiv 3\left( {81} \right)$

Thanks!

**hatsoff** · June 12th 2011, 07:07 PM

The watered-down version of the CRT (which is all you need for stuff like this) tells us that there is a natural map from $\mathbb{Z}/p_1^{\alpha_1}\mathbb{Z}\times\cdots\times\mathbb{ Z}/p_n^{\alpha_n}\mathbb{Z}$ to $\mathbb{Z}/p_1^{\alpha_1}\cdots p_n^{\alpha_n}\mathbb{Z}$ , for distinct primes $p_1,\cdots,p_n$ and positive integers $\alpha_1,\cdots,\alpha_n$ , and it is an isomorphism.

To apply the theorem here, we have an element $(1,2,3)\in\mathbb{Z}/2^3\mathbb{Z}\times\mathbb{Z}/5^2\mathbb{Z}\times\mathbb{Z}/3^4\mathbb{Z}$ , and we want to find the associated element in $\mathbb{Z}/2^3 5^2 3^4\mathbb{Z}$ . By the euclidean algorithm we can find linear combinations

$1(25\cdot 81)-253(8)=1$

$12(8\cdot 81)-311(25)=1$

$32(8\cdot 25)-79(81)=1$

Each of these equalities corresponds to a value 1, 2 or 3 (mod 8, 25 and 81, respectively). Take the first term in the left of each expression, multiply it by the corresponding value 1/2/3, and then add them all together. We get:

$1(25\cdot 81)(1)+12(8\cdot 81)(2)+32(8\cdot 25)(3)=36,777$

and this is the solution mod $8\cdot25\cdot81=16,200$ . Reducing we get

$x\equiv 4,377\pmod{16,200}$ .

This equivalence class captures all the solutions to the system by the CRT.

**orbit** · June 12th 2011, 07:52 PM

Originally Posted by hatsoff

the watered-down version of the crt (which is all you need for stuff like this) tells us that there is a natural map from $\mathbb{z}/p_1^{\alpha_1}\mathbb{z}\times\cdots\times\mathbb{ z}/p_n^{\alpha_n}\mathbb{z}$ to $\mathbb{z}/p_1^{\alpha_1}\cdots p_n^{\alpha_n}\mathbb{z}$ , for distinct primes $p_1,\cdots,p_n$ and positive integers $\alpha_1,\cdots,\alpha_n$ , and it is an isomorphism.

To apply the theorem here, we have an element $(1,2,3)\in\mathbb{z}/2^3\mathbb{z}\times\mathbb{z}/5^2\mathbb{z}\times\mathbb{z}/3^4\mathbb{z}$ , and we want to find the associated element in $\mathbb{z}/2^3 5^2 3^4\mathbb{z}$ . By the euclidean algorithm we can find linear combinations

$1(25\cdot 81)-253(8)=1$

$12(8\cdot 81)-311(25)=1$

$32(8\cdot 25)-79(81)=1$

each of these equalities corresponds to a value 1, 2 or 3 (mod 8, 25 and 81, respectively). Take the first term in the left of each expression, multiply it by the corresponding value 1/2/3, and then add them all together. We get:

$1(25\cdot 81)(1)+12(8\cdot 81)(2)+32(8\cdot 25)(3)=36,777$

and this is the solution mod $8\cdot25\cdot81=16,200$ . Reducing we get

$x\equiv 4,377\pmod{16,200}$ .

This equivalence class captures all the solutions to the system by the crt.

thanks!!!

Thread: The chinese remainder theorem.

LinkBack

Thread Tools

Display

The chinese remainder theorem.

Thanks!!!

Similar Math Help Forum Discussions

Chinese Remainder Theorem

Chinese remainder theorem 2

Chinese Remainder Theorem

Chinese Remainder Theorem

chinese remainder theorem

Search Tags