Blaise Pascal invent a rule how to check if number divides on another number.
I don't know exactly how it sounds but from school I remember that if sum of digits in given number divides on three, then this number is divides on three.
Also there exist a rules of division on 7, 11 etc.
Can this help us somehow?
I mean make sum of 10000000 and divide it on 3 takes few seconds, not few days, right?