Question

Devise a recursive algorithm for finding${\mathit{x}}^{\mathit{n}}$ whenever n, x, and m are positive integers based on the fact that ${\mathbf{x}}^{\mathbf{n}}\mathbf{mod}\mathbf{m}\mathbf{=}\left(x^{n-1}modm\cdot xmodm\right)\mathbf{mod}\mathbf{m}\mathbf{.}$.

Short answer

The recursive algorithm is,

$$\begin{gathered} \mathrm{procedure}\mathrm{modulo}\left(\mathrm{n},\mathrm{x},\mathrm{m}:\mathrm{positive}\mathrm{integers}\right) \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}\mathrm{x}\mathrm{modm} \\ \mathrm{return}(\mathrm{modulo}(\mathrm{n}-1,\mathrm{x},\mathrm{m}).\mathrm{x}\mathrm{mod}\mathrm{m})\mathrm{mod}\mathrm{m} \end{gathered}$$

Step-by-step solution

Describe the given information

The objective is to write the recursive algorithm for ${\mathit{x}}^{\mathbf{n}}\mathit{m}\mathit{o}\mathit{d}\mathbf{}\mathit{m}$.

Give a recursive algorithm for computing  xn mod m

Call the algorithm "modulo" and the input are three positive integers n , x and m .

$\text{procedure modulo}(n,x,m\text{: positive integers})$

When the power n is 1 , then $x^n$mod m = x mod m .

if n = 1 then

return x mod m

Since,

$\begin{array}{r}{\mathrm{x}}^{\mathrm{n}}mod\mathrm{m}=\left({\mathrm{x}}^{\mathrm{n}-1}mod\mathrm{m}\cdot \mathrm{x}mod\mathrm{m}\right)mod\mathrm{m}\\ \text{else}\\ \text{return}(mod\mathrm{ulo}(\mathrm{n}-1,\mathrm{x},\mathrm{m})\cdot \mathrm{x}mod\mathrm{m})mod\mathrm{m}\end{array}$

By combining all the steps the algorithm is obtained as:

$$\begin{gathered} \mathrm{procedure}\mathrm{modulo}\left(\mathrm{n},\mathrm{x},\mathrm{m}:\mathrm{positive}\mathrm{integers}\right) \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}\mathrm{x}\mathrm{modm} \\ \mathrm{return}(\mathrm{modulo}(\mathrm{n}-1,\mathrm{x},\mathrm{m}).\mathrm{x}\mathrm{mod}\mathrm{m})\mathrm{mod}\mathrm{m} \end{gathered}$$

Therefore, the recursive algorithm is shown above.