4
$\begingroup$

Compute $3^{2003}\pmod {99}$ by hand?

It can be computed easily by evaluating $3^{2003}$, but it sounds stupid. Is there a way to compute it by hand?

$\endgroup$
1
  • 1
    $\begingroup$ $3^{2003}\equiv 0\pmod 9$ and $3^{2003}\equiv 3^3\equiv 5\pmod {11}$. Solve with Chinese remainder theorem. $\endgroup$ Nov 2, 2014 at 17:24

4 Answers 4

5
$\begingroup$

Calculate $3^2, 3^3, 3^4, 3^5, 3^6, 3^7$ modulo $99$, i.e. reduce at each step. For example $3^4=729\equiv 36\pmod{ 99}$. Now $3^5=3\cdot 3^4\equiv 3\cdot 36\equiv 45$. You will find that $$9=3^2\equiv 3^7\pmod{99}$$ Hence $$3^{2+5k}\equiv 9\pmod{99}$$ for all $k\in \mathbb{Z}^{\ge 0}$. Hopefully you can finish the problem from here.

$\endgroup$
3
  • $\begingroup$ Does this method have a name? $\endgroup$
    – Fan
    Nov 2, 2014 at 17:19
  • $\begingroup$ 729 is not congruence to 81 mod 99 $\endgroup$
    – Fan
    Nov 2, 2014 at 17:21
  • $\begingroup$ @Fan, thanks, fixed. $\endgroup$
    – vadim123
    Nov 2, 2014 at 19:19
2
$\begingroup$

I would calculate separately modulo $9$ and $11$ and put the pieces together at the end.

Modulo $9$ is trivial, we get $0$.

Note that $3^5\equiv 1\pmod{11}$, so $3^{2000}\equiv 1\pmod{11}$, and therefore $3^{2003}\equiv 3^3\equiv 27\pmod{11}$. This is already congruent to $0$ modulo $9$, so we are finished.

$\endgroup$
2
  • $\begingroup$ It actually takes computation to show $3^5\equiv 1$, but it is easy to use $3^{10}\equiv 1$... $\endgroup$ Nov 2, 2014 at 17:28
  • $\begingroup$ I was avoiding the Fermat theorem for no good reason apart from keeping the mood more computational. $\endgroup$ Nov 2, 2014 at 17:57
2
$\begingroup$

Note that $3^n$ is divisible by $9$ for $n\ge 2$ so the outcome will be $0, 9, 18, 27, \dots 90$ - eleven different answers, which have different residues modulo $11$.

Now by little Fermat $3^{10}\equiv 1$ mod $11$, so that $3^{2003}\equiv 3^3=27 \equiv 5$ mod $11$.

I will leave you to work out the final answer.

$\endgroup$
0
$\begingroup$

As $(3^{2003},99)=9,$

we can start with $3^{2003}/9\pmod{99/9}$ i.e., $3^{2001}\pmod{11}$

As $(3,11)=1,$ using Fermat's Little Theorem, $3^{10}\equiv1\pmod{11}$ and $2001\equiv1\pmod{10}$

$\implies3^{2001}\equiv3^1\pmod{11}$

Using property$\#9$ of this, $9\cdot3^{2001}\equiv9\cdot3^1\pmod{9\cdot11}\equiv?$

$\endgroup$

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