Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to calculate $d^{1/x} \bmod n$ where $d$ and $x$ belong to $\Bbb Z_n$. Here $x$ is greater than one, thus $1/x$ is less than one. How can I do a computation like that? For example what is the result of

$$5^{0,23} \bmod 4?$$

(In fact I am trying to implement this in the language PHP, but this is not important.)

Thanks again.

share|improve this question
1  
In modular arithmetic, $1/x$ usually does not correspond to dividing $1$ by $x$ in the "real" sense, but by computing the inverse of $x$ in the relevant field. –  TMM May 10 '13 at 15:17
    
@TMM Thank you. I will try it now, and I will tell you if I can do this works. Thanks again –  Jasmin May 10 '13 at 15:21
1  
Your example doesn't fit your question, since $0.23$ is not of the form $1/x$. Also, in $\mathbb Z_n$, it is not generally true that $a^{m}=a^{m+n}$, so there is really no point in thinking of the exponent as being in $\mathbb Z_n$. –  Thomas Andrews May 10 '13 at 15:23
    
@TMM Thank you very much. I was (and am) a little confused. If I have (100 ^ 121) mod 257 then ((100 ^ 121) mod 257) ^ (1/121) mod 257 than the result of the second equation is equal to 100? –  Jasmin May 10 '13 at 16:26
    
@Andres: Yes. Note that $(a^x)^y = a^{xy}$, so $(a^x)^{1/x} = a^{x/x} = a^1 = a$. You should not compute $1/121 = 0.00826\ldots$ as that is irrelevant. –  TMM May 10 '13 at 16:29

1 Answer 1

up vote 1 down vote accepted

As @TMM said, $\frac 1 x$ should be equal to $x^{-1}$ for some $x\in \mathbb{Z}_n$ in modular arithmetic. You can compute the inverse element in $\mathbb{Z}_n$, if $(x,n) = 1$, using the extended Euclid algorithm. If you find $(a, b)$, so that $ax+bn = 1$, then $ax = 1 (mod~n)$, $a = x^{-1}$.

share|improve this answer
    
Thank you very much. I was (and am) a little confused. If I have (100 ^ 121) mod 257 then ((100 ^ 121) mod 257) ^ (1/121) mod 257 than the result of the second equation is equal to 100? –  Jasmin May 10 '13 at 16:19
    
$121^{-1} = 17 (mod 257)$, so $(100^{121})^{\frac {1}{121}} = (100^{121})^{17} = 100^{121\cdot 17} = 141 (mod~257)$ –  Harold May 10 '13 at 16:46
    
This isn't the root. The problem of getting the root is much harder. –  Harold May 10 '13 at 16:51
    
Thank you. However that's kind of strange... If I have the number 100 and the number 257 is my modulo number, then how I can choose the powers, in order to get number 100 bavk, when I apply these two powers? –  Jasmin May 10 '13 at 16:52
    
You can use the Euler's criterion. Just note that $a^{256}=1~(mod~257)$ for any $a$, so $100^{256\cdot C+1}=100^{1} (mod~257)$ for any $C$. –  Harold May 10 '13 at 17:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.