Is there a simple algorithm I can use for this?

Question

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.

Answer 1

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$