Talk:Modular arithmetic/Intermediate
The following material can be reworded and incorporated into this article:--MCrawford 18:54, 30 June 2006 (EDT)
A General Algorithm
In the example above, we were fortunate to find a power of -- namely,
-- that is congruent to
mod
. What if we aren't this lucky? Suppose we want to solve the following problem:
What are the tens and units digits of ?
Again, we will solve this problem by computing modulo
. The first few powers of
mod
are
This time, no pattern jumps out at us. Is there a way we can find the power of
mod
without taking this list all the way out to the
term -- or even without patiently waiting for the list to yield a pattern?
Suppose we condense the list we started above; and instead of writing down all powers of mod
, we write only the powers
, where
is a power of
. We have the following (all congruences are modulo
):
(Observe that this process yields a pattern of its own, if we carry it out far enough!)
Now, observe that, like any positive integer, can be written as a sum of powers of two:
We can now use this powers-of-two expansion to compute :
So the tens and units digits of are
and
, respectively.
We can use this method to compute modulo
, for any integers
and
, with
. The beauty of this algorithm is that the process takes, at most, approximately
steps -- at most
steps to compute the values
modulo
for
a power of two less than
, and at most
steps to multiply the appropriate powers of
according to the binary representation of
.
This method can be further refined using Euler's Totient Theorem.