Results 1 to 3 of 3

Math Help - The chinese remainder theorem.

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    54

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2009
    Posts
    54

    Thanks!!!

    Quote Originally Posted by hatsoff View Post
    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!!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2010, 07:56 PM
  2. Chinese remainder theorem 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 19th 2009, 10:38 AM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2009, 08:26 PM
  4. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 01:27 AM
  5. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 29th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum