Modular Arithmetic

Recall: Divisibility, Division Algorithm, GCD, Prime nos, co-prime nos

​Divisibility on set A a|b (where a, b ∈A, b ≠ 0 ), if there exist c∈A such that b = ca  Note: 1) 'a|b' read as 'a divides b' and 'a∤b' read as 'a does not divide b'.           2)  '∈' stands for 'belongs to' and '∉' stands for 'not belongs to'.   If A = ℕ ( The set of all the natural numbers)              Divisibility on ℕ:  a|b (where a, b ∈ℕ), if there exists c∈ℕ such that b = ca                        For example:            a)  4|8,  because there exists 2∈ℕ such that 8 = 2 × 4            b) 4∤13, because there does not exist  c ∈ℕ such that 13 = c × 4   If A = ℤ( The set of all the integers)            Divisibility on ℤ: a|b (where a, b ∈ℤ and b≠0), if there exists c∈ℤ such that b = ca            For example:            a)  4|-8,  because there exists -2∈ℤ such that -8=-2 × 4            b) -4∤13, because there does not exist c∈ℤ such that 13=c ×-4 Division Algorithm Let a,b (≠0) be any two integers, then there exist unique integers q and r such that a = bq + r, where 0 ≤ r < b For example:  For a = 13 and b = 4, there exists unique integers q=3 and r=1 such that 13 = (4 × 3) + 1, clearly 0≤r<4 Greatest Common Divisor (GCD) Or Highest Common Factor (HCF) A positive integer 'd' is the GCD of a and b means 'd' is the greatest among all the common divisors of a and b i.e. if c is any other common divisor of a and b then c < d , in fact c|d. In other words:  A positive integer 'd' is the GCD of a and b, if  (i) d|a and d|b (ii)c|a and c|b ⇒ c|d  Note: GCD of integers a and b is denoted by (a, b).   For example:  4 is the GCD of 12 and 8 because it satisfies both (i) and (ii). (i) 4|12 and 4|8 (which is true) (ii) 0, 2, 4 are the common divisors of 12 and 8As 0|12 and 0|8 ⇒ 0|4 (which is true)As 2|12 and 2|8 ⇒ 2|4 (which is true)As 4|12 and 4|8 ⇒ 4|4 (which is true) So, (8, 12) = 4 Also, (8, -12)=4, (-8, 12)=4, (-8, -12)=4  Prime Number A positive integer p (≠1) is called a prime number if its only divisors are 1 and p. For example: 5 is a prime number because its only divisors are 1 and 5. Whereas, 4 is not a prime number because 2 is also its divisor which is other than 1 and 4. Note: The smallest divisor (> 1) of an integer (> 1) is a prime number. Coprime Numbers If a, b ∈ℤ+ then a and b are coprimes if and only if (a, b) = 1 i.e., two positive integers are co-prime if and only if their GCD is 1.  (Note: We can write 'if and only if' in a short way as 'iff') Some important properties of prime numbers: Property 1):   If p is a prime number and a is any integer then (p, a) = 1 or, (p, a) = p. Property 2):  Let a, b∈ℤ+, if there exist s, t∈ℤ such that as+bt=1,then (a, b) = 1 i.e. a, b are coprimes. (Note: We can use the mathematical symbol '∃' for writing 'there exists') Property 3):  If p is a prime number and a, b are two integers then p|ab ⇒p|a or p|b Proof: Let us assume that p|ab but p⫮a and  p⫮ b Since, p is a prime and p|ab ⇒(ab, p) = p             .....(1) (Using property 1)  And,  p⫮ a ⇒(a, p) = 1 similiarly p⫮ b ⇒ (b, p) = 1⇒∃ s, t, u, v ∈ ℤ such that as + pt = 1 and bu + pv = 1    (Using property 2)⇒∃ s, t, u, v ∈ ℤ such that (as + pt) (bu + pv) = 1⇒∃ s, t, u, v ∈ ℤ such that (abus + apvs + pbtu + p2tv)=1⇒∃ (us), (avs + btu + ptv) ∈ ℤ such that ab(us) + p(avs + btu + ptv)=1⇒(ab, p) = 1 Which contradicts (1), thus, our assumption is wrong.  Hence, p|ab ⇒p|a or p|b Note: 'Property 3' may fail when p is not a prime For example: 6|12 but 6∤3 and 6∤4 ​Divisibility on set A a|b (where a, b ∈A, b ≠ 0 ), if there exist c∈A such that b = ca  Note: 1) 'a|b' read as 'a divides b' and 'a∤b' read as 'a does not divide b'.           2)  '∈' stands for 'belongs to' and '∉' stands for 'not belongs to'.   If A = ℕ ( The set of all the natural numbers)              Divisibility on ℕ:  a|b (where a, b ∈ℕ), if there exists c∈ℕ such that b = ca                        For example:            a)  4|8,  because there exists 2∈ℕ such that 8 = 2 × 4            b) 4∤13, because there does not exist  c ∈ℕ such that 13 = c × 4   If A = ℤ( The set of all the integers)            Divisibility on ℤ: a|b (where a, b ∈ℤ and b≠0), if there exists c∈ℤ such that b = ca            For example:            a)  4|-8,  because there exists -2∈ℤ such that -8=-2 × 4            b) -4∤13, because there does not exist c∈ℤ such that 13=c ×-4 Division Algorithm Let a,b (≠0) be any two integers, then there exist unique integers q and r such that a = bq + r, where 0 ≤ r < b For example:  For a = 13 and b = 4, there exists unique integers q=3 and r=1 such that 13 = (4 × 3) + 1, clearly 0≤r<4 Greatest Common Divisor (GCD) Or Highest Common Factor (HCF) A positive integer 'd' is the GCD of a and b means 'd' is the greatest among all the common divisors of a and b i.e. if c is any other common divisor of a and b then c < d , in fact c|d. In other words:  A positive integer 'd' is the GCD of a and b, if  (i) d|a and d|b (ii)c|a and c|b ⇒ c|d  Note: GCD of integers a and b is denoted by (a, b).   For example:  4 is the GCD of 12 and 8 because it satisfies both (i) and (ii). (i) 4|12 and 4|8 (which is true) (ii) 0, 2, 4 are the common divisors of 12 and 8As 0|12 and 0|8 ⇒ 0|4 (which is true)As 2|12 and 2|8 ⇒ 2|4 (which is true)As 4|12 and 4|8
…