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

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

Thanks!

Printable View

- Jun 12th 2011, 01:26 PMorbitThe 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.

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

Thanks! - Jun 12th 2011, 07:07 PMhatsoff
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 $\displaystyle \mathbb{Z}/p_1^{\alpha_1}\mathbb{Z}\times\cdots\times\mathbb{ Z}/p_n^{\alpha_n}\mathbb{Z}$ to $\displaystyle \mathbb{Z}/p_1^{\alpha_1}\cdots p_n^{\alpha_n}\mathbb{Z}$, for distinct primes $\displaystyle p_1,\cdots,p_n$ and positive integers $\displaystyle \alpha_1,\cdots,\alpha_n$, and it is an isomorphism.

To apply the theorem here, we have an element $\displaystyle (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 $\displaystyle \mathbb{Z}/2^3 5^2 3^4\mathbb{Z}$. By the euclidean algorithm we can find linear combinations

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

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

$\displaystyle 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:

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

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

$\displaystyle 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 PMorbitThanks!!!