🧮 Modular arithmetic: Checking Huge Numbers for Divisibility

Have you ever seen a number like this in a programming problem?

7678123668327637674887634

And then the question asks:

“Is this number divisible by 101?”

When you look at it at first, it seems like it is really not going to work. The thing is, it feels impossible. This number does not fit into an integer (int) or even a very long integer (long long int).

But here is the good news:
👉 You do not need integers at all.

In this post I will explain an reliable technique to check the divisibility of huge numbers using only basic math and strings.

The core idea

A number N is divisible by m if and only if:

$$N \equiv 0 \pmod{m}$$

You read this expression as: "N is congruent to zero modulo m."
At its simplest, this means that N is exactly divisible by m.

We do not need to figure out the number. What we really want to know is what is left over when we divide the number. This is called the remainder of the number. We only care about the remainder of the number.

This small idea is really important because it is the key to everything that comes after it. The idea is tiny. The key, to everything that follows is this small idea.

How numbers are actually built

Let’s look at a normal number:

527

It’s really built like this:

((5 × 10 + 2) × 10 + 7)

So numbers are constructed digit by digit.
That means we can process even huge numbers the same way — one digit at a time — and just keep track of the remainder.

Let’s check if:

527 is divisible by 7

Step by step:

Digit	Calculation	Remainder
start	$0$	0
5	$(0×10 + 5)\mod 7$	5
2	$(5×10 + 2)\mod 7$	3
7	$(3×10 + 7)\mod 7$	2

Final remainder is 2.
And $2 \neq 0$ .
So, we can say 527 is not divisible by 7.

The golden formula

If we see the calculation pattern from the table.
It start with 0

remainder = 0

For every digit d in the number:

remainder = (remainder × 10 + d) % m

m is the divisor or modulus, which is 7 in our example

It is really interesting to see that the remainder is always small. The remainder never gets big it always stays small. This is something that always happens with the remainder.

Why this works

Let's connect the dots with our 527 ÷ 7 example.

Remember when we calculated (5×10 + 2) mod 7?
Here's the magic: we don't actually need to compute 52 first. We can work with the remainder of 5 instead.

The key insight from modular arithmetic is this:

$$(a \times b + c) \bmod m = ((a \bmod m) \times b + c) \bmod m$$

Let me show you what this means with our actual numbers:

Traditional way (what we'd do if the number fit in memory):

$$\begin{aligned} &(5 \times 10 + 2) \bmod 7\\ &= 52 \bmod 7\\ &= 3 \end{aligned}$$

Our smart way (using the remainder from the previous step):

$$\begin{aligned} &((5 \bmod 7) \times 10 + 2) \bmod 7\\ &= (5 \times 10 + 2) \bmod 7\\ &= 52 \bmod 7\\ &= 3 \end{aligned}$$

See? Same answer!

This is why our algorithm works beautifully. At each step, instead of building a massive number, we just carry forward a tiny remainder (always less than m). When we process the next digit, we multiply this small remainder by 10, add the new digit, and take the modulus again.

So even if you're checking whether a billion-digit number is divisible by 101, you're never working with numbers bigger than 101. That's the elegant power of modular arithmetic.

A clean and correct PHP solution

<?php

/**
 * Check divisibility of a huge number given as a string.
 *
 * @param string $number The number as a string (can be very large)
 * @param int $mod The divisor
 * @return bool True if divisible, false otherwise
 */
function isDivisible(string $number, int $mod): bool {
    $rem = 0;
    $len = strlen($number);

    for ($i = 0; $i < $len; $i++) {
        $rem = (($rem * 10) + (int)$number[$i]) % $mod;
    }

    return $rem === 0;
}

Performance

• Time complexity: O(number of digits)
• Space complexity: O(1)
• Works even for numbers with millions of digits

Final thoughts

You don’t need fancy libraries or big integers to solve big problems.

Sometimes, a small mathematical insight is all it takes.

If you found this helpful, feel free to share or leave a comment.
And happy coding! 🚀🚀