a. 3 mod 4 b. 7 mod 5 c. -5 mod 3 d. 11 mod 5 e. -8 mod 6

Write down the recursive algorithm to find the value of b^{n} and prove its correctness using induction.

This answer is restricted. Please login to view the answer of this question.

Login Now**Problem Part:**

a) 3 mod 4

= 3 (mod 4)

= 3

b) 7 mod 5

= 7 (mod 5)

= 2

c) 11 mod 5

= 11 (mod 5)

= 1

d) -8 mod 6

= -8 (mod 6)

= 4

**Algorithm Part:**

A recursion algorithm for b^{n}

Here, the power function can be defined recursively as:-

- Base case: a
^{0}= 1 - Recursive definition: b
^{n}= b.b^{n-1}for b > 1

power (b, nb)

1. Start 2. If (n == 0) return 1; else return b*power(b, n-1) 3. End

**Proof by induction**

Base case: If n = 0, b^{0} = 1

Here, power(b, 0) = 1

Inductive Step:

Algotithm computes b^{k+1}

Suppose, power(b, k) = b^{k} ∀ b **≠ **0 and k is +ve integer

Now,

To show power (b, k+1) = b^{k+1}

By inductive gypothesis,

power(b, k+1) = b × b^{k} = b^{k+1}

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.

Click here to submit your answer.

HAMROCSIT.COM

## Discussion