Select Board & Class


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 cA such that b = ca 

Note: 1) 'a|b' read as 'a divides b' and 'ab' 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) 413, 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 b0), if there exists c such that b = ca

           For example:
           a)  4|-8,  because there exists -2 such that -8=-2 × 4
           b) -413, because there does not exist c such that 13=c ×-4

Division Algorithm

Let a,(≠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 = 4, there exists unique integers q=3 and r=1 such that 13 = (4 × 3) + 1, clearly 0r<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 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 (pa) = 1 or, (pa) = 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 ab are two integers then p|ab p|a or p|b
Proof: Let us assume that p|ab but pa and  p b
Since, p is a prime and p|ab (ab, p) = p             .....(1) (Using property 1) 
 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

To view the complete topic, please

What are you looking for?