Number theory problem on Chinese remainder theorem

Question

Let $T$ be the smallest positive integer which, when divided by $11,13,15$ leaves remainders in the sets $\{7,8,9\},\{1,2,3\},\{4,5,6\}$ respectively. What is the sum of the squares of the digits of $T$?

My working

After applying CRT, I got

$T\equiv 469+1365a+495b+286c\,\, \left(\mod 2145\right)$ where $a,b,c\in\{0,1,2\}$

Now what to do should I check all 27 cases?

By trail and error I got $T=184,$ for $a=1,b=1,c=0$

Is this smallest?

Answer 1

In answer to your specific question, yes. I thought that the simplest (although possibly not quickest) way to check would be to check all the consecutive triplets satisfying the condition for remainder upon division by $15$, up to $184$. For the sake of having a more complete answer, these are:

$\{19,20,21\}$, $\{34,35,36\}$, $\{49,50,51\}$, $\{64,65,66\}$, $\{79,80,81\}$, $\{94,95,96\}$, $\{109,110,111\}$, $\{124,125,126\}$, $\{139,140,141\}$, $\{154,155,156\}$, $\{169,170,171\}$, $\{184,185,186\}$.

The first number that works is $184$.

Answer 2

The simplest solution is to use computer support to verify. (There is nothing structural in the given setting, and it is a finite quick search.) For instance, using sage:

sage: for k in [1..10000]:
....:     if k%11 in (7,8,9) and k%13 in (1,2,3) and k%15 in (4,5,6):
....:         print k
....:         break
....:     
184

This answer is a check. (Not a human unaided solution. But the aids do not differ much from what was needed to post the question...)

---

Later edit. It seems that a "human other solution" is needed. In this case the best way to get a quick answer is for me the following one. We work modulo $15$ first. The first $13$ possibilities for a match modulo $15$ are as follows, and in the contest we really write them down:

sage: for k in [0..12]:
....:     print "%3s %3s %3s" % ( 15*k + 4, 15*k + 5, 15*k + 6 )
....:     
  4   5   6
 19  20  21
 34  35  36
 49  50  51
 64  65  66
 79  80  81
 94  95  96
109 110 111
124 125 126
139 140 141
154 155 156
169 170 171
184 185 186

The computer was only helping me type the stuff. Now we further check the condition modulo $13$, which repeats in the next set/package, too. The possible numbers are than among the above:

sage: f = lambda k:    k if k%13 in (1,2,3) else '-'
sage: for k in [0..12]:
....:     print "%3s %3s %3s" % ( f(15*k + 4), f(15*k + 5), f(15*k + 6) )
....:     
  -   -   -
  -   -   -
  -   -   -
  -   -   -
  -   -  66
 79  80  81
 94   -   -
  -   -   -
  -   -   -
  -   -   -
  -   -   -
  - 170 171
184 185   -

In the contest i would have underlined in the already typed columns. This is again simple to check with bare hands, and it also gives the pattern. The above numbers match the conditions modulo $13$, and modulo $15$. The next numbers are obtained by adding $13\cdot 15$ to the above "package". Now we search in the list the first one that also matches the condition modulo $11$. If not above, then in the next package, if even not, than we add once more $13\cdot 15$.

The solution is $184$, the above numbers taken modulo $11$ are...

sage: f = lambda k:    k%11 if k%13 in (1,2,3) else '-'
sage: for k in [0..12]:
....:     print "%3s %3s %3s" % ( f(15*k + 4), f(15*k + 5), f(15*k + 6) )
....:     
  -   -   -
  -   -   -
  -   -   -
  -   -   -
  -   -   0
  2   3   4
  6   -   -
  -   -   -
  -   -   -
  -   -   -
  -   -   -
  -   5   6
  8   9   -

Note: If the condition modulo $11$ would have been to hit the reminder $1$ and/or $7$, then we would have to go to the next "package" with numbers obtained from the already typed ones by adding $13\times 15$, which is $2\times 4=8$ modulo $11$, so we add $8$ to the above computed reminders and look for the first $1$ and/or $7$...