Devise an algorithm to determine whether a given positive hexadecimal integer N is divisible by (B)

_{16}, and if NOT, to find the remainder.

N can contain up to (20220)_{10} digits.

__Note__:

o Simply dividing N by (B)_{16} is NOT permissible.

o (B)_{16} is equal to 11 in base ten.

From Fermat's little theorem we know that 2^10 mod 11 = 1. Then 2^20 mod 11 = 1 as well. 2^20 = 16^5, and 16 is the hexadecimal base. Then an algorithm is apparent:

Break the big hexadecimal number into chunks of 5 hexdigits, starting from the right.

Add those numbers together.

If the resulting sum is still longer than 5 hexdigits, repeat this process on the sum.

Eventually the sum will be at most 5 hexdigits. Now divide this by B (base 16). The remainder will be the remainder of the original big number.

(All calculations done in hexadecimal here on)

Example: 123456789ABCDEF mod B:

= 12345+6789A+BCDEF mod B

= 1369CE mod B

= 1+369CE mod B

= 369CF mod B

= A

Now if dividing a 5 digit hexadecimal number is still too big, that can be reduced with an identity VWXYZ = 9*V+4*W+3*X+5*Y+Z mod B

Then continuing from the example: 369CF mod B

= 9*3+4*6+3*9+5*C+F mod B

= 1B+18+1B+3C+F mod B

= 99 mod B

= A