Skip to main content
3 of 3
replaced http://mathematica.stackexchange.com/ with https://mathematica.stackexchange.com/

Let's rephrase your question a little:

I want this loop to, IFF $i\equiv i^{-1}\mod n$, output the value of $i$.

Translating this into Mathematica:

If[i == PowerMod[i, -1, n], Print[i]]

We can make a few improvements. First, I'll use Do instead of For (Try to avoid constructs like For and While in Mathematica, they're less idiomatic). I'll also make your loop a function, so you can easily call it for different moduli:

selfInverses[n_] := Do[If[i == PowerMod[i, -1, n], Print[i]], {i, 0, n - 1}]

We're still getting those "not invertible" errors, so let's try a slightly different tack. By multiplying both sides of the condition by $i$, we get:

$$ \begin{align} i(i)&\equiv i^{-1}(i)\mod n \\ i^2&\equiv 1\mod n \end{align} $$

Since you can always multiply two numbers [citation needed], you don't get those errors. Putting in these changes:

selfInverses[n_] := Do[If[1 == PowerMod[i, 2, n], Print[i]], {i, n}]

(If for some reason you needed to keep PowerMod[i, -1, n], I suggest checking that i is invertible first with Not[CoprimeQ[i, n]] && PowerMod[i, -1, n] == i)

Note that the iterator for this Do, {i, n}, loops from 1 to n, not 0 to n - 1 as your code did. However, since $0^2\equiv 0\not\equiv 1$ and $n^2\equiv n\equiv 0\not\equiv 1\mod n$, neither end case will change our results.

Printing the results is less helpful if you want to use the results later, so we'll have the function generate a list instead:

selfInverses[n_] := 
 Reap[Do[If[1 == PowerMod[i, 2, n], Sow[i]], {i, n}]][[2, 1]]

An example of usage:

selfInverses[15] (* returns {1, 4, 11, 14} *)

If you're having trouble understanding what this function is doing, look at the documentation of the functions used.

2012rcampion
  • 7.9k
  • 26
  • 44