Learn / Library / Brainteasers

Combined remainders

BrainteasersMedium

Find the smallest positive integer that leaves remainder $3$ when divided by $7$ , remainder $5$ when divided by $8$ , and remainder $1$ when divided by $9$ .

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

List the numbers that leave remainder $1$ on division by $9$ and keep only those that also fit the other conditions, stepping by the product of the moduli already satisfied.

Solution

Numbers with remainder $1$ modulo $9$ are $9 k + 1$ , and $9 k + 1$ leaves remainder $5$ modulo $8$ exactly when $k$ leaves remainder $4$ modulo $8$ , so the first candidate is $37$ and the rest are $37 + 72 t$ .
Modulo $7$ we have $37 \equiv 2$ and $72 \equiv 2$ , so $37 + 72 t \equiv 2 + 2 t$ , and we need this to be $3$ modulo $7$ .
That means $2 t \equiv 1$ modulo $7$ , so $t \equiv 4$ modulo $7$ , and the smallest value is $t = 4$ .
The number is $37 + 72 \times 4 = 325$ .

Answer: $325$

Next question Back to the library