• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q5E

Expert-verified Found in: Page 370 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Trace Algorithm 4 when it is given m = 5 , n = 11 , and b = 3 as input. That is, show all the steps Algorithm 4 uses to find 3 mod 5 .

The value is ${3}^{11}\mathrm{mod}5=2$ .

See the step by step solution

## Step 1: Recursive Definition

From the recursive definition,

${\mathbf{mpower}}{\mathbf{}}{\mathbf{\left(}}{\mathbf{b}}{\mathbf{,}}{\mathbf{n}}{\mathbf{,}}{\mathbf{m}}{\mathbf{\right)}}{\mathbf{=}}\left\{\begin{array}{l}1 \text{if}n=0\\ \mathrm{mpower}\left(b,n/2,m{\right)}^{2}modm \text{if}n\text{even}\\ \left[\mathrm{mpower}\left(b,⌊n/2⌋,m{\right)}^{2}modm\cdot bmodm\right]modm \text{otherwise}\end{array}$

## Step 2: Determine the recursive

Evaluate the recursive definition at n = 11 , m = 5 and b = 3.

${3}^{11}\mathrm{mod}5=\mathrm{mpower}\left(3,11,5\right)$

$\begin{array}{r}=\left[\mathrm{mpower}\left(3,⌊11/2⌋,5{\right)}^{2}mod5\cdot 3mod5\right]mod5\\ =\left[\mathrm{mpower}\left(3,5,5{\right)}^{2}mod5\cdot 3\right]mod5\end{array}$

Determine mpower (3,5,5).

$\begin{array}{r}\mathrm{mpower}\left(3,5,5\right)=\left[\mathrm{mpower}\left(3,⌊5/2⌋,5{\right)}^{2}mod5\cdot 3mod5\right]mod5\\ =\left[\mathrm{mpower}\left(3,2,5{\right)}^{2}mod5\cdot 3\right]mod5\end{array}$

Determine mpower (3,2,5).

$\begin{array}{r}\mathrm{mpower}\left(3,2,5\right)=\mathrm{mpower}\left(3,2/2,5\right)mod5\\ =\mathrm{mpower}\left(3,1,5\right)mod5\\ =\left[\mathrm{mpower}\left(3,⌊1/2⌋,5{\right)}^{2}mod5\cdot 3mod5\right]mod5\\ =\left[\mathrm{mpower}\left(3,0,5{\right)}^{2}mod5\cdot 3\right]mod5\end{array}$

Simplify further.

$\begin{array}{r}\mathrm{mpower}\left(3,2,5\right)=\left[{1}^{2}mod5\cdot 3\right]mod5\\ =\left[1\cdot 3\right]mod5\\ =3mod5\\ =3\end{array}$

Evaluate the found expression for mpower (3,5,5).

$\begin{array}{r}\mathrm{mpower}\left(3,5,5\right)=\left[\mathrm{mpower}\left(3,⌊5/2⌋,5{\right)}^{2}mod5\cdot 3mod5\right]mod5\\ =\left[\mathrm{mpower}\left(3,2,5{\right)}^{2}mod5\cdot 3\right]mod5\\ =\left[{3}^{2}mod5\cdot 3\right]mod5\\ =\left[9mod5\cdot 3\right]mod5\end{array}$

Simplify further.

$\begin{array}{r}\mathrm{mpower}\left(3,5,5\right)=\left[4\cdot 3\right]mod5\\ =12mod5\\ =2\end{array}$

Evaluate the found expression for mpower (3,11,5).

$\begin{array}{r}{3}^{11}mod5=\mathrm{mpower}\left(3,11,5\right)\\ =\left[\mathrm{mpower}\left(3,⌊11/2⌋,5{\right)}^{2}mod5\cdot 3mod5\right]mod5\\ =\left[\mathrm{mpower}\left(3,5,5{\right)}^{2}mod5\cdot 3\right]mod5\\ =\left[{2}^{2}mod5\cdot 3\right]mod5\end{array}$

Simplify further.

$\begin{array}{r}{3}^{11}mod5=\left[4mod5\cdot 3\right]mod5\\ =\left[4\cdot 3\right]mod5\\ =12mod5\\ =2\end{array}$

Therefore, the value is ${3}^{11}\mathrm{mod}5=2$ . ### Want to see more solutions like these? 