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

- Dec 13th 2006, 07:20 AMSoroban
Hello, mathlg!

Here's a primitive approach . . .

Quote:

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

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

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