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
    10
    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
    10
    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
    10
    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
    10
    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, 01:37 PM
  2. Chinese Postman Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 5th 2009, 04:24 AM
  3. A chinese puzzle with coins
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: April 14th 2009, 09:28 AM
  4. chinese remainder
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 10:20 AM
  5. Chinese Roulette?
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 25th 2008, 03:23 AM

Search Tags


/mathhelpforum @mathhelpforum