While revisiting this old thread, I realized there’s an even better/quicker way to get the mod 222!
TL;DR
222 = 2\times 3\times 37. To find N \bmod 37, split N into 3-digit blocks, add them, and if the result is still large, repeat.
Example:
889{,}014{,}113{,}748{,}268 \Rightarrow 889+014+113+748+268=2{,}032 \Rightarrow 2+32=34
So:
N \equiv 34 \pmod{37}
Full Explanation
We modularize (can I say it this way?) this number: 889014113748268
Split it into blocks of three digits:
889 | 014 | 113 | 748 | 268
Now add them:
\Rightarrow 889+014+113+748+268=2{,}032
We can repeat the same process once more, since 2{,}032 is still large:
2{,}032 \Rightarrow 2+032=2+32=34
(After this there is a quick mod-2 and mod-3 test. See below.)
Done.
Why this works
We start by noting that
222 = 2\times3\times37
So a number is divisible by 222 if it’s divisible by 2, 3, and 37 simultaneously.
Step 1. Focus on \text{mod }37
Because 1000 \equiv 1 \pmod{37}, we can split the number into 3-digit chunks and simply add them.
That’s a very compact, mathematical way of explaining this. Let’s unpack it.
In plain English, 37\times27=999.
Let’s write a number, say 222{,}032, as 222\times1000 + 032
If we call a=222 and b=032, then this becomes 1000a+b
The remainder modulo 37 of a number doesn’t change if we subtract any multiple of 37.
Since 999=27\times37, this is a multiple of 37.
If 999 is a multiple of 37, then so is 999a.
Subtracting 999a gives:
1000a-999a+b=a+b
Let’s make the number larger. For any 7–9-digit number, after splitting into groups of three [a, b, c], we can write it as 1{,}000{,}000a + 1{,}000b + c \Rightarrow 1{,}000(1{,}000a + b) + c
Let’s call x=1000a+b, then we get:
1000x+c
Subtract 999x (a multiple of 37):
1000x-999x+c = x+c
Substituting back x=1000a+b gives:
1000a+b+c
Subtract 999a, and we get:
a+b+c
So in short: any number written in 3-digit groups modulo 37 is equivalent to simply adding the groups together.
We can repeat the same process once more (since 2032 is still large):
2032 \Rightarrow 2+032=2+32=34
Thus:
889014113748268 \equiv 34 \pmod{37}
Step 2. Mods 2 and 3
Before we continue, let’s briefly recap.
We said that a number is divisible by 222 if and only if it’s divisible by 37, 2, and 3 at the same time.
We already handled \bmod 37; now let’s look at \bmod 2 and \bmod 3.
A number that leaves the same remainder as the original must satisfy all three conditions.
Because 222 = 2\times3\times37, the remainder must be:
- even (to satisfy divisibility by 2), and
- behave the same way as the original number with respect to 3.
Let’s check what the original number does mod 3.
When we add its digits, we get
8+8+9+0+1+4+1+1+3+7+4+8+2+6+8 = 70.
Since 70 \equiv 1 \pmod{3}, the original number leaves a remainder 1 when divided by 3.
So any smaller equivalent remainder r must also satisfy r \equiv 1 \pmod{3}.
That’s why our target remainder r must satisfy both r \equiv 0 \pmod{2} and r \equiv 1 \pmod{3}.
Mod 2: the last digit is 8 (even), so N \equiv 0 \pmod{2}.
Mod 3: as shown above, 70 \equiv 1 \pmod{3}, so N \equiv 1 \pmod{3}.
Step 3. Combine the results
We now seek a remainder r such that:
r \equiv 0 \pmod{2}
r \equiv 1 \pmod{3}
r \equiv 34 \pmod{37}
Try r=34:
34\equiv0\pmod{2} ✓
34\equiv1\pmod{3} ✓
34\equiv34\pmod{37} ✓
All conditions are satisfied.
Therefore:
889014113748268 \bmod 222 = 34
In short
Reduce the number mod 37 by adding 3-digit groups, then verify
- mod 2 = 0 (even number)
- mod 3 = 1 (digit-sum leaves 1)
The final remainder that fits all three is 34.
(I might have messed it up, be kind!)
