Q:

I can't solve this modulo operation

I'm trying to find an easy and fast way to get the result of
$$353094232 \mod 721.$$
I would solve this by dividing manually the terms until I get the remainder of dividing, but I was wondering if there is a faster way, like breaking down $721$ in $7\cdot 103$ and doing something.
I can't find any theorem or property regarding this specific case.
Thanks, 
Dave

A:

It can be done in a minute of mental arithmetic via CRT. Note $\,100\equiv -3\pmod{\!103}$ so evaluating it as a Horner polynomial in radix $100$ (with the  $\rm\color{#90f}{partial}\ \color{#0a0}{eval}\color{#c00}{uations}$ written below it)
$\!\!\begin{align}
\bmod 103\!:\,\ \color{#f6f}3,\color{#0af}{53},09,\color{#0a0}{42},32 \equiv (((\color{#f6f}3({-3}) + &\color{#0af}{53})({-3}) + 9)\color{#90f}{(-3)}+\color{#0a0}{42})(-3) + 32\equiv 35\\
                                             &44)\ \ \ \ \ \ \ \ \underbrace{\color{#90f}{{-}20)}\ \ \ \ \ \ \ \ \ \ \ \  {\color{#c00}{-1}}}_{\large\!\!\!\! \color{#90f}{-20(-3)}\ +\ \color{#0a0}{42}\ \equiv\ \rlap{\color{#c00}{-1}\ }})\ \ \ \ \ \ \ \ \ \ \ \ \ 35)\\
\end{align}$
$\!\bmod 7\!:\ \ \ \ \ \ 353094232\equiv 1\,$ by this Remark ($10$ secs of mental arithmetic).
$\!\bmod 721\!:\,\ 353094232\equiv 35+103\underbrace{\left[\dfrac{1\!-\!35}{103}\bmod 7\right]}_{\Large\frac{-34}{-2}\equiv\ 17\ \equiv\  3}\equiv 344\ $ by Easy CRT
Though it is instructive, it is not any quicker than long division. But it may be for other numbers.

