StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q5E

Expert-verifiedFound in: Page 370

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$ .

**From the recursive definition,**

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

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

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

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

Determine mpower (3,5,5).

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

Determine mpower (3,2,5).

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

Simplify further.

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

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

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

Simplify further.

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

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

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

Simplify further.

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

Therefore, the value is ${3}^{11}\mathrm{mod}5=2$ .

94% of StudySmarter users get better grades.

Sign up for free