0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Faux Apr 8 '14 at 0:54
  • $\begingroup$ 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. $\endgroup$ – Sandeep Silwal Apr 8 '14 at 1:09
1
$\begingroup$

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.

enter image description here
enter image description here

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