# Is there a simple algorithm I can use for this?

if I were asked to find all integers between 1 and 100 that leave remainder 3 on division by 5 and leave remainder 4 on division by 7, how would I go about this? It seems like such a simple question yet I am not sure if there is a simple algorithm that I can use? It should jump out at me but it doesn't seem to.

-
Do you know how to do it if you have only one constraint, leaving a remainder of $r$ on division by $d$? –  Daniel Fischer Aug 10 '14 at 11:19
CRT: Chinese Remainder Theorem. en.wikipedia.org/wiki/Chinese_remainder_theorem. To find one of solutions ($18$), then $\pm 35, \pm 70, \pm 105, ...$, while they were in $[1,100]$. –  Oleg567 Aug 10 '14 at 11:27

## 1 Answer

As suggested by oleg567 you have to solve the following

$\begin{cases} x \equiv 3 \pmod{5}\\ x \equiv 4 \pmod{7}\\ \end{cases}$

or you can write

$\begin{cases} x=3+5t\\ x=4+7s \end{cases}$

Now after subtituting the value of $x$ from first equation into the second equation you will have

$3+5t=4+7s$

or you can write

$3+5t=4 \pmod{7}$ $\hspace{0.3cm}$$\implies$$\hspace{0.3cm}$$5t=1 \pmod{7} \implies t=5^{-1} \pmod{7}=3 \pmod{7} So t=3+7s Hence x=3+5t=3+5(3+7s)=18+35s Hence the all integers between\hspace{0.1cm}$$1$ and $100$ that leave remainder $3$ on division by $5$ and leave remainder $4$ on division by $7$ are

$x=18,53,88$

-