All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Divisible by B (Posted on 2023-02-10)
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.

 See The Solution Submitted by K Sengupta Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 1 of 2
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.
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

 Posted by Brian Smith on 2023-02-10 12:57:34

 Search: Search body:
Forums (0)