How to check divisibility by 97 I'm looking for rule to check divisibility by 97 for big numbers. For example, for numbers with 26 digits. Thanks.
 A: I just looked into this and I formed my own way of doing this. For example, let's take a number that we know is a multiple of 97, like $547627565$, i.e $97*5645645$.
This number contains 9 digits. Let the no. of digits of the given number be $n$. Take the first (n-2) digits. So here in this case it would be 5476275. Now do the following;
$$547627565-5476275(97)=16428890\tag{Step 1.}\label{1}$$
So i.e; $(the\; number) - 97(the\; number\; with\; the\; first \;(n-2)\; digits)$
Now do the same step and take the first $(n-2)$ digits of this. And repeat the process
$$16428890-164288\left(97\right)=1202509\tag{Step 2.}\label{2}$$
$$1202509-12025\left(97\right)=36084\tag{Step 3.}\label{3}$$
$$36084-360\left(97\right)=1164\tag{Step 4.}\label{4}$$
$$1164-11\left(97\right)=97\tag{Step 5.}\label{5}$$
So if any number after this transformation/process ends up at $97$, Then it is a multiple of $97$. Also note that even for a 9-digit number, this takes only 5-steps.
A: A general way to compute $n\%m$ starts by writing $n$ in some base. Say you pick base $10$, so you write $n=\sum_i a_i 10^i$ where $a_i \in \{ 0,1,\dots,9 \}$. Now compute $10^i \% m$ for a sufficiently large segment of $i$'s that you find the cycle. When $m$ and the base are coprime (as here), Euler's theorem tells you that the cycle will have at most $\varphi(m)$ elements (not counting the duplicate at the end), where $\varphi$ is the totient function. In particular $\varphi(p)=p-1$ for a prime $p$.
So here you can precompute $\{ 10^i \% 97 : i=1,\dots,95 \}$. Say these numbers are $r_1,\dots,r_{95}$ and also introduce $r_0=1$. Then $n\%97=\left ( \sum_i a_i r_{i\%96} \right )\%97$. You can then do this computation by using this algorithm recursively (stopping when you get a sum that is less than 97), or you could take moduli as you carry out the summation, or you could follow various similar options.
A: Let $\overline{a_1a_2\cdots a_n}$ denote a $n$ digit number equal to $a_n+10a_{n-1}+100a_{n-2}\cdots$. Then, we can write the following: $\overline{a_1a_2\cdots a_{n-1}a_n}=10\overline{a_1a_2\cdots a_{n-1}}+a_n=10(\overline{a_1a_2\cdots a_n-1}-29a_n)+291a_n$. And since $97|291$, then $97|291a_n$ and $97|10(\overline{a_1a_2\cdots a_{n-1}}-29a_n)$ implies $97|\overline{a_1a_2\cdots a_n}$. We can also ignore the $10$ factor. We can keep doing this recursively.
So our algorithm is:


*

*Take the last digit of a number. Let’s call it $e$.

*Subtract $e$ from the number and divide by $10$.

*Subtract $29\cdot e$ from the number.

*Repeat Steps 1-3 as many times as you want.

