# 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)

## 2 Answers

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 one can use the following well-known simple order algorithm for groups
This thesis is a good reference on order algorithms in generic groups. Here's the abstract:

• now this is a useful result! so basically, I only have to check for every divisor of $\lambda(n)$? – Eugene Bulkin Sep 27 '10 at 3:31
• Yes, in any group the order of an element divides the order/expt of the group (Lagrange's theorem) - see my post here math.stackexchange.com/questions/4715 – Bill Dubuque Sep 27 '10 at 3:53
• @Eugene: That one's from Cohen's "A Course in Computational Algebraic Number Theory"; a good book, if you can find it in your nearest library. – J. M. is a poor mathematician Sep 27 '10 at 3:54

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

• most values of $b$ that I would work with would not be too difficult to factorize, but otherwise I agree – Eugene Bulkin Sep 27 '10 at 3:30
• @Eugene Bulkin: but the problem is hard even if b is prime (since one needs to factor b-1). I just mean that if you are given a large random value of b it isn't trivial to apply Carmichael's theorem to it. – Qiaochu Yuan Sep 27 '10 at 3:32
• from what I understood looking up Carmichael's theorem, all that is necessary is the prime factorization of b; $\lambda(p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n})=\mathrm{lcm}(\lambda(p_1^{k_1}),\lambda(p_2^{k_2}),\ldots,\lambda(p_n^{k_n}))$, and the function is simple for any $p^k$. – Eugene Bulkin Sep 27 '10 at 13:17
• @Eugene Bulkin: the possible values of n are the divisors of lambda(b), so not only is it necessary to factor b to compute lambda(b), it is then necessary to factor lambda(b). This is not hard if b is smooth (e.g. it is a large power of a small prime) but is very hard if b is a random prime, since b-1 is for all intents and purposes a random number. – Qiaochu Yuan Sep 27 '10 at 16:13
• that is true. I was mostly learning this for a math contest, so they wouldn't really give us any particularly difficult ones. thanks though! – Eugene Bulkin Sep 27 '10 at 22:23