0
$\begingroup$

I'm trying to find the answer to the following: What is the remainder when $9^{2012}$ is divided by $11$?

Apparently, you're supposed to use Fermat's Little Theorem, but I'm not sure how to use it to solve this problem. Can someone please explain this to me?

$\endgroup$

3 Answers 3

3
$\begingroup$

Note that $$9 \equiv -2 \pmod{11} \implies 9^5 \equiv (-2)^5 \pmod{11} \equiv 1\pmod{11}$$ Hence, \begin{align} 9^{2012} & \equiv 9^{2010} \cdot 9^2 \pmod{11}\\ & \equiv \left(9^{2010}\pmod{11} \right)\cdot\left( 9^2 \pmod{11} \right)\\ & \equiv \left(\left(9^5\right)^{402}\pmod{11} \right)\cdot\left( 9^2 \pmod{11} \right)\\ & \equiv \left(1^{402}\pmod{11} \right)\cdot\left( 9^2 \pmod{11} \right)\\ & \equiv 9^2 \pmod{11}\\ & \equiv 81 \pmod{11}\\ & \equiv 4\pmod{11} \end{align}

$\endgroup$
2
$\begingroup$

$9^{2012} = (9^{10})^{200}\cdot 9^{10}\cdot 9^2 \equiv 1\cdot 1\cdot 4 (mod 11) = 4 (mod 11)$

$\endgroup$
1
  • 1
    $\begingroup$ It's a bit unclear why (9^10)^200 and 9^10 are congruent to 1(mod 11). $\endgroup$
    – Jason Chen
    Commented Apr 18, 2014 at 4:34
2
$\begingroup$

The two answers provided are spot on. I will add some more about Fermat's Little Theorem, though. It states that for $p$ a prime, that $a^{p} \equiv a \pmod{p}$. This gives us $a^{p-1} \equiv 1 \pmod{p}$. So we can factor out the coefficients and use rules of exponents to simplify, as LACarguy did above.

User141421 used a corollary to a theorem from Abstract Algebra called Lagrange's Theorem, which follows from Fermat's Little Theorem. Perhaps you have been introduced to the concept of an "order of an element." If you haven't seen groups or Lagrange's Theorem, then don't worry too much about what it says. There is a consequence of it that I talk about a bit later. Even if you haven't formally touched groups, you may still get orders in Number Theory. I did when I took Number Theory. The order of an element $a$ in a group (in this case, $\mathbb{Z}_{p}$ excluding $0$ over multiplication) is the smallest natural number $n$ such that $a^{n} = 1$. So the order of $9$ in $\mathbb{Z}_{11}$ is $5$.

The corollary to Lagrange's Theorem gives us that if $9^{n} \equiv 1 \pmod{11}$, then $5|n$. More generally, any exponent that brings an element $a$ to its identity is a multiple of $ord(a)$ (the order of $a$). This makes sense in terms of rules of exponents, right? If $ord(9) = 5$ (ie., $9^{5} \equiv 1 \pmod{11}$) and Fermat's Little Theorem gives us $9^{10} \equiv 1 \pmod{11}$, we have $5|10$, right? So that's why user141421 could do some additional factoring up front.

Hopefully this clears up the machinery some. Please let me know if I can clarify.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .