6
$\begingroup$

I would like to find smallest x value for each m value such that Mod[3^x, m] == 1, where m is not multiple of 3.

Here is my try, which is not optimal for large m, say m >= 10000. How can I write a condition in Table, so that whenever the condition Mod[3^x, m] == 1 holds, the computation breaks and proceeds to the next m value?

A different approach would also be welcome.

range = 100;
m = Complement[Range[2, range], Range[3, range, 3]];
sol = ParallelTable[Mod[3^x, m[[i]] ] , {i,  Length @ m}, {x, range}];
pos = FirstPosition[#, 1] & /@ sol;
Transpose @ {m, Flatten @ pos}

Edit Here is two different and faster method I found. First time I am using While and Break in my code :)

range = 10;
m = Complement[Range[2, range], Range[3, range, 3]];
val = (x = 1; While[x <= range, If[Mod[3^x, #] == 1, Break[]]; x++]; 
     x) & /@ m;
Transpose@{m, val}

{{2, 1}, {4, 2}, {5, 4}, {7, 6}, {8, 2}, {10, 4}}

range = 10;
m = Complement[Range[2, range], Range[3, range, 3]];
val = Last@
      Reap@Do[If[Mod[3^x, #] == 1, Sow@x; Break[]], {x, range}] & /@ 
    m // Flatten;
Transpose@{m, val}

{{2, 1}, {4, 2}, {5, 4}, {7, 6}, {8, 2}, {10, 4}}

Edit 2 I realized one can use Throw and Catch functions.

range = 10;
m = Complement[Range[2, range], Range[3, range, 3]];
val = Catch@Table[If[Mod[3^x, #] == 1, Throw@x], {x, range}] & /@ m
Transpose@{m, val}



range = 10;
m = Complement[Range[2, range], Range[3, range, 3]];
val = Catch@Do[If[Mod[3^x, #] == 1, Throw@x], {x, range}] & /@ m
Transpose@{m, val}
$\endgroup$
  • 5
    $\begingroup$ Lookup the function MultiplicativeOrder $\endgroup$ – Carl Woll Mar 17 '18 at 21:19
  • $\begingroup$ Wow! I was not aware that function. Thanks. {#, MultiplicativeOrder[3, #]} & /@ m $\endgroup$ – OkkesDulgerci Mar 17 '18 at 21:26
  • $\begingroup$ I think that Euler's Theorem may be helpful for this, it can be used to find an x quickly, but I'm not sure about the finding the lowest such x $\endgroup$ – Alex Li Mar 18 '18 at 2:57
6
$\begingroup$

Although this question can be answered by a link to the documentation of MultiplicativeOrder, I think something more should put on record because MultiplicativeOrder can not be expected to be known or easy to find for Mathematica beginners.

First we generate the search space.

searchSpace =
  With[{max = 100}, Module[{r = Range[2, max]}, Pick[r, Not /@ Divisible[r, 3]]]];

And now we use MultiplicativeOrder to generate the requested table, which we then plot.

ListPlot[{#, MultiplicativeOrder[3, #]} & /@ searchSpace,
  PlotRangePadding -> {Automatic, {Automatic, 15}},
  AspectRatio -> 1]

plot

$\endgroup$
  • $\begingroup$ Thanks for the answer. Question is now how can we solve this problem without MultiplicativeOrder. I wanna learn efficient way to solve this problem. $\endgroup$ – OkkesDulgerci Mar 18 '18 at 1:42
  • $\begingroup$ @OkkesDulgerci. That you were more interested in the algorithm and its implementation than in making computations with it is not at all clear in your question. However, you should not bring the issue up in a comment to an answer. You should edit the question to bring the community's attention to it. $\endgroup$ – m_goldberg Mar 18 '18 at 8:03

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