Select Board & Class


Modular Arithmetic

Divisibility on set A

a|b (where a, b A, b  0 ), if  cA such that b = ca 

(Note: 'a|b' read as 'a divides b')

  • If A =  ( The set of all the natural numbers)  
           Divisibility on :  a|b (where a, b ), if  c such that b = ca
  • If A = ( The set of all the integers)
           Divisibility on a|b (where a, b  and b0), if  c such that b = ca

Division Algorithm

 Let a, b( 0) be any two integers, then  unique integers q and r such that a=bq+r,where 0r<b

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).

Prime Number

A positive integer p (1) is called a prime number if its only divisors are 1 and p.

Note: The smallest divisor (> 1) of an integer (> 1) is a prime number.

Coprime Numbers

If a, b + then a and b are coprimes iff (a, b) = 1 i.e., two positive integers are co-prime iff their GCD is 1. 

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.

Property 3): 
If p is a prime number and ab are two integers then p|ab p|a or p|b
Modular Arithmetic is a system of arithmetic for integers, …

To view the complete topic, please

What are you looking for?