Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By chiro
  • 1 Post By HallsofIvy

Math Help - Solve using the Chinese Remainder Theorem

  1. #1
    Junior Member
    Joined
    Feb 2013
    From
    Charlotte, NC
    Posts
    50

    Solve using the Chinese Remainder Theorem

    An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,163
    Thanks
    761

    Re: Solve using the Chinese Remainder Theorem

    Hey Civy71.

    The first thing I suggest you do is write out the system of congruence equations first given your data. You will have one for each of the items including mod 2, mod 3, mod 4, mod 5, mod 6, and mod 7.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,418
    Thanks
    1854

    Re: Solve using the Chinese Remainder Theorem

    I am puzzled by this. Where did you get this problem? Obviously, whoever gave you this problem expects you to know what the "Chinese Remainder Theorem" is! If you do, why have you not at least tried to solve it yourself?
    Last edited by HallsofIvy; June 15th 2013 at 08:25 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,418
    Thanks
    1854

    Re: Solve using the Chinese Remainder Theorem

    Since this has been here a week now and we have not heard back from Civy71, if anyone is interested, the "Chinese Remainder Theorem" say, in modern language (I can't write Chinese!) "The solution to a system of equation x= a (mod n1), x= a (mod n2), ..., x= a (mod nk) (that is, x is congruent to the same thing, a, modulo k different numbers) satisfies x= a (mod m) where m is the least common multiple of n1, n2, ..., nk.


    "she had taken them out two at a time, there was one egg left.[/quote]
    That is, if you divide the number of eggs, n, by 2, the remainder is 1: n= 1 (mod 2)

    "The same happened when she picked them out three, four, five, and six at a time'
    If you divide n by 3, 4, 5, and 6, the remainder is 1: n= 1 (mod 3), n= 1 (mod 4), n= 1(mod 5), and n= 1 (mod 6).

    The least common multiple of 2, 3, 4, 5, and 6 is 3(4)(5)= 60. n= 1 (mod 6) which means n is a multiple of 60 plus 1: n= 60i+ 1 for some integer i.

    "but when she took them seven at a time they came out even."
    n is a multiple of 7: n= 7j for some integer j. We now have n= 7j= 7j60i+ 1, or 7j- 60i= 1, a "Diophantine equation".

    To solve that, note that 7 divides into 60 8 times with remainder 4: 60- 8(7)= 4.
    4 divides into 7 once with remainder 3: 7- 4= 3.
    3 divides into 4 once with remainder 1: 4- 3= 1.

    Replace that "3" in 4- 3= 1 with 7- 4: 4- (7- 4)= 2(4)- 7= 1.
    Replace the "4" in that with 60- 8(7): 2(60- 8(7))- 7= 2(60)- 17(7)= 1. But we wanted j(7)- i(60)= 1, with the subtraction reversed. Okay, us negative values: -(-2)(60)+ (-17)(7)= 1. That is, a solution to "j(7)- i(60)= 1" is j= -17, i= -2. But it is easy to see that j= -17+ 60k, i= -2+ 17k is also a solution, for any integer k: (-17+ 60k)(7)- (-2+ 17k)(60)= -121+ 420k+ 120- 420k= 1. Taking k= 1 gives j= p17+ 60= 43, i= -2+ 17= 15. n= 7j= 7(43)= 301.

    And, it is easy to check: 2 divides into 301 150 times with remainder 1. 3 divides into 301 100 times with remainder 1. 4 divides into 301 75 times with remainder 1. 5 divides into 301 60 times with remainder 1, 6 divides into 301 5 times with remainder 1. And, finally, 7 divides into 301 exactly 43 times, with no remainder.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem Help
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 21st 2012, 03:08 PM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: September 6th 2012, 09:19 AM
  3. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 15th 2008, 07:12 PM
  4. Chinese Remainder Theorem 3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 27th 2007, 12:27 PM
  5. Chinese Remainder Theorem 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2007, 09:00 PM

Search Tags


/mathhelpforum @mathhelpforum