# The chinese remainder theorem.

• Jun 12th 2011, 01:26 PM
orbit
The chinese remainder theorem.
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!
• Jun 12th 2011, 07:07 PM
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.
• Jun 12th 2011, 07:52 PM
orbit
Thanks!!!
Quote:

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!!!