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