115. Division by 37. I would like to know if the number 49129308213 is divisible by 37, and if not, what the remainder is. How can I do this without performing the division? It turns out that with a skilled approach, the answer to my question can be obtained in a few seconds.
115. Let's write the numbers \(1,10,11\) from right to left under our number, as shown below:

\[
\begin{array}{rrrrrrrrrrr}
4 & 9 & 1 & 2 & 9 & 3 & 0 & 8 & 2 & 1 & 3 \\
10 & 1 & 11 & 10 & 1 & 11 & 10 & 1 & 11 & 10 & 1
\end{array}
\]

Now, let's multiply the numbers 1 and 10 at the bottom by the numbers above them and sum the products; then do the same with the numbers 11 and subtract the second sum from the first. The result is: \(13 + 08 + 29 + 49 = 99\); \(11 \times (2 + 3 + 1) = 66\). The difference is 33, which coincides with the remainder of our number when divided by 37.

This is the key to solving the problem. If we divide \(1,10,100,1000\) and so on by 37, we will sequentially get the remainders: \(1,10,26\) and again \(1,10,26\) and so on. It is more convenient to subtract 37 from 26 and say that the remainder is minus 11. If you apply this method to the number 49629708213, you will find that the first sum is 99, and the second sum is 165. The difference is minus 66. Add 37 and you get minus 29. Since the answer is negative, add 37 again, and you get the correct answer, which is 8. Now you can apply a similar method to other prime divisors. In the case of 7 and 13, this is easy. In the first case, you write \(1,3,2\) \((1,3,2), 1,3,2\) and so on from right to left, with the numbers in parentheses taken with a negative sign. In the second case, you need to write \(1(3,4,1), 3,4\), \(1(3,4,1)\) and so on.
\footnotetext{
" Alternatively, we can say: the probability that a randomly chosen number is divisible by 11 is \(\frac{11}{126}\).
}