Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
This has only to do with modular arithmetic, please remove the other three tags. –  Lord_Farin Oct 17 '12 at 17:09
    
Sorry, do you know the answer though?? –  Dara Oct 17 '12 at 17:17
    
Can i just have an answer instead of yer editing?? –  Dara Oct 17 '12 at 17:27
1  
Really, is four answers not enough for you? Come on, calm down. –  Lord_Farin Oct 17 '12 at 17:30
1  
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. If this is homework, please add the homework tag –  Julian Kuelshammer Oct 18 '12 at 8:43

5 Answers 5

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|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|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|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|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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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