SECTION 2.1 Elementary Number Theory 69
An old woman goes to market and a horse steps on her basket
and crushes 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 she remembered that 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?The solution of the above is expressed by a system of congruences:
ifmis the number of eggs that the old woman had, then
m≡1(mod 2)
m≡1(mod 3)
m≡1(mod 4)
m≡1(mod 5)
m≡1(mod 6)
m≡0(mod 7)Expressed in terms of integers modulon for variousn, we can express
the above as
m 2 = 1 2 ; m 3 = 1 3 ; m 4 = 1 4 ; m 5 = 1 5 ; m 6 = 1 6 ; m 7 = 0 7.Note first that there is some redundancy in the above problem.
Namely, notice that ifm 4 = 1 4 , then surelym 2 = 1 2. Indeed,
m 4 = 1 4 =⇒ 4 |(4−1)
=⇒ 2 |(4−1)
=⇒ m 2 = 1 2.In exactly the same way we see that the conditionm 6 = 1 6 implies that