View source for Talk:Modular arithmetic/Intermediate

The following material can be reworded and incorporated into this article:--[[User:MCrawford|MCrawford]] 18:54, 30 June 2006 (EDT)

==== A General Algorithm ====

In the example above, we were fortunate to find a power of <math>7</math> -- namely, <math>7^4</math> -- that is congruent to <math>1</math> mod <math>100</math>.  What if we aren't this lucky?  Suppose we want to solve the following problem:

''What are the tens and units digits of <math>13^{404}</math>?''

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

<math>13, 69, 97, 61, 93, \ldots</math>

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

<math>\displaystyle 13^1 = 13</math>

<math>13^2 \equiv 69</math>

<math>13^4 \equiv 69^2 \equiv 61</math>

<math>13^8 \equiv 61^2 \equiv 21</math>

<math>13^{16} \equiv 21^2 \equiv 41</math>

<math>13^{32} \equiv 41^2 \equiv 81</math>

<math>13^{64} \equiv 81^2 \equiv 61</math>

<math>13^{128} \equiv 61^2 \equiv 21</math>

<math>13^{256} \equiv 21^2 \equiv 41</math>

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

Now, observe that, like any positive integer, <math>404</math> can be written as a sum of powers of two:

<math>404 = 256 + 128 + 16 + 4</math>

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

<math>13^{404} = 13^{256} \cdot 13^{128} \cdot 13^{16} \cdot 13^4 \equiv 41 \cdot 21 \cdot 41 \cdot 61 \equiv 61.</math>

So the tens and units digits of <math>13^{404}</math> are <math>6</math> and <math>1</math>, respectively.

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

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

== Two suggestions ==

Why is <math>n>0</math> 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 <math>\mathbb Z_n</math> instead of <math>\mathbb Z / n \mathbb Z</math>, the first one is already used for <math>n</math>-adic integers and rarely seen in non-olympiad books.

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

== Best movies for you ==

Welcome back! On our site you can download any movie. All new movies come at us very quickly. Collection of our site is constantly updated, it presents films of various genres. Much attention is paid to the classics of cinema and art house, and certainly novelties. And most importantly - you can download a movie in one file at high speed. Happy viewing! [url=http://video-good.pp.ua/]Best movies for you[/url]