Modulus of a Big number
How to Evaluate Modulus of very large numbers ? We know the modular addition property which is: IF N = a + b, then N % n = ( a + b ) % n . Which can be written as : N % n = ( ( a % n ) + ( b % n) ) % n Lets say we want to calculate 123456 % 7 . Let's consider : For a number 123 % 7 it can be evaluated as ( 120 + 3 ) %7 Now 12 = 12 + 12 + 12 + ............ + 12 ; adding 12, 10 times will give us 120. So Applying the modular addition formula we get : ( ( 12 +12+12+.........+12) + 3 ) ) % 7 ( ( 12 % 7 ) + ( 12 % 7 ) + ........ + ( 12 % 7 ) + ( 3 % 7 ) ) % 7 ( ( 12 % 7) * 10 + ( 3 % 10 ) ) % 7 Now the modulus of the number 123456 can be represented like this: 1 % 7 -> ( 0 *10 + 1 ) % 7 12 % 7 -> ( 10+2 ) % 7= ( 1 % 7 )*10 + ( 2 % 7) ) % 7 123 -> ( 120+3 ) % 7 = ( (12 % 7 ) * 10 + ( 3 % 7 ) ) % 7 1234 -> ( 1230+4 ) % 7 = ( (123 % 7 ) * 10 + ( 4 % 7 ) ) % 7 12345 -> ( 12340 + 5 ) % 7 = ( (1234 ...