All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
An old egg problem (Posted on 2019-11-05) Difficulty: 2 of 5
An old woman went to the market and a horse stepped on her basket and smashed her eggs. The rider offered to pay for the eggs and asked her how many there were. She did not remember the exact number, but when she had taken them two at a time there was one egg left, and the same happened when she took 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?

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution re: more formally - no guessing | Comment 4 of 5 |
(In reply to more formally by Steven Lord)

The problem essentially asks to find integer x to solve a system of congruences:
x = 1 mod 60
x = 0 mod 7
With 60 and 7 being coprime, solving this is basically applying the Chinese Remainder Theorem.  The wikipedia page on the theorem has a lot of useful info. https://en.wikipedia.org/wiki/Chinese_remainder_theorem

An explicit solution can be found by first calculating a pair of values S and T such that 60*S + 7*T = 1.  Then a solution x = 0*60*S + 1*7*T.  To solve for S and T this without guessing an extended Euclidean algorithm can be applied. https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

index | quotient | remainder |     S value |      T value
  0   |          |     60 |      1  |      0
  1   |          |      7 |     0  |     1
  2   |  60/7=8  |  60-7*8=4 |  1-0*8=1  |  0-1*8=-8
  3   |   7/4=1  |   7-4*1=3 |  0-1*1=-1 | 1-(-8)*1=9
  4   |   4/3=1  |   4-3*1=1 | 1-(-1)*1=2 | -8-9*1=-17
  5   |   3/1=3  |   3-1*3=0 | Stop here

The S and T values from the last nonzero remainder are the values needed.  Then 60*2 + 7*(-17) = 1.  Then back to the Chinese Remainder Theorem.  If we already have 60*2 + 7*(-17) = 1 then x = 0*60*2 + 1*7*(-17) = -119.  Then the smallest positive integer solution is -119+60*7 = 301.

  Posted by Brian Smith on 2019-11-06 11:11:49
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2021 by Animus Pactum Consulting. All rights reserved. Privacy Information