0

Calculate: $3^{1234} $ (mod 17)

We're not suppose to use any "tricks" like the little theorem or anything else alike because we haven't learned that yet just the the definition of modulo.

I tried to do this but it doesn't really help:

$3^{1234}=20^{1234}=2^{1234}10^{1234} $

Thanks in advance.

GinKin
  • 4,429
  • 1
    Why not just notice that $3^{16} \equiv 1 \pmod{17}$ and that $1234 \equiv 2 \pmod{16}$ – M.B. Nov 19 '13 at 20:30

3 Answers3

2

Just start computing: $$3^2\equiv 9\\3^3\equiv 10 \\3^4\equiv 13 \\3^5 \equiv 5 \\3^6\equiv15\\3^7\equiv 11\\ \dots \\3^{16}\equiv 1$$ So now you can just look for the remainder when $1234$ is divided by $16$, which is $2$

Ross Millikan
  • 374,822
2

Doing arithmetic modulo $\;17\;$ all along:

$$3^4=81=-4\;,\;\;3^5=-12=5\;,\;\;3^6=15=-2\;,\;\;3^7=-6\;,\;\;3^8=-18=-1\implies$$

$$\implies 3^{16}=1\;,\;\;\text{and $\;3\;$ is a primitive root modulo}\;17$$

Now:

$$1234=77\cdot 16+2\implies3^{1234}=(3^{16})^{77}\cdot3^2=3^2=9$$

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • Wait how did you find this out: $1234=77\cdot 16+2 $?

    Also, we haven't covered the primitive root.

     – GinKin Nov 19 '13 at 20:47
  • 2
    Well, after I corrected the nonsense I did, I just divided $;1234/16;$ as we were taught in second grade...Forget about the primitive root: it doesn't matter for you now. – DonAntonio Nov 19 '13 at 20:49
1

Alternatively work this out in stages, each time bringing a square inside the brackets:

$3^{1234} \equiv 9^{617} \equiv 9.9^{616} \equiv 9.13^{308} \equiv 9.(-4)^{308} \equiv 9.(-1)^{154} \equiv 9 \bmod 17.$

fretty
  • 11,156
  • 1
  • 26
  • 37