Compute the following values.

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

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

  1. Base case: a0 = 1
  2. Recursive definition: bn = b.bn-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, b0 = 1

Here, power(b, 0) = 1

Inductive Step:

Algotithm computes bk+1

Suppose, power(b, k) = bk ∀ b ≠ 0 and k is +ve integer

Now,

To show power (b, k+1) = bk+1

By inductive gypothesis,

power(b, k+1) = b × bk = bk+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.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .