Division

Let a and b be two integers with a $\neq$ 0, we say that a divides b if there is an integer k such that b=ka, and we write a | b

Notations

• ‘a divides b’ is denoted by a | b (e.g. 3 | 21)
  • 3 is a factor of 21; 3 is a divisor of 21
  • 21 is a multiple of 3
• ‘a does not divide b’ is denoted by a ∤ b ****(e.g. 3 ∤ 20)

Basic Rules

• if a | b and a | c, then a | (b + c)
• if a | b, then a | bc for all integers c
• if a | b and b | c, then a | c

Division Algorithm (mod)

Let a be an integer and d be a positive integer. Then there are unique integers q and r with 0 ≤ r < d, such that a = dq + r

a : dividend d : divisor

q : quotient r : remainder

Notation:

• q = a div d
• r = a mod d
• examples

Modular Arithmetic

Let a and b be integers and M a positive integer. We say that a is congruent to b modulo M if M divides a-b. We write,

a $\equiv$ b (mod M) if and only if M | (a - b)

[Theorem 3]

If a $\equiv$ b (mod M) and c $\equiv$ d (mod M)

• a + c $\equiv$ b + d (mod M)
• ac $\equiv$ bd (mod M)

[Corollary]

Let M be a positive integer and let a and b be integers. Then,

(a+b) mod M = ((a mod M) + (b mod M)) mod M

(ab) mod M = ((a mod M) x (b mod M)) mod M

[Computing $b^n$ mod $m$]