# Thread: Euler's Theorm - Homework

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

2. 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,
$\displaystyle 45=3^2\cdot 5$
Thus,
$\displaystyle \phi(45)=45\left(1-\frac{1}{3}\right) \left(1-\frac{1}{5}\right)=24$
Thus,
$\displaystyle 11^{24}\equiv 1$
Raise both sides to 83th,
$\displaystyle 11^{1992}\equiv 1$
Now,
$\displaystyle 11^{12}\equiv 1$
Thus, (multiply them through)
$\displaystyle 11^{2004}\equiv 1$

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

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

Thus the remainder is 1.

-Dan

4. Originally Posted by topsquark
Now, I couldn't find this number on the net, but using my calculator I easily found that $\displaystyle 11^6 \equiv 1$ (mod 45).
What you found was actually the "order of 11". Euler's theorem says that $\displaystyle \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 $\displaystyle \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).

5. Hello, mathlg!

Here's a primitive approach . . .

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

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

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

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

6. Originally Posted by Soroban
Hello, mathlg!

Here's a primitive approach . . .

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

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

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

(Chuckles) Looks familiar somehow...

-Dan

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

8. Originally Posted by ThePerfectHacker
Did you get Soroban's joke, "a primitive approach".
*groans*

-Dan