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
Ex 4:
Prove that for any positive integer n:
1) n.(n+1).(2n+1) is divisible by 6.
Either n or (n+1) is even. So it's divisible by 2.
Now 3 cases for proving divisibility by 3:
a) n mod 3 = 0, then it's div by 3.
b) n mod 3 = 1 then (2n + 1) mod 3 = 2 + 1 = 0 mod 3, hence div by 3.
c) n mod 3 = 2 then (n + 1) mod 3 = 0, H.P.
2) (2n - 1). n. (2n + 1) is divisible by 3.
Similar to above. Take 3 cases as above and prove.
Ex 5:
Prove that if (x - 1) is divisible by d then x^k - 1is also divisible by d for every integer k >= 1.
Solution:
x - 1 mod d = 0
=> x = 1 mod d
=> x^k = 1^k mod d
=> x^k = 1 mod d
=> x^k - 1 mod d = 0
H.P.
So it means that (x-1) is always a factor of (x^k - 1) for every integer k >= 1.
r -s = 0 mod 6 is same as saying r-s = 6k
Cyclicity:
What is the period of powers of 2 modulo 9?
2^1 mod 9 = 2
2^2 mod 9 = 4
2^3 mod 9 = 8
2^4 mod 9 = 7
2^5 mod 9 = 5
2^6 mod 9 = 1
As soon as it becomes 1, it will start repeating.
So answer is 6.
------------------------------
Division in modulus
Q1. Solve 4x = 2 mod 6
S1.
-2x = 2 mod 6 (Replace 4 with -2)
-x = 1 mod 6 (Divide by 2)
x = -1 mod 6
x = 5 mod 6
What's wrong here?
We missed one more solution which is x = 2 mod 6.
The mistake is when we divide by 2.
In modulo arithmetic, if divisor and modulus share a common factor you can't simply divide by that divisor.
You have to divide the modulus as well by the gcd(divisor,modulus).
So the correct method here is:
-2x = 2 mod 6
=> -x = 1 mod (6/2) Since gcd(2,6) = 2.
=> x = -1 mod 3
=> x = 2 mod 3
=> x = 2 mod 6 and x = 5 mod 6 are the 2 answers.
Q2.
4x = 4 mod 6
S2.
This time we will be careful and divide by gcd as well.
x = 1 mod (6/2)
x = 1 mod 3
=> x = 1 mod 6 and x = 4 mod 6
Q3.
10 = 10x mod 5 (true for all x)
1 = x mod 1
Now is it true for all x?
You might wonder that x mod 1 = 0 for all x.
But the correct definition here is that x - 1 = 0 mod 1 for all x and that holds.
In general, if a = b mod x then (a-b) = 0 mod x.
------------------------------------------------------
Combining and Splitting Moduli (The Coprime Rule)
Splitting a modulo:
x = 1 mod k1.k2.k3
=>
x = 1 mod k1
x = 1 mod k2
x = 1 mod k3.
Irrespective of whether k1,k2,k3 are pairwise co-prime or not.
Proof:
x - 1 = N.(k1.k2.k3)
Now dividing x-1 with k1,k2,k3 also leaves remainder one.
H.P.
Combining moduli:
x = 1 mod a
x = 1 mod b
x = 1 mod c
=> x = 1 mod (a * b * c)
Only if a,b,c are pairwise co-prime.
Proof:
a | x - 1
b | x - 1
c | x - 1
=>
lcm(a,b,c) | x - 1
If a,b,c are pairwise co-prime then:
lcm(a,b,c) = a.b.c
H.P.
Ex1:
If x = 1 mod 3 and x = 1 mod 5 then x = 1 mod 15
Ex2:
Let x = 13
So:
x = 1 mod 4
x = 1 mod 6
then:
x = 1 mod 24?
No.
=> x = 1 mod 12
Comments
Post a Comment