Modular Arithmetic - Finding the smallest possible length of the room in inches

Question

I need to know if I've done this proof correctly.

Question: A rectangular room is to be tiled with square tiles. Consider only the length of the room. The tiles are available in 9-inch, 10-inch, or 11-inch squares. If only 9-inch tiles are used, there is a 5 inch gap at one wall. If only 10-inch tiles are used, there is a 7 inch gap. And if only 11-inch tiles are used, there is a 2 inch gap. Find the smallest possible length of the room in inches.

My attempt:

The three congruences are

$ x \equiv 5 $ (mod 9)

$x \equiv 7 $ (mod 10)

$ x \equiv 2 $ (mod 11)

We solve the system by letting

$x =f_1+f_2+f_3$

To compute $f_1$ we set $f_1 = 10 \times 11 \times b_1$ where $b_1$ satisfies the single congruence.

$110b_1 \equiv 5 $ (mod 9)

$2b_1 \equiv 5 $ (mod 9)

$2b_1-5 = 9k$

$2b_1=9k+5$

$b_1 = \frac{9k+5}{2}$

If we let $k = 1$, then

$b_1 = \frac{9+5}{2}$

$b_1 = \frac{14}{2}$

$b_1 = 7$

Thus $f_1 = 10 \times 11 \times 7 = 770$

Similarly, set $f_2 = 9 \times 11 \times b_2$

$99b_2 \equiv 7$ (mod 10)

$9b_2 \equiv 7$ (mod 10)

$9b_2 - 7 =10k$

$9b_2 =10k+7$

$b_2 = \frac{10k+7}{9}$

If we let $k=2$, then

$b_2 = \frac{20+7}{9}$

$b_2 = \frac{27}{9}$

$b_2 =3$

Thus $f_2 = 9 \times 11 \times 3 =297$

Also, set $f_3 = 10 \times 9 \times b_3$

$90b_3 \equiv 2 $ (mod 11)

$2b_3 - 2 =11k$

$2b_3 =2 +11k$

$b_3 =\frac{2+11k}{2}$

If we let $k = 0$, we have $b_3 =\frac{2}{2}$

$b_3 =1$

Thus $f_3 = 10 \times 9 \times 1 = 90$

This means $x = 770+297+90 = 1157$

Since $ 9 \times 10 \times 11 = 990$, we need to reduce $1157$ modulo $990$. The smallest possible length is $167$ inches.

Answer 1

Looks good to me (I didn't absolutely check all the figures). However there are short cuts and you could solve the three congruences doing much less work.

• $110b_1\equiv5\pmod9\Rightarrow 2b_1\equiv5\pmod9\Rightarrow 2b_1\equiv14\pmod9\Rightarrow b_1\equiv7\pmod9$
• $99b_2\equiv7\pmod{10}\Rightarrow -b_2\equiv-3\pmod{10}\Rightarrow b_2\equiv3\pmod{10}$
• $90b_3\equiv2\pmod{11}\Rightarrow 2b_3\equiv2\pmod{11}\Rightarrow b_3\equiv1\pmod{11}$

By the way there is no need for the $b_k$ to be positive. Even easier for the first step would be

• $110b_1\equiv5\pmod9\Rightarrow 2b_1\equiv-4\pmod9\Rightarrow b_1\equiv-2\pmod9$.

Answer 2

Simpler: $\ 3,5,11\mid x\!-\!2\,$ so $\, x = 2\! +\! 165k.\,$ Checking $\,k=0,1,\ldots, 5 $ we see $\,2\!+\!165$ works.