Mod

Mod refers to the remainder after a division is performed.

For example, 11 mod 3 = 2, because 11 ÷ 3 = 3 with a remainder of 2.

Example #1 (easy): 56221 mod 10

A question of the form x mod 10 is as simple as it gets.

Write:

56221 = (5622 × 10) + 1

Any integer multiplied by 10 is divisible by 10, so:

• 56220 mod 10 = 0

• 1 mod 10 = 1

Therefore:

56221 mod 10 = 1

Example #2 (advanced): 7216371773 mod 19646275

Here we have a 10-digit number mod an 8-digit number.

When the modulus is large (and especially when it’s larger than √x), a practical approach is:

1. Find the integer quotient q = ⌊x / y⌋ (even approximately, but here we’ll treat it as exact).

2. Compute x − qy to get the remainder.

In this case, using standard division (or cross-division), we get:

• q = 367

So the remainder is:

7216371773 − 367 × 19646275

A practical way to do this mentally is to multiply 19646275 × 367 as:

• 19646275 × 300

• 19646275 × 60

• 19646275 × 7

…and subtract from 7216371773.

A digit-by-digit “remainder tracking” variant (left-to-right)

Another approach is to reduce the problem to:

7216371773 mod 367

after finding the quotient (the “367” here), and then to compute the remainder by repeatedly bringing down digits (division-style), subtracting multiples of 367 as you go.

A sample reduction sequence (illustrative) looks like this:

• 721 − 367 = 354 → bring down next digit → 3546

• subtract 9×367 = 3303 → 3546 − 3303 = 243 → bring down next digit → 2433

• 2433 − 6×367 = 231 → bring down next digit → 2317

• 2317 − 4×367 = 849 → bring down next digit → 8491

• 8491 − 6×367 = 6289 → bring down next digit → 62897

• 62897 − 2×367 = 62163 → bring down next digit → 621637

• 621637 − 7×367 = 619068 → bring down next digit → 6190683

• 6190683 − 5×367 = 6188848

• then finish with the remaining remainder mod 367

This method can be made fast, but it takes practice—especially the “bring down / subtract a multiple / keep the running remainder” rhythm.

Example #3 (expert): 1731879273540 mod 59501

Now we have a 13-digit number mod a 5-digit modulus. Straight digit-by-digit division is possible, but it’s heavy. Here are two high-level approaches.

Option 1: Factorization + Chinese Remainder Theorem (CRT)

If the modulus factors cleanly, CRT can be used.

Here:

59501 = 13 × 23 × 199

Compute the remainder of x modulo each prime factor:

• x mod 13 = 0

• x mod 23 = 13

• x mod 199 = 62

So we want w such that:

• w ≡ 0 (mod 13)

• w ≡ 13 (mod 23)

• w ≡ 62 (mod 199)

From w ≡ 0 (mod 13), write:

• w = 13v

Then:

• 13v ≡ 13 (mod 23)
  Divide both sides by 13 (equivalently, multiply by the inverse of 13 mod 23). This gives:

• v ≡ 1 (mod 23)

So:

• v = 23u + 1

• w = 13(23u + 1) = 299u + 13

Now impose the final condition:

• 299u + 13 ≡ 62 (mod 199)
  Subtract 13:

• 299u ≡ 49 (mod 199)

Since 299 ≡ 100 (mod 199), this becomes:

• 100u ≡ 49 (mod 199)

Now we need the inverse of 100 mod 199. A quick observation:

• 100 × 2 = 200 ≡ 1 (mod 199)

So the inverse of 100 mod 199 is 2, hence:

• u ≡ 49 × 2 = 98 (mod 199)

Use u = 98 in w = 299u + 13:

• w = 299 × 98 + 13

• w = 29302 + 13

• w = 29315

Therefore:

1731879273540 mod 59501 = 29315

(Using CRT efficiently requires comfort with modular inverses. The arithmetic is not bad; the structure is what takes practice.)

Option 2: Chunking (block reduction)

Instead of treating the number as 13 digits, break it into blocks and repeatedly reduce mod 59501.

Write x as:

1 731 879 273 540

Start from the left, take enough digits to exceed 59501, reduce mod 59501, then “bring down” the next block.

For example:

1. Reduce:

• 1731879 mod 59501
  If you can quickly see the quotient is about 29, then:

• 1731879 − 29×59501 = 6350

So now carry forward:

• remainder = 6350

1. Bring down the next block (here “273” as a 3-digit chunk), meaning:

• 6350 → 6350273
  Then compute:

• 6350273 mod 59501 = 43167

1. Bring down the final block “540”:

• 43167 → 43167540
  Then:

• 43167540 mod 59501 = 29315

This approach is only “fast” if you can also quickly approximate quotients and do mid-sized multiplications without getting lost. The upside is fewer steps; the downside is higher effort per step.