Modulo arithmetic fundamental properties
One can easily prove that
(a + b) % k = ( (a % k) + (b % k) ) % k,
where % is the remainder operator.
To prove that assume a = pk +q, b = mk + n. And try to equate LHS and RHS.
Similarly,
(a - b) % k = ( (a % k) - (b % k) ) % k
And
(ab) % k = ( (a % k) * (b % k) ) % k
Ex 1:
6 mod 7 = -1 mod 7
This is a useful trick for exams.
If remainder is 1 less than divisor it can be rewritten as -1.
Since -1 + 7 mod 7 = 6
Similarly
13 mod 7 = -1
17 mod 9 = -1
Ex 2:
For a non-zero 'a', a mod (a + 1) is -1.
Same argument as above.
Ex 3:
Extending Ex 2, a^2 mod (a+1) = 1
Since
a^2 mod (a+1) = -1 * -1 = 1
Comments
Post a Comment