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"

 
(→‎Best movies for you: new section)
 
(2 intermediate revisions by 2 users not shown)
Line 48: Line 48:
  
 
This method can be further refined using [[Euler's Totient Theorem]].
 
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]

Latest revision as of 00:41, 19 December 2013

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.

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]

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