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

Thanks!

Printable View

- Jun 12th 2011, 02: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.

Thanks! - Jun 12th 2011, 08: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 to , for distinct primes and positive integers , and it is an isomorphism.

To apply the theorem here, we have an element , and we want to find the associated element in . By the euclidean algorithm we can find linear combinations

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:

and this is the solution mod . Reducing we get

.

This equivalence class captures all the solutions to the system by the CRT. - Jun 12th 2011, 08:52 PMorbitThanks!!!