# Computing $a^r \bmod n$ for a real number $r < 1$

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.

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

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