**Division Algorithm**

If 0 ≠ a, b ϵ Z then ∃ q, r ϵ Z uniquely such that b = aq + r where 0 ≤ r < |a|. A nonzero integer a is said to divide an integer b if there exist q ϵ z such that b = aq. It is denoted by a/b.

**Note 1:**If a/b then we also called a is a divisor of b or a is a factor of b or b is a multiple of a.**Note 2:**If a, b ϵ N, a/b then the integer q ϶ b =aq is a positive integer.

**1.** Show that 4ⁿ – 3n – 1 is divisible by 9 for all n ϵ N.

**Solution:** Let S(n) be the statement that f(n) = 4ⁿ – 3n – 1 is divisible by 9.

f(1) = 4¹ – 3 (1) – 1 = 0 is divisible by 9

Assume that S(k) is true

f(k) is divisible by 9 and hence f(k) = 9m

4^{k} – 3k – 1 = 9m

⇒ 4^{k} = 9m + 3k + 1

Now f (k + 1) = 4^{K}⁺¹ – 3 (k + 1) – 1 = 4^{K} .4 – 3 (k + 1) – 1

= 4 (9m + 3k + 1) – 3k – 4

= 36m + 12k + 4 – 3k – 4

= 36m + 9k

= 9 (4m + k) [∵ Divisible by 9]

Therefore S(k+1) is true by principal of finite mathematical induction S(n) true for all n ϵ N

**2.** Show that 2.4²ⁿ⁺¹ + 3³ⁿ⁺¹ is divisible by 11 for all n ϵ N

**Solution: **Let S(n) be the statement that

f (n) = 2.4²ⁿ⁺¹ + 3³ⁿ⁺¹ is divisible by 11

f (1) = 2.4²^{(}¹^{)}⁺¹ + 3³^{(}¹^{)}⁺¹ = 2 x 64 + 81 = 209 = 11 x 19, divisible by 11

Therefore S(1) is true

Assume that S(k) is true

Therefore f(k) is divisible by 11

f (k) = 2.4²^{k}⁺¹ + 3³^{k}⁺¹ is divisible by 11

f (k) = 2.4²^{k}⁺¹ + 3³^{k}⁺¹ = 11q where q ϵ N

Consider f (k + 1) = 2.4²^{(k}⁺¹^{)}⁺¹ + 3³^{(k}⁺¹^{)}⁺¹

f (k + 1) = 2.4²^{k}⁺¹4² + 3³^{k}⁺¹3³

16 (11q – 3³^{k}⁺¹) + 27. 3³^{k}⁺¹ = 176q – 16. 3³^{k}⁺¹ + 27. 3³^{k}⁺¹ = 176q + 11. 3³^{k}⁺¹

11 (16q + 3³^{k}⁺¹) is divisible by 11

Therefore f(K+1) is true

by principal of finite mathematical induction S(n) true for all n ϵ N

2.4²ⁿ⁺¹ + 3³ⁿ⁺¹ is divisible by 11 for all n ϵ N.