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

- Dec 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... - Dec 13th 2006, 05:11 AMThePerfectHacker
- Dec 13th 2006, 05:17 AMtopsquark
- Dec 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).

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

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

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