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.