2
$\begingroup$

I am new to Mathematica and I have a For loop like so:

For[i = 0, i < 15, i++, PowerMod[i, -1, 15]]

Currently it doesn't output anything. The calculation I am performing is i^-1 mod n. I want t his loop to output the values of i ONLY where i = i^-1 mod n. How can i accomplish this?

Edit

I can print the output by wrapping PowerMod in Print[]. How can I accomplish printing i and then the result from PowerMod? Here is what I tried, but it is incorrect since I don't know the syntax to use here:

For[i = 0, i < 15, i++, Print[i] Print[PowerMod[i, -1, 15]]]

This prints i and then the result of PowerMod below it. How can I get them on the same line?

$\endgroup$
  • $\begingroup$ Note that in Mathematica For-loops always return Null, which does not print at top-level. $\endgroup$ – m_goldberg Feb 21 '15 at 1:46
  • $\begingroup$ I edited my questions if you could take a look again please. $\endgroup$ – connor Feb 21 '15 at 1:55
  • $\begingroup$ Nvm, I figured it out looking at wolframs docs. Any clue if there is an equal sign with a ? above it symbol in mathematica? $\endgroup$ – connor Feb 21 '15 at 1:57
  • $\begingroup$ Try Overscript["=", "?"] $\endgroup$ – 2012rcampion Feb 21 '15 at 2:13
  • $\begingroup$ Did I match your needs with my answer? $\endgroup$ – Jinxed Feb 22 '15 at 22:41
3
$\begingroup$

Avoid the For-loop. Here is way to do this with functional programming tools, which are more idiomatic to Mathematica.

Quiet[Table[{i, PowerMod[i, -1, 15]}, {i, 1, 14}]] // Cases[{x_, x_} :> x]
{1, 4, 11, 14}
$\endgroup$
  • $\begingroup$ Nice use of the operator form of Cases, I never know when to use it. $\endgroup$ – 2012rcampion Feb 21 '15 at 2:02
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Here is a simple function, which lets you calculate your result for any modulus n:

pm[n_Integer/;n>1]:=Quiet@Select[Range[0,n-1],PowerMod[#,-1,n]==#&]

e.g.:

pm[15]   (* {1,4,11,14} *)
pm[30]   (* {1,11,19,29} *)
pm[3129] (* {1,148,895,1042,2087,2234,2981,3128} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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