Talk:Modular arithmetic/Intermediate

From AoPSWiki

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.

Personal tools

Navigation

Search

Toolbox

Talk:Modular arithmetic/Intermediate

From AoPSWiki

A General Algorithm

Two suggestions