In Maths:
15 mod 7 = 1
12 mod 5 = 2
16 mod 4 = 0
2 mod 6 = 2
-1 mod 5 = -1 => 4 //do 1 mod 5 and add negative sign
-15 mod 7 = -1 => 6
-12 mod 5 = -2 => 3
12 mod -5 = 2 => -3
16 mod -4 = 0
In Programming:
y % x is 0.[1, x-1].compile-time error.Restrictions in C/C++:
compile-time error.x % y always returns results with the sign of x.1. (a + b) % c = ( ( a % c ) + ( b % c ) ) % c
2. (a * b) % c = ( ( a % c ) * ( b % c ) ) % c
3. (a – b) % c = ( ( a % c ) – ( b % c ) ) % c
4. (a / b ) % c = ( ( a % c ) / ( b % c ) ) % c (Not Distributive)
Negative Remainders with Subtraction: We have to be careful with identity 3 as it can give negative value as result of modulo. Two fixes are -
int ans = (a - b) % mod;
if(ans < 0) ans += mod;
int ans = ((a - b) % mod + mod) % mod; //slower than previous way as it increases mod operations
Identity: (a / b) % m = ( ( a % m ) * ( 1/b ) % m ) % m. Finding modulo for division is not always possible.
1e9+7.Gotcha!!
long long ans;
ans = (a * b) % n; //a and b are huge numbers
The above solution may lead to overflow as we multipled them and even when we're not storing them in variable ans before the modulo, they are still huge for intermediate value to be stored temporarily for performing modulo operation by the machine. Fix -
long long ans;
ans = ( (a % n) * (b % n) ) % n;
if (a mod n) = (b mod n), then
a ≡ b (mod n)
Some Observations regaarding a ≡ b (mod n):
1. a = k * n + b //b need not be the remainder of a/n
2. (a - b) is a multiple of n
Congruence modulo is an equivalence relation for (mod C): It is reflexive, symmetric, and transitive.
Reflexive: A ≡ A (mod N)
Symmetric: if A ≡ B (mod N) then B ≡ A (mod N)
Transitive: if A ≡ B (mod N) and B ≡ C (mod N) then A ≡ C (mod N)