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
Solution
