How do I find the lowest $n$ for which $a^n \equiv 1 \pmod{b}$? This is mostly related to doing large modular exponentiation by hand. For example, a problem I was doing was to find the last 3 digits of $7^{9729}$; that is, find $7^{9729}\bmod{1000}$.
Using the simplest concept for Euler's theorem, I found that $7^{400}\equiv 1\pmod{1000}$, since $\varphi(1000)=400$. Using Carmichael's theorem, I found a smaller number, $7^{100}\equiv 1\pmod{1000}$, as $\lambda(1000)=100$. Now, by manually multiplying it out, I found that $7^{20}\equiv 1 \pmod{1000}$, and that is the first $n$ for which that is true, meaning I just need to find $7^9 \bmod{1000}$, making the answer 607.
Is there a way to arrive at this answer without multiplying it out each time for every number I get? For example, could I do something like $13^{12937}\bmod{1000}$ without sitting around modding out multiples of $13^4$? (I know that the first $n$ for 13 would be 100, so no less than using Carmichael's theorem, but I want to know if there are other ways to find numbers lower than those given by Carmichael's theorem)
 A: If $\rm\: gcd(a,10)=1\:$ then order of $\rm\: a\:$ in $\:\mathbb Z/1000 \:$ must be a divisor of $100 = \lambda(1000)$. You can compute the order simply and quickly by computing in order  $\rm a^2, a^4, a^5, a^{10}, a^{20}, a^{25}, a^{50}\:$ by squaring or multiplying previous entries. This requires at most 5 squaring and 2 multiplication operations $\rm (mod\ 1000)$. Obviously the same sort of optimized divisor lattice searching works for any modulus.
Alternatively we can use the following well-known simple order algorithm for groups (based upon the Order Test), from Cohen's book A Course in Computational Algebraic Number Theory.

This thesis is a good reference on order algorithms in generic groups. Here's the abstract:

A: As I discuss in my answer to this question, this is a hard quantity to compute in general.  For practical purposes you should use exponentiation by squaring to test the possibilities (and you should definitely use exponentiation by squaring for computing remainders in general; this is how computer algebra systems do it).  Note that using Carmichael's theorem is not trivial, as it requires that you know the prime factorization of $b$.  
