Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Talk:Modular arithmetic/Intermediate"

 
(No difference)

Revision as of 17:03, 11 July 2006

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 $7$ -- namely, $7^4$ -- that is congruent to $1$ mod $100$. What if we aren't this lucky? Suppose we want to solve the following problem:

What are the tens and units digits of $13^{404}$?

Again, we will solve this problem by computing $13^{404}$ modulo $100$. The first few powers of $13$ mod $100$ are

$13, 69, 97, 61, 93, \ldots$

This time, no pattern jumps out at us. Is there a way we can find the $404^{th}$ power of $13$ mod $100$ without taking this list all the way out to the $404^{th}$ 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 $13$ mod $100$, we write only the powers $13^k$, where $k$ is a power of $2$. We have the following (all congruences are modulo $100$):

$\displaystyle 13^1 = 13$

$13^2 \equiv 69$

$13^4 \equiv 69^2 \equiv 61$

$13^8 \equiv 61^2 \equiv 21$

$13^{16} \equiv 21^2 \equiv 41$

$13^{32} \equiv 41^2 \equiv 81$

$13^{64} \equiv 81^2 \equiv 61$

$13^{128} \equiv 61^2 \equiv 21$

$13^{256} \equiv 21^2 \equiv 41$

(Observe that this process yields a pattern of its own, if we carry it out far enough!)

Now, observe that, like any positive integer, $404$ can be written as a sum of powers of two:

$404 = 256 + 128 + 16 + 4$

We can now use this powers-of-two expansion to compute $\overline{13}^{404}$:

$13^{404} = 13^{256} \cdot 13^{128} \cdot 13^{16} \cdot 13^4 \equiv 41 \cdot 21 \cdot 41 \cdot 61 \equiv 61.$

So the tens and units digits of $13^{404}$ are $6$ and $1$, respectively.

We can use this method to compute $M^e$ modulo $n$, for any integers $M$ and $e$, with $e > 0$. The beauty of this algorithm is that the process takes, at most, approximately $2 \log_2 e$ steps -- at most $\log_2 e$ steps to compute the values $M^k$ modulo $n$ for $k$ a power of two less than $e$, and at most $\log_2 e$ steps to multiply the appropriate powers of $M$ according to the binary representation of $e$.

This method can be further refined using Euler's Totient Theorem.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Talk:Modular_arithmetic/Intermediate&oldid=7370"