Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 threes there are 2 eggs leftover, counting in fives there are 2 eggs leftover and counting in sevens there are 3 eggs leftover. How many eggs are in the basket?

share|cite|improve this question

closed as off-topic by Cameron Buie, Marconius, Rory Daulton, 6005, graydad Nov 8 '15 at 2:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Cameron Buie, Marconius, Rory Daulton, 6005, graydad
If this question can be reworded to fit the rules in the help center, please edit the question.

This has only to do with modular arithmetic, please remove the other three tags. – Lord_Farin Oct 17 '12 at 17:09

Could you write this up? $$\begin{align} x&\equiv 2 \pmod{3} \\ x &\equiv 2 \pmod{5} \\ x & \equiv 3 \pmod{7} \end{align}$$

These are small numbers, you can also find manually a common remainder of these three. In general, if $\gcd(m,n)=1$, then

$$\big( x\equiv a\pmod{m}\ \text{ and }\ x\equiv a\pmod{n} \big) \iff x\equiv a \pmod{mn}$$

Well, two of the remainders above are already common, so we can write one instead of them: $$\begin{align} x&\equiv 2 \pmod{15} \\ x & \equiv 3 \pmod{7} \end{align}$$

Now. Can you find a common remainder of them?

Well, for example $2\equiv 17 \pmod{15}$ and $17\equiv 10 \equiv 3 \pmod{7}$, so $x\equiv 17$ is good: $$x\equiv 17 \pmod{3\cdot 5\cdot 7}$$ How many solutions does it give between $100$ and $200$?

share|cite|improve this answer
The first step uses the constant-case optimization of CRT, which often proves handy in practice. You can find many examples in my prior posts. The second step is best generally done with Easy CRT. $\ \ $ – Bill Dubuque Oct 17 '12 at 17:39

$x=2+3k$. Therefore $2+3k \equiv 2 \ \ (5)$. This gives $k=5t$. So, $x=2+15t$. Finally $2+15 t \equiv 3 \ \ (7)$ which means that $t=1+7s$. So, $x=17 +105 s$. For $s=1$ we get $x=122$.

share|cite|improve this answer
Note that $\:122 \equiv 17\pmod{\!105 = 3\cdot 5\cdot 7}.\ \ $ – Bill Dubuque Oct 17 '12 at 17:34

Hint $\rm\ 5,7\:|\:2x\!+\!1\:\Rightarrow\:35\:|\:2x\!+\!1\:\Rightarrow\:mod\ 35\!:\ x\equiv \dfrac{-1}2\equiv \dfrac{34}2\equiv 17.\:$ Also $17\equiv 2\pmod 3.\:$

share|cite|improve this answer

Use the Chinese remainder theorem. Working with the congruences $x \equiv 2 \pmod{3}$ and $x \equiv 2 \pmod{5}$, we compute the multiplicative inverse of 3 modulo 5 as 2, and of 5 modulo 3 as 2; hence $x \equiv 2 \cdot 5 \cdot 2 + 2 \cdot 3 \cdot 2 \equiv 2 \pmod {15}$. Repeating for the congruences $x \equiv 2 \pmod{15}$ and $x \equiv 3 \pmod{7}$, we get the multiplicative inverse of 7 modulo 15 is 13 and of 15 modulo 7 is 1; hence $x \equiv 2 \cdot 7 \cdot 13 + 3 \cdot 15 \cdot 1 \equiv 17 \pmod{105}$. 122 is the only integer between 100 and 200 with remainder 17 modulo 105.

share|cite|improve this answer

Let $n$ be the number of eggs in the basket. By hypothesis, both $3$ and $5$ are factors of $n-2$, so $15$ is a factor of $n-2$, and so $n=15j+2$ for some integer $j$. Since $100\le n\le 200$ and $j$ is an integer, then $7\le j\le 13$. At this point, you want to see which of these $j$ will give $n=15j+2$ the form $n=7m+3$ for some integer $m$. In other words, you want to find for which of these $j$ that $7$ is a factor of $n-3=15j-1$. Well, $n-3=14j+j-1$, and $7$ is always a factor of $14j$, so we really only need to choose our $j$ so that $7$ is a factor of $j-1$. The only possibility is $j=8$, whence $n=15j+2=122$.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.