Distinct integers reached under modulo

Question

This seems like a rather simple problem but I can't seem to figure out how to even approach it. Any ideas would be greatly appreciated:

Given integers $N$ and $S$, how can we determine the smallest integer $i$ s.t.:

$S^i \,mod\, N$ = 1

We can assume that $N > S$ and $S>1$ if that helps.

Answer 1

You also need to assume $\gcd(S, N) = 1$.

There isn't a good approach to the general problem, though: it's hard!

You can use the Chinese remainder theorem to reduce the problem to prime power moduli — this requires factoring $N$.

You can use $p$-adic logarithms to reduce the problem to prime moduli (this part is fairly simple, once you know the theory).

And to the best of my knowledge, the best general algorithm for solving the problem when $N$ is prime is:

• For every $i$ dividing $N-1$:
  • Compute (a reduced representative of) $S^i \bmod N$ to see if it is congruent to $1$

Which requires at least partially factoring the number $N-1$; in the typical case you'd have to factor it completely.

---

In my opinion, for the sorts of small problems you'd typically be doing by hand, you might as well just use brute force since it's simpler. That is, write down all of the powers of $S$ until you reach $1$.

Answer 2

There may be no such integer. Consider $N = 12$ and $S = 3$. The powers of $S$, mod $12$, are $3, 9, 3, 9, 3, 9, \ldots$, so no power is ever congruent to $1 \bmod 12$. In short: your question does not, in general, have an answer.

Well...except that $3^0 = 1$, and $1 \bmod 12 = 1$, but I'm not at all certain whether $i = 0$ is an allowable answer for you. If so, it's the answer for any $S$ and $N$ except $N = 0$. (Assuming that by "smallest" you mean "smallest in absolute value".)