4
$\begingroup$

What's the reason (or is there an easy explanation) of why it is possible to calculate the division mod $97$ of a large number by first calculating it for the first $9$ (or $6$?) leftmost digits and then prepend the result to the rest of the number and going on like this, like explained in: http://en.wikipedia.org/wiki/International_Bank_Account_Number#Modulo_operation_on_IBAN

I know it has to do with modular arithmetic, i tried to apply the relations like $(a \times b) \bmod c = (a \bmod c \times b \bmod c) \bmod c$, but I couldn't find a demonstration

Thank you.

$\endgroup$
3
$\begingroup$

You can do that with any number of initial digits and any modulus. (Except, of course, you will only make progress if the number of digits you handle in each step is longer than the modulus).

Suppose we want to find $x \bmod m $, where $x$ is large. Divide $x$ into a "front part" $y$ and a "back part" $z$: $$ x = y\cdot 10^{k} + z $$ (where $k$ is the number of digits left in $z$) and let $w=y\bmod m$. Then $$ (y\cdot 10^{k} + z) \bmod m = (w\cdot 10^k+z) \bmod m$$ This is because, by construction $$ y\equiv w \pmod m $$ and if we multiply by $10^k$ and add $z$ on each side (both of which preserve congruences) we get $$ y\cdot 10^k + z \equiv w \cdot 10^k + z \pmod m $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.