9
$\begingroup$

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)

$\endgroup$
0

2 Answers 2

Reset to default
10
$\begingroup$

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.
alt text
This thesis is a good reference on order algorithms in generic groups. Here's the abstract: alt text

$\endgroup$
3
  • $\begingroup$ now this is a useful result! so basically, I only have to check for every divisor of $\lambda(n)$? $\endgroup$
    – Eugene Bulkin
    Commented Sep 27, 2010 at 3:31
  • $\begingroup$ 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 $\endgroup$
    – Bill Dubuque
    Commented Sep 27, 2010 at 3:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – J. M. ain't a mathematician
    Commented Sep 27, 2010 at 3:54
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ most values of $b$ that I would work with would not be too difficult to factorize, but otherwise I agree $\endgroup$
    – Eugene Bulkin
    Commented Sep 27, 2010 at 3:30
  • $\begingroup$ @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. $\endgroup$
    – Qiaochu Yuan
    Commented Sep 27, 2010 at 3:32
  • $\begingroup$ 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$. $\endgroup$
    – Eugene Bulkin
    Commented Sep 27, 2010 at 13:17
  • $\begingroup$ @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. $\endgroup$
    – Qiaochu Yuan
    Commented Sep 27, 2010 at 16:13
  • $\begingroup$ 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! $\endgroup$
    – Eugene Bulkin
    Commented Sep 27, 2010 at 22:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .