# Division Algorithm

### 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

4k – 3k – 1 = 9m

⇒ 4k = 9m + 3k + 1

Now f (k + 1) = 4K⁺¹ – 3 (k + 1) – 1 = 4K .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.