# How does one compute how big the cycle of modding by a prime number is?

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 $8$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.

## 2 Answers

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? – David Faux Apr 8 '14 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. – Sandeep Silwal Apr 8 '14 at 1:09

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.  