In modular arithmetic, the numbers we are dealing with are just integers and the operations used are addition, subtraction, multiplication and division.

We say a|b “a divides b” if there exists an integer c such that b = ac.

Euclid’s Division Algorithm

Let a be any integer and d be a positive integer. Then, there exists unique q and r (0 ≤ r < d) such that

a = dq + r.

d is called the divisor, a is called the dividend, q is called the quotient and r is called the remainder.

Modular Arithmetic

Let a be any integer and d be a positive integer. If a = dq + r, then a mod d = r.