Modular Arithmetic

Divisibility on set A

$a|b (\mathrm{where} a, b \in \mathit{A}, b \ne 0 ), \mathrm{if} \exists c\in \mathit{A} \mathrm{such} \mathrm{that} b = ca$ 

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

• If A = $\mathbf{\mathbb{N}}$ ( The set of all the natural numbers)  

           Divisibility on $\mathbf{\mathbb{N}}$:  $a|b (\mathrm{where} a, b \in \mathbf{\mathbb{N}}), \mathrm{if} \exists c\in \mathbf{\mathbb{N}} \mathrm{such} \mathrm{that} b = ca$

• If A = $\mathrm{\mathbb{Z}}$( The set of all the integers)

           Divisibility on $\mathrm{\mathbb{Z}}$: $a|b (\mathrm{where} a, b \in \mathrm{\mathbb{Z}} \mathrm{and} b\ne 0), \mathrm{if} \exists c\in \mathrm{\mathbb{Z}} \mathrm{such} \mathrm{that} b = ca$

Division Algorithm

 $$\begin{gathered} \mathrm{Let} a, b(\ne 0) \mathrm{be} \mathrm{any} \mathrm{two} \mathrm{integers}, \mathrm{then} \exists \mathrm{unique} \mathrm{integers} q \mathrm{and} r \mathrm{such} \mathrm{that} a=bq+r, \\ \mathrm{where} 0\le r<\left|b\right| \end{gathered}$$

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 \mathrm{and} d|b$
(ii)$c|a \mathrm{and} c|b \Rightarrow c|d$ 

Note: GCD of integers a and b is denoted by (a, b). Modular Arithmetic is a system of arithmetic for integers, …