Talk:Modular arithmetic/Intermediate

< Talk:Modular arithmetic
Revision as of 13:34, 27 September 2007 by ZetaX (talk | contribs) (New section: Two suggestions)

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.

Two suggestions

Why is $n>0$ assumed here, it's never needed. It's in general better to neglect this restriction after one has mastered the first steps (and as this is Intermediate, I would assume this to be true).

And I'm still strongly against using $\mathbb Z_n$ instead of $\mathbb Z / n \mathbb Z$, the first one is already used for $n$-adic integers and rarely seen in non-olympiad books.

But as both is some kind of disputed, I didnÄt edit it untill now.

Invalid username
Login to AoPS