Can someone post basic rules for operations with MOD?
Mod arithmetics
http://en.wikipedia.org/wiki/Modulo_operation ;)
For example: is (a+b) mod m= a mod m +b mod m or something else? Same question with other operations
Yes it is, rules are similar to normal division.
No, it's not.
( A + B ) % m = ( ( A % m ) + ( B % m ) ) % m
For example:
( 2 + 2 ) % 3.
With your formula, you'd get ( 2 % 3 ) + ( 2 % 3 ) = 4, but the solution is 1 :)
( A + B ) % m = ( ( A % m ) + ( B % m ) ) % m
For example:
( 2 + 2 ) % 3.
With your formula, you'd get ( 2 % 3 ) + ( 2 % 3 ) = 4, but the solution is 1 :)
( A + B ) % m = ( ( A % m ) + ( B % m ) ) % m
( A - B ) % m = ( ( A% m ) - ( B % m ) + m ) % m
( A * B ) % m = ( ( A % m ) * ( B % m ) ) % m
( A / B ) % m = ( ( A % m ) * ( B^( m - 2 ) % m ) ) % m , if m is prime
( A - B ) % m = ( ( A% m ) - ( B % m ) + m ) % m
( A * B ) % m = ( ( A % m ) * ( B % m ) ) % m
( A / B ) % m = ( ( A % m ) * ( B^( m - 2 ) % m ) ) % m , if m is prime
Oops, my mistake. I did know that but totally forgot it :)
One more: (a^b) mod m=?
(a^b)mod m = ((a mod m)*(a mod m)*...*(a mod m) mod m)
((a mod m) is repeated b times)
But, for each pair of (a mod m)*(a mod m), you can aply "mod m" to the result in order to avoid overflow issues.
I think (if I am wrong, correct me, please, someone) you cannot say nothing more than that for (a^b) mod m.
((a mod m) is repeated b times)
But, for each pair of (a mod m)*(a mod m), you can aply "mod m" to the result in order to avoid overflow issues.
I think (if I am wrong, correct me, please, someone) you cannot say nothing more than that for (a^b) mod m.