Difference between revisions of "Talk:Modular arithmetic/Intermediate"
AnthonyRids (talk | contribs) (→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 01: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 -- namely,
-- that is congruent to
mod
. What if we aren't this lucky? Suppose we want to solve the following problem:
What are the tens and units digits of ?
Again, we will solve this problem by computing modulo
. The first few powers of
mod
are
This time, no pattern jumps out at us. Is there a way we can find the power of
mod
without taking this list all the way out to the
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 mod
, we write only the powers
, where
is a power of
. We have the following (all congruences are modulo
):
(Observe that this process yields a pattern of its own, if we carry it out far enough!)
Now, observe that, like any positive integer, can be written as a sum of powers of two:
We can now use this powers-of-two expansion to compute :
So the tens and units digits of are
and
, respectively.
We can use this method to compute modulo
, for any integers
and
, with
. The beauty of this algorithm is that the process takes, at most, approximately
steps -- at most
steps to compute the values
modulo
for
a power of two less than
, and at most
steps to multiply the appropriate powers of
according to the binary representation of
.
This method can be further refined using Euler's Totient Theorem.
Two suggestions
Why is 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 instead of
, the first one is already used for
-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]