# Recursive algorithm

1. Jan 29, 2006

### neik

Devise a recursive algorithm for finding $$x^n \bmod m$$ whenever n, x, and m are positive integers, based on the fact that

$$x^n \bmod m = (x^{n-1} \bmod m \cdot x \bmod m) \bmod m$$

can anyone give me some hints? i dont know where to start

thank you

Last edited: Jan 29, 2006
2. Jan 29, 2006

### 0rthodontist

Well, it's pretty much given to you. Define a function

powermod(x, n, m)

Inside this function you will use 2 ordinary mods and a recursive call to powermod. Don't forget a base case.

3. Jan 30, 2006

### ramsey2879

I guess that you would start with $$x^0 = 1$$ or $$x^1 = x \mod m$$. Is this a homework problem? If so, see the first topic.

4. Jan 30, 2006

### Hurkyl

Staff Emeritus
I hate to ask, but do you even know what a recursive algorithm is? This is a fill-in-the-blanks type problem... and you've been handed almost the entire answer!

Last edited: Jan 30, 2006
5. Jan 30, 2006

### neik

thanks every one, i got the answer

thats why i have to ask 'coz its too good to be true.
i dont think this question hurts you, does it?

its not your fault if you dont understand the question; but it is if you dont know how to ask. Besides, i only ask for hint and not the answer.

Last edited: Jan 30, 2006
6. Jan 31, 2006

### Hurkyl

Staff Emeritus
I took you literally when you said "I don't know where to start".

7. Jan 31, 2006

### neik

if every were only half as perfect as you then we might not need this home work area.