Modular Arithmetic
Divisibility on set A
(Note: '' read as 'a divides b')
- If A = ( The set of all the natural numbers)
- If A = ( The set of all the integers)
Division Algorithm
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 .
In other words:
A positive integer 'd' is the GCD of a and b, if
(i)
(ii)
Note: GCD of integers a and b is denoted by (a, b).
Prime Number
A positive integer is called a prime number if its only divisors are .
Note: The smallest divisor (> 1) of an integer (> 1) is a prime number.
Coprime Numbers
If 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 (p, a) = 1 or, (p, a) = p.
Property 2):
Let .
Property 3):
If p is a prime number and a, b are two integers then
To view the complete topic, please