# Euler's Theorm - Homework

Printable View

• December 12th 2006, 09:27 PM
mathlg
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...
• December 13th 2006, 04:11 AM
ThePerfectHacker
Quote:

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,
$45=3^2\cdot 5$
Thus,
$\phi(45)=45\left(1-\frac{1}{3}\right) \left(1-\frac{1}{5}\right)=24$
Thus,
$11^{24}\equiv 1$
Raise both sides to 83th,
$11^{1992}\equiv 1$
Now,
$11^{12}\equiv 1$
Thus, (multiply them through)
$11^{2004}\equiv 1$
• December 13th 2006, 04:17 AM
topsquark
Quote:

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 $a^{\phi (n) } \equiv 1$ (mod n). So we need to know $\phi (45)$. Now, I couldn't find this number on the net, but using my calculator I easily found that $11^6 \equiv 1$ (mod 45).

So
$11^{2004} = 11^{6 \cdot 334} = (11^6)^{334} \equiv 1^{334}$ (mod 45) = 1 (mod 45)

Thus the remainder is 1.

-Dan
• December 13th 2006, 04:21 AM
ThePerfectHacker
Quote:

Originally Posted by topsquark
Now, I couldn't find this number on the net, but using my calculator I easily found that $11^6 \equiv 1$ (mod 45).

What you found was actually the "order of 11". Euler's theorem says that $\phi(n)$ is always AN exponent that makes the statement true. But not necessarily the smallest (the order of the integer). Whenever the order is $\phi(n)$ 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, 07:20 AM
Soroban
Hello, mathlg!

Here's a primitive approach . . .

Quote:

Find the remainder when we divide $11^{2004}$ by $45$

Raising $11$ to consecutive powers, we find that:
. . $11^6 \div 45$ has a remainder of 1.

So we have: . $11^{2004} \:=\:(11^6)^{334} \:\equiv\:1^{334}\!\!\!\!\!\pmod{45}\;\equiv\; 1\!\!\!\!\!\pmod{45}$

Therefore: . $11^{2004} \div 45$ has remainder $1.$

• December 13th 2006, 07:46 AM
topsquark
Quote:

Originally Posted by Soroban
Hello, mathlg!

Here's a primitive approach . . .

Raising $11$ to consecutive powers, we find that:
. . $11^6 \div 45$ has a remainder of 1.

So we have: . $11^{2004} \:=\:(11^6)^{334} \:\equiv\:1^{334}\!\!\!\!\!\pmod{45}\;\equiv\; 1\!\!\!\!\!\pmod{45}$

Therefore: . $11^{2004} \div 45$ has remainder $1.$

(Chuckles) Looks familiar somehow...

-Dan
• December 13th 2006, 07:51 AM
ThePerfectHacker
Did you get Soroban's joke, "a primitive approach".
:)
• December 13th 2006, 08:05 AM
topsquark
Quote:

Originally Posted by ThePerfectHacker
Did you get Soroban's joke, "a primitive approach".
:)

*groans*

-Dan