Modular Arithmetic, Studymaterial: CBSE Class 12-science APPLIED MATHEMATICS, Applied Mathematics

Modular Arithmetic

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

Divisibility on set A

$a | b (where a, b \in A, b \neq 0), if there exist c \in A such that b = c a$

Note: 1) ' $a | b$ ' read as 'a divides b' and 'a $∤$ b' 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 \in ℕ), if there exists c \in ℕ such that b = c a

For example:
a)

4 | 8,

because there exists

2 \in ℕ such that 8 = 2 \times 4

4 ∤ 13,

because there does not exist

c \in ℕ such that 13 = c \times 4

If A = $ℤ$ ( The set of all the integers)

Divisibility on

ℤ

a | b (where a, b \in ℤ and b \neq 0), if there exists c \in ℤ such that b = c a

For example:
a)

4 | - 8,

because

there exists - 2 \in ℤ such that - 8 = - 2 \times 4

- 4 ∤ 13,

because

there does not exist c \in ℤ such that 13 = c \times - 4

Division Algorithm

Let a,b (≠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 b = 4, there exists

unique integers q = 3 and r = 1 such that 13 = (4 \times 3) + 1

, clearly

0 \leq 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 a 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 \Rightarrow 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 8 As 0 | 12 and 0 | 8 \Rightarrow 0 | 4 (which is true) As 2 | 12 and 2 | 8 \Rightarrow 2 | 4 (which is true) As 4 | 12 and 4 | 8 \Rightarrow 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 (\neq 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 \in ℤ^{+} 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 (p, a) = 1 or, (p, a) = p.

Property 2):
Let

a, b \in ℤ^{+}, if there exist s, t \in ℤ such that a s + b t = 1, then (a, b) = 1 i . e . a, b are coprimes

.

(Note: We can use the mathematical symbol '

\exists

' for writing 'there exists')
Property 3):
If p is a prime number and a, b are two integers then

p | a b \Rightarrow p | a or p | b

Proof: Let us assume that

p | a b but p ⫮ a and p ⫮ b

Since,

p is a prime and p | a b \Rightarrow (a b, p) = p . . . . . (1) (Using property 1)

And,

p ⫮ a \Rightarrow (a, p) = 1 similiarly p ⫮ b \Rightarrow (b, p) = 1 \Rightarrow \exists s, t, u, v \in ℤ such that a s + p t = 1 and b u + p v = 1 (Using property 2) \Rightarrow \exists s, t, u, v \in ℤ such that (a s + p t) (b u + p v) = 1 \Rightarrow \exists s, t, u, v \in ℤ such that (a b u s + a p v s + p b t u + p^{2} t v) = 1 \Rightarrow \exists (u s), (a v s + b t u + p t v) \in ℤ such that a b (u s) + p (a v s + b t u + p t v) = 1 \Rightarrow (a b, p) = 1

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

p | a b \Rightarrow p | a or p | b

Note: 'Property 3' may fail when p …

To view the complete topic, please