# Algorithms for computing multiplicative order modulo $n$

If I take the $$k \in \mathbb{N}$$ power of 10 and mod it by a large prime, I notice that the remainders repeat at some point.

For instance $$10^k mod~7$$ seems to repeat every $$6^{th}$$ value of $$k$$.

Given $$k$$ (the power of ten), and a large prime number $$p$$, how can I compute the size of the cycle?

I tried writing a python script that computes the first instance of a repeat. However, I don't know if this works since a single instance of a repeat may not necessarily mean a full cycle.

For $a^k \pmod p$, this cycle that you refer to has the name "order". We generally write this as $\text{ord}_p(a)$, that is the minimum $k$ such that $a^k \equiv 1 \pmod p$. (Then the cycle starts back at $a$). There is not really a good way to estimate this well. A weak estimate comes from Fermat's Little Theorem, a stronger one comes from the Euler Totient Function, and the strongest one that I know is the Carmichael function. Wikipedia has information on all of these.
To elaborate on the Carmichael function, if $\gcd(a,b) = 1$, define the Carmicheal value of $b$ as $\lambda(b)$.
Then it is well known (and easily proven) that $a^{\lambda(b)} \equiv 1 \pmod {b}$. Now from prime $p$, define $\lambda(p^k) = \phi(p^k)$ where $\phi$ is the totient function. Let $b = \prod_i p_i^{a_i}$. Then $\lambda(b) = lcm(\phi(p_1^{a_1}), \phi(p_2^{a_2}), \cdots)$.
• Thanks! How do I use Fermat's Little Theorem to obtain a suboptimal order? If $a^p \equiv a~mod~p$, does that imply we cycle every $p$ elements? Commented Apr 8, 2014 at 0:54
• Fermat's Little Theorem only works modulo prime. However, it is just $a^{p-1} \equiv 1 \pmod a$ when $\gcd(a,p) = 1$. A well known fact about orders is that when ever we find a $k$ such that $a^{k} \equiv 1 \pmod p$, then the order is a factor of $k$. I dont think it is hard to program the totient function in python which works pretty well. Commented Apr 8, 2014 at 1:09
• You can also write it base $p$ and sum the digits ... Commented Jul 26, 2021 at 23:41
The least $$\,n >0\,$$ such that $$\,a^n\equiv 1\pmod p\,$$ is called the order of $$\,a\pmod p.\,$$ For the state-of-the-art on the order computation algorithms see Andrew Sutherland's 2007 MIT Thesis Order Computations in Generic Groups. Below is an excerpt from p. 14.