0

Apologies, I know I have asked a few questions already.

The question is : A housewife is travelling to market with all her eggs in one basket. She has between $100$ and $200$ eggs in the basket. Counting in three's there is one left over. Counting in fives's there is four left over, counting in seven's there is four left over. How many eggs are in the basket?

I know there is a question very similar to this on here, but unfortunately I don't understand it fully.

So my attempt is :

We have three equations

$x \equiv 1 \pmod{3}\\$ $x \equiv 4 \pmod{5}\\$ $x \equiv 4 \pmod {7}\\$

So now

$x \equiv 1 \pmod {3}$ and $x \equiv 4 \pmod {35}$

I don't know what to do now

moony
  • 720
  • $$x \equiv 4 \pmod{35} \implies x = 35k + 4$$ Plug this in the first congruence and solve $k$ – AgentS Oct 02 '14 at 13:54

2 Answers2

2

If we remove the restriction that the number of eggs is between 100 and 200, then having 4 eggs satisfy all the congruences. By the Chinese Remainder Theorem, since all the modulos are coprime to each other, all numbers satisfying the conqruences will be equal to $4$ modulo $3 \times 5 \times 7 = 105$. There's only one such solution that lies between $100$ and $200$, namely $105 + 4$.

Irvan
  • 2,208
  • Thank you, makes great sense now. I find modular arithmetic very hard, but you have made it easier thank you – moony Oct 02 '14 at 13:55
2

Irvan's answer is good, but I just wanted to make a point: this question is intentionally set to be very simple to "crack" without knowing much about modular arithmetic.

The "first guess" of $4$ is immediately seen to solve all the three congruences, so the answer immediately follows from Chinese Remainder Theorem.

However, even a slight tweak to the question would've made it a lot harder. For instance, if the wife had two left over when counting in threes (with all else being the same), then the solution isn't immediately apparent anymore.

In which case, it becomes necessary to apply a little formal modular arithmetic.

From the latter two congruences, $x = 35t + 4$.

Substituting that into the first congruence (in my altered question), $$35t + 4 \equiv 2 \pmod 3 \implies 35t \equiv -2 \pmod 3 \implies 35t \equiv 1 \pmod 3 \implies \\ t \equiv 35^{-1} \pmod 3$$

Now, to solve for $t$ involves computing the multiplicative inverse of $35$ modulo $3$. This involves an application of the Extended Euclidean Algorithm, and there are a few implementations which you can google for. I personally favour the "magic box" method, which you can also search for. Anyway you can work out that $35^{-1} \equiv 2 \pmod 3$, so $t \equiv 2 \pmod 3$. Hence you can say $t = 3k + 2$, which allows you to get the final solution as $x = 35(3k+2)+4 = 105k + 74$. Within the required range, the only admissible value of $x$ is $105 + 74 = 179$.

You don't necessarily have to compute the modular inverse in this case, you can also test different values of $t$ till you find one that satisfies the first congruence. In this case, you should still be able to find $t=2$ relatively quickly. However, I wanted to show you that there's a rigorous algorithm to solve the first congruence without needing to guess and check.

But my main point is this: you can see that the small tweak I applied to the conditions of the question have caused the smallest positive solution to "shoot up" from something small like $4$ to something quite a bit larger like $74$ which simply isn't possible to immediately/intuitively "see" unless you're a savant. I just wanted to illustrate that the solutions may not always come so easily as in this (original) question, but if you learn the principles and methods rigorously, you won't ever be daunted even by a tough question.

Deepak
  • 26,801
  • For this specific instance where all modulus are prime, we can use fermat little theorem to calculate the inverse in clean mathematical form. – Irvan Oct 02 '14 at 17:19