Results 1 to 11 of 11

Math Help - Chinese Rem. Thm.

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Chinese Rem. Thm.

    1.) Utilizing the Chin. Rem. Thm., find 5 consec. pos. integers such that the following conditions hold: the first is div. by 2, the 2nd is div by 3, the 3rd is div by 5, the 4th is div. by 7 and the final (the 5th) is div. by 11.

    2.) Now, prove for any pos. integer n, there will exist n consecutive pos. integers a_1, a_2, ..., a_n, such that p_i | a_i for each i, where the p_i illustrates the i-th prime.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    1.) Utilizing the Chin. Rem. Thm., find 5 consec. pos. integers such that the following conditions hold: the first is div. by 2, the 2nd is div by 3, the 3rd is div by 5, the 4th is div. by 7 and the final (the 5th) is div. by 11.
    Let x be the first positive integer.

    Then,
    x = 0 (mod 2)
    x+1 = 0 (mod 3)
    x+2 = 0 (mod 5)
    x+3 = 0 (mod 7)
    x+4 = 0 (mod 11)

    Hence,
    x = 0 (mod 2)
    x = -1 (mod 3)
    x = -2 (mod 5)
    x = -3 (mod 7)
    x = -4 (mod 11)

    Write in normal form,
    x = 0 (mod 2)
    x = 2 (mod 3)
    x = 3 (mod 5)
    x = 4 (mod 7)
    x = 7 (mod 11)

    And the moduli are relatively prime to each other, that is exactly the form we need.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post

    2.) Now, prove for any pos. integer n, there will exist n consecutive pos. integers a_1, a_2, ..., a_n, such that p_i | a_i for each i, where the p_i illustrates the i-th prime.
    Just generalize what I did.

    And we end up with the following congruences,
    x = 0 (mod p_1)
    x = -1 (mod p_2)
    ....
    x = -(n-1) (mod p_n)
    Because these are prime numbers we have that,
    gcd(p_i,p_j)=1
    For 1<= i,j<=n
    And hence by the Chinese Remainder Theorem there exists such an integer.
    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by ThePerfectHacker View Post
    Just generalize what I did.

    And we end up with the following congruences,
    x = 0 (mod p_1)
    x = -1 (mod p_2)
    ....
    x = -(n-1) (mod p_n)
    Because these are prime numbers we have that,
    gcd(p_i,p_j)=1
    For 1<= i,j<=n
    And hence by the Chinese Remainder Theorem there exists such an integer.
    Q.E.D.
    Why are you so smart? You're simply amazing

    Thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Ideasman View Post
    Why are you so smart? You're simply amazing

    Thanks
    i think it's these weird drugs he's taking
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Why are you so smart? You're simply amazing
    Because I came from Union of Soviet Socialist Republic.

    i think it's these weird drugs he's taking
    What did Erdos use again?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by ThePerfectHacker View Post
    Let x be the first positive integer.

    Then,
    x = 0 (mod 2)
    x+1 = 0 (mod 3)
    x+2 = 0 (mod 5)
    x+3 = 0 (mod 7)
    x+4 = 0 (mod 11)

    Hence,
    x = 0 (mod 2)
    x = -1 (mod 3)
    x = -2 (mod 5)
    x = -3 (mod 7)
    x = -4 (mod 11)

    Write in normal form,
    x = 0 (mod 2)
    x = 2 (mod 3)
    x = 3 (mod 5)
    x = 4 (mod 7)
    x = 7 (mod 11)

    And the moduli are relatively prime to each other, that is exactly the form we need.
    Hi TPH,

    I was following your work. Once you get to the "normal form" it is now that I have to use the Chinese Remainder Theorem right? This will give me the 5 consecutive pos integers?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    Hi TPH,

    I was following your work. Once you get to the "normal form" it is now that I have to use the Chinese Remainder Theorem right? This will give me the 5 consecutive pos integers?
    Yes, but be careful, x is the first among these integers.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by ThePerfectHacker View Post
    Yes, but be careful, x is the first among these integers.
    Alright, I attempted doing the chinese rem. theorem but ran into difficulty. In my notes, I have:

    x = a_1*M_1*y_1 + a_2*M_2*y_2 + ... a_k*M_k*y_k ; m_i = M/m_i and y_i satisfies M_i*y_i = 1 (mod m_i)

    Ah this formula looks confusing and I think it's simpler than I am making it out to be. It would have been nice if my prof. at least gave us an example.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Aug 2012
    From
    usa
    Posts
    17

    Re: Chinese Rem. Thm.

    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jul 2012
    From
    Jaipur,Rajasthan
    Posts
    36
    Thanks
    1

    Re: Chinese Rem. Thm.

    I like this concept.I have read something like it very long ago.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Thm
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: April 8th 2010, 12:37 PM
  2. Chinese Postman Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 5th 2009, 03:24 AM
  3. A chinese puzzle with coins
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: April 14th 2009, 08:28 AM
  4. chinese remainder
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 09:20 AM
  5. Chinese Roulette?
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 25th 2008, 02:23 AM

Search Tags


/mathhelpforum @mathhelpforum