Select Board & Class

Modular Arithmetic

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

Divisibility on set A

Note: 1) '$a|b$' read as 'a divides b' and 'a$\nmid$b' read as 'a does not divide b'.
2)  '∈' stands for 'belongs to' and '∉' stands for 'not belongs to'.

• If A = $\mathbf{ℕ}$ ( The set of all the natural numbers)
Divisibility on $\mathbf{ℕ}$:

For example:

a)   because there exists
b) $4\nmid 13,$ because
there does not exist

• If A = $\mathrm{ℤ}$( The set of all the integers)
Divisibility on $\mathrm{ℤ}$

For example:
a)   because
b) $-4\nmid 13,$ because

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 < $\left|b\right|$

For example:
For a = 13 and = 4, there exists, clearly $0\le 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 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)
(ii)

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)  (which is true)
(ii)

So, (8, 12) = 4
Also,

Prime Number

A positive integer is called a prime number if its only divisors are .

For example: $5$ is a prime number because its only divisors are .
Whereas, $4$ is not a prime number because $2$ is also its divisor which is other than .

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

Coprime Numbers

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:

Property 1):

If p is a prime number and a is any integer then (pa) = 1 or, (pa) = p.

Property 2):
Let .

(Note: We can use the mathematical symbol '$\exists$' for writing 'there exists')
Property 3):
If p is a prime number and ab are two integers then
Proof: Let us assume that
Since,
And,

Which contradicts (1), thus, our assumption is wrong.
Hence,

Note: 'Property 3' may fail when p

To view the complete topic, please

What are you looking for?

Syllabus