# A part of modular arithmetic I jut dont get, badly stuck for an answer. Help please? [closed]

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?

## closed as off-topic by Cameron Buie, Marconius, Rory Daulton, 6005, graydadNov 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$?

$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$.

• 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.\:$

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.

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$.