Re: Puzzled (4^162 mod 100)

In article <D0JXf.135522$_o1.1459194@wagner.videotron.net>,
Carlos Moreno <moreno_at_mochima_dot_com@mailinator.com> wrote:
>
>I stumbled into this exercise in number theory, and I'm
>clueless about what is the "correct" way to solve it.

Your method is correct; no need for the square quotes.

>The exercise is computing 4^162 mod 100 (I'm given the
>tip that phi(100) is 40 -- which I could calculate, but
>I'm given that piece of information).

The tip is a bit misleading, IMHO.

>The thing is, the answer is 16, but I don't know how to
>obtain it without "cheating" (I double cheated -- to
>verify my first level of cheating, I just wrote a three-
>liner program that computes it).
>
>If I start multiplying 4 several times, always modulo 100,
>then after 10 times I obtain 4 again -- this immediately
>tells me that 4^N mod 100 is the same as 4^(N mod 10) mod 100
>(and the program confirms this, reporting a result of 16)

THis is fine.

>But, why? If 4 and 100 were relatively prime, then I'd
>know the exponent is cyclic modulo phi(100), which is
>40 -- then, 4^162 is reduced to 4^(162 mod 40), or
>4^2 (by coincidence, it gives me the correct result!!)

The result is cyclic regardless. If you have a and b, b>1, and you
want to compute a^n, then

  (i) If (a,b)=1, the sequence a, a^2, a^3,...., computed so that we
  always use the smallest nonnegative integer congruent to a^k modulo
  b, will eventually have a value of 1; and we can show that it will
  have value 1 at some divisor of phi(b). If

  k = min { r>0 | a^r = 1}

  then it is not hard to verify that a^r = a^s if and only if
  r=s (mod k). All this information can be kept trakc of by the
  single number k, and the number k will allow you to compute
  not-too-hardly the value of a^N (mod b) for any N.

 (ii) If (a,b)=k>1, then the sequence a, a^2, a^3, ..., computed so
 that we always use the smallest nonnegative integer conguent to a^k
 modulo b, will ALSO eventually repeat; this because there are only
 finitely many possible "remainders". In this case, we also know that
 the sequence will never take the value 1, so we may end up with a
 more complex cycle.

 
Nonetheless, in case (ii), there will be two positive integers, n and
k, with the following properties:

   (a) a^n = a^{n+k} (mod b)
   (b) n = min {m>0 | there exists r>0 such that a^m = a^{m+r} }
   (c) k = min {r>0 | a^n = a^{n+k}, n as in (b) }.

In that case, it is not too hard to verify that a^r = a^s if and only
if (r=s) or (r,s>=n, and r=s (mod k) ).

In this case, you will need to keep track of the TWO numbers, (n,k)
(in the specified order); these two numbers will allow you to compute
a^N (mod b) for any N.

The question here, of course, is whether n and k have any relation with
phi(b), the way that it happens in case (i). See below.

>What other principle/property am I supposed to use to
>analytically obtain this result (i.e., without resorting
>to calculating things until I either get the result or
>observe a pattern that allows me to take a shortcut)

You can do it by invoking the Chinese Remainder Theorem. Let me do it
for the example you have, then I will get back to case (ii) above.

You are working modulo 100 = 25*4. By the Chinese Remainder Theorem,
given any r and s, there exist a unique x (modulo 100) such that
x=r (mod 25) and x=s (mod 4). Thus, if you figure out 4^{162} (mod 25)
and 4^{162} (mod 4), that will give you values of r and s, which in
turn will give you a unique value modulo 100.

Now, 4^{162} (mod 4) is easy: it is just 0. As for the congruence
modulo 25, you know that phi(25) = 20; since (4,25)=1, we are in case
(i) above, so 4^{20}=1 (mod 25); in particular, 4^{160}=1 (mod 25),
and 4^{162} = 4^2*4^{160} = 4^2 = 16 (mod 25).

So the answer is that if 4^{162}=x (mod 100), then

x = 16 (mod 25)
x = 0 (mod 4).

Now, there is one and only one value of x modulo 100 which satisfies
these two inequalities; namely, x=16. So 4^{162}=16 (mod 100).

Now, is it a coincidence that the "key observation" here was about the
20th power, while phi(100)=40 is a multiple of 20? No, because if n|m,
then phi(n)|phi(m).

So, getting back to case (ii) above. What can we say about n and k, in
terms of phi(b)?

Factor b into primes,

   b = p_1^{a_1} * ... * p_r^{a_r}

with p_i a positive prime, p_i = p_j if and only if i=j, and a_i>0.

If (a,p_i)>1 for i=1,...,r, then there exists an s>0 such that
b|a^s. Then the value of n is the smallest such s, and the value of k
is 1. That is, your pair will be (n,1), so that a^r = a^s if and only
if r=s, or r,s>=n.

Otherwise, there will be some primes p_i which divide a, and some that
do not. Let us rewrite b as

   b = p_1^{a_1} * ... * p_s^{a_s}*q_1^{c_1} * ... * q_t^{c_t}

where the p_i and q_j are pairwise distinct positive primes,
a_i,c_i>0, t>=1, s>=1, and p_i|a for each i, (q_j,a)=1 for each j.

Let P = p_1^{a_1}*...*p_s^{a_s}
    Q = q_1^{c_1}*...*q_t^{c_t}

Then we can use the Chinese Remainder theorem, and work with a^N
modulo P and modulo Q. "Modulo P" we are in the case I just finished,
where there is an n_P>0 such that a^{n_P}=0 (mod P), and a^u=a^v (mod
P) if and only if u=v or u,v>= n_P.

The case "Modulo Q", on the other hand, is just the same as case (i)
above: there exists a unique n_Q>0 such that a^u=a^v (mod Q) if and
only if u=v (mod n_Q).

So now you can compute

a^N (mod P) using (n_P,1)
a^N (mod Q) using n_Q.

How often will these cycle modulo PQ=b? To cycle they must cycle both
modulo P and modulo Q. They cycle modulo P as soon as you hit n_P;
then they cycle modulo Q every n_Q. Therefore

a^N = a^M (mod b) if and only if N=M or (N,M>= n_P, and N=M (mod n_Q)).

So the pair in question here is (n_P,n_Q).

You'll note that n_Q | phi(Q) | phi(n). So there ->is<- a relation
between the cycle and phi(n). The "problem" is finding n_P, but that
is not too hard.

In your case we had a=4, b=100; so P=4, Q=25, n_P=1, n_Q=20, and so
the pair in question is (1,20); meaning, 4^N = 4^M (mod 100) if and
only if N=M or (N,M>=1 and N=M (mod 20)), which reduces to just "N=M
(mod 20)".

Hope this helps.

-- 
======================================================================
"It's not denial. I'm just very selective about
 what I accept as reality."
    --- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu