Question

there are two integers between 1 and 100 such that for each: if you divide by 4, the remainder is 3; if you divide by 3, the remainder is 1; if you divide by 5, the remainder is 1. what is the sum of those two integers?

Answer 1

Let
`n` be an integer such that

`\begin{cases} n \equiv 1 \pmod 3 \\ n \equiv 3 \pmod 4 \\ n \equiv 1 \pmod 5 \end{cases}`

Note that (3, 4, 5) are mutually coprime, so we can use the Chinese remainder theorem.

Starting with

`n = 1 + 3 + 1`

we adjust to

`n = (1\cdot4\cdot5) + (3\cdot3\cdot5) + (1\cdot3\cdot4)`

to make computing the residues a bit easier.

• Taken modulo 3, we have

`n \equiv 20 + 0 + 0 \equiv 2 \\ot\equiv 1 \pmod 3`

so we need to further adjust the first term by introducing the inverse of 2 modulo 3. We have

`2\cdot2 \equiv 4 \equiv 1 \pmod 3 \implies 2^(-1) \equiv 2 \pmod 3`

Then

`n = (1\cdot4\cdot5\cdot2) + (3\cdot3\cdot5) + (1\cdot3\cdot4)`

• Taken modulo 4, we have

`n \equiv 0 + 45 + 0 \equiv 1 \\ot\equiv 3 \pmod 4`

We need another inverse; we have

`3\cdot3 \equiv 9 \equiv 1 \pmod 4 \implies 3^(-1) \equiv 3 \pmod 4`

and so

`n = (1\cdot4\cdot5\cdot2) + (3\cdot3\cdot5\cdot3) + (1\cdot3\cdot4)`

• Taken modulo 5, we have

`n \equiv 0 + 0 + 12 \equiv 2 \\ot\equiv 1 \pmod 5`

One more inverse:

`2\cdot3 \equiv 6 \equiv 1 \pmod 5 \implies 2^(-1) \equiv 3 \pmod 5`

and so

`n = (1\cdot4\cdot5\cdot2) + (3\cdot3\cdot5\cdot3) + (1\cdot3\cdot4\cdot3)`

Simplifying, we have
`n = 211`, and by the CRT we have

`n \equiv 211 \pmod{3\cdot4\cdot5} \implies n \equiv 31 \pmod{60}`

which is to say
`n=60k + 31` where
`k` is an integer.

The two integers that fall between 1 and 100 occur for
`k\in\{0,1\}`; they are 31 and 31 + 60 = 91, and their sum is 31 + 91 = 122.