How to compute the remainder of a very large number (string with 1 mi digits) in the division by 1500

Question

I'm wondering if there is a trick with number theory to compute this remainder without need to implement a BigInt division algorithm.

Answer 1

Its simple, just check these three things:

Divisibility by 1500

1. it has to be divisible by 100 (last two digits must be 00)
2. it has to be divisible by 5 (third digit from right has to be 0 or 5)
3. it has to be divisible by 3 (iterate over all digits, sum them, and the result has to be divisible by 3)

And if you want to know the remainder, its again simple:

Check for divisible by 5 and get remainder

1. get remainder from last 4 digits after division by 500, it will be from 0 to 499.

Check for divisible by 3 and get remainder

2. iterate over all digits, sum them, and get remainder from that after division by 3, it will be from 0 to 2.

3. and depending from this remainder increase the remainder from 1st step by this remainder multiplied by 500.

Example 1

1234567890 % 1500 = 390

1. 7890 % 500 = 390
2. 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0 = 45 and 45 % 3 = 0, so nothing has to be added to 390 and the result is then 390.

Example 2

12345678901 % 1500 = 901

1. 8901 % 500 = 401
2. 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0 + 1 = 46 and 46 % 3 = 1, so we have to add 1 * 500 to the result from 1st step, so 401 + 1 * 500 = 901.

Example 3

1357913579 % 1500 = 1079

1. 3579 % 500 = 79
2. 1 + 3 + 5 + 7 + 9 + 1 + 3 + 5 + 7 + 9 = 50 and 50 % 3 = 2, so we have to add 2 * 500 to the result from 1st step, so 79 + 2 * 500 = 1079.

Hope this helps you.

Answer 2

Haha, it's easy!

I can iterate over all digits, adding each parcel... Using the properties:

1) (a+b) mod c = (a mod c + b mod c) mod c

2) (a*b) mod c = (a mod c * b mod c) mod c

The power of ten can be increased mod 1500 each step.