# Difference between revisions of "Talk:Modular arithmetic/Intermediate"

(New section: Two suggestions) |
|||

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. |

## Revision as of 13:34, 27 September 2007

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.