Thread: Euler'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...

Originally Posted by mathlg

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

Note,

Thus,

Thus,

Raise both sides to 83th,

Now,

Thus, (multiply them through)

Originally Posted by mathlg

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

Euler's theorem says that (mod n). So we need to know . Now, I couldn't find this number on the net, but using my calculator I easily found that (mod 45).

So
(mod 45) = 1 (mod 45)

Thus the remainder is 1.

-Dan

Originally Posted by topsquark

Now, I couldn't find this number on the net, but using my calculator I easily found that (mod 45).

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

Hello, mathlg!

Here's a primitive approach . . .

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

Originally Posted by Soroban

Hello, mathlg!

Here's a primitive approach . . .


Raising to consecutive powers, we find that:
. . has a remainder of 1.

So we have: . 11^6)^{334} \:\equiv\:1^{334}\!\!\!\!\!\pmod{45}\;\equiv\; 1\!\!\!\!\!\pmod{45}" alt="11^{2004} \:=\11^6)^{334} \:\equiv\:1^{334}\!\!\!\!\!\pmod{45}\;\equiv\; 1\!\!\!\!\!\pmod{45}" />


Therefore: . has remainder

(Chuckles) Looks familiar somehow...

-Dan

Did you get Soroban's joke, "a primitive approach".

Originally Posted by ThePerfectHacker

Did you get Soroban's joke, "a primitive approach".

*groans*

-Dan