Recall: Divisibility, Division Algorithm, GCD, Prime nos, co-prime nos
Divisibility on set A
Note: 1) '' 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)
a) because there exists
b) because there does not exist
- If A = ( The set of all the integers)
Let a,b (≠0) be any two integers, then there exist unique integers q and r such that a = bq + r, where 0 ≤ r <
For a = 13 and b = 4, there exists, clearly
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
Note: GCD of integers a and b is denoted by (a, b).
4 is the GCD of 12 and 8 because it satisfies both (i) and (ii).
(i) (which is true)
So, (8, 12) = 4
A positive integer is called a prime number if its only divisors are .
For example: is a prime number because its only divisors are .
Whereas, is not a prime number because is also its divisor which is other than .
Note: The smallest divisor (> 1) of an integer (> 1) is a prime number.
If 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:
If p is a prime number and a is any integer then (p, a) = 1 or, (p, a) = p.
(Note: We can use the mathematical symbol '' for writing 'there exists')
If p is a prime number and a, b are two integers then
Proof: Let us assume that
Which contradicts (1), thus, our assumption is wrong.
Note: 'Property 3' may fail when p …
To view the complete topic, please