1

Someone just shared some code with me that attempts to calculate modulus of big numbers in a more simple way, but I don't quite understand how it works.

If you want to know $a$ modulus $b$, where $a$ is some big number, you can split a into digits: $a = a_1 a_2...a_n$ (so to be clear, this is not multiplication, it means 123 = 1 and 2 and 3). Then, you can (seemingly arbitrarily) pick groups of digits to calculate it modulus $b$. For every group, you prepend the outcome to the next group: $a_1a_2a_3 \mod b = x$, then $xa_4a_5 \mod b = y$, then $ya_6...a_n \mod b = z$ where z = a mod b. Here is an example:

77766655544 mod 98
> 7776665 mod 98 = 71
> 715544 mod 98 = 46 = 77766655544 mod 98

How does this work?

Luctia
  • 113

1 Answers1

0

This is a very simple result derived from basic properties of modular arithmetic. First, you can split the number: $$77766655544 \bmod 98 = (77766650000 \bmod 98)+(5544 \bmod 98)$$ Now, based on the fact that $$7776665 \bmod 98 = 71 \\ \implies 7776665 \equiv 71 \pmod{98} $$ you can derive (by multiplying by $10000$) $$ \implies 77766650000 \equiv 710000 \pmod{98}$$ and replace in the original equation $$ (77766650000 \bmod 98)+(5544 \bmod 98) \\ = (710000 \bmod 98)+(5544 \bmod 98) \\ = 715544 \bmod 98 $$ In essence, these properties allow one to process huge numbers with large counts of digits by iteratively processing smaller "chunks" of it.

user3733558
  • 1,218