Need some help with this problem

Question:

Find the remainder when we divide 11^2004 by 45

Not sure what to do on this problem...

Printable View

- December 12th 2006, 10:27 PMmathlgEuler's Theorm - Homework
Need some help with this problem

Question:

Find the remainder when we divide 11^2004 by 45

Not sure what to do on this problem... - December 13th 2006, 05:11 AMThePerfectHacker
- December 13th 2006, 05:17 AMtopsquark
- December 13th 2006, 05:21 AMThePerfectHacker
What you found was actually the "order of 11". Euler's theorem says that is always AN exponent that makes the statement true. But not necessarily the smallest (the order of the integer). Whenever the order is that is called a "primitive roots" (in an algebraic way of sense we can think of this a generator of the cyclic group). The number 45 has not primitive roots, as a problem solved by Gauss. It is not one of the standard forms for which primitive roots exists. (primes, power of primes, and doubling power of primes).

- December 13th 2006, 08:20 AMSoroban
Hello, mathlg!

Here's a primitive approach . . .

Quote:

Find the remainder when we divide by

Raising to consecutive powers, we find that:

. . has a remainder of 1.

So we have: .

Therefore: . has remainder

- December 13th 2006, 08:46 AMtopsquark
- December 13th 2006, 08:51 AMThePerfectHacker
Did you get Soroban's joke, "a primitive approach".

:) - December 13th 2006, 09:05 AMtopsquark