Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

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 .

Short Answer

Expert verified

The value is311mod5=2 .

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards

Over 22 million students worldwide already upgrade their learning with Vaia!

01

Recursive Definition

From the recursive definition,

mpower(b,n,m)={1    ifn=0mpower(b,n/2,m)2modm    ifnevenmpower(b,n/2,m)2modmbmodmmodm    otherwise

02

Determine the recursive

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

311mod5=mpower(3,11,5)

=mpower(3,11/2,5)2mod53mod5mod5=mpower(3,5,5)2mod53mod5

Determine mpower (3,5,5).

mpower(3,5,5)=mpower(3,5/2,5)2mod53mod5mod5=mpower(3,2,5)2mod53mod5

Determine mpower (3,2,5).

mpower(3,2,5)=mpower(3,2/2,5)mod5=mpower(3,1,5)mod5=mpower(3,1/2,5)2mod53mod5mod5=mpower(3,0,5)2mod53mod5

Simplify further.

mpower(3,2,5)=12mod53mod5=[13]mod5=3mod5=3

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

mpower(3,5,5)=mpower(3,5/2,5)2mod53mod5mod5=mpower(3,2,5)2mod53mod5=32mod53mod5=[9mod53]mod5

Simplify further.

mpower(3,5,5)=[43]mod5=12mod5=2

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

311mod5=mpower(3,11,5)=mpower(3,11/2,5)2mod53mod5mod5=mpower(3,5,5)2mod53mod5=22mod53mod5

Simplify further.

311mod5=[4mod53]mod5=[43]mod5=12mod5=2

Therefore, the value is311mod5=2 .

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Study anywhere. Anytime. Across all devices.

Sign-up for free