Index Arithmetic

**Kackie** · January 17th 2009, 07:43 AM

I have been given a question which is

Write down a table of indices to the base 3 modulo 17. Use this to find all the solutions of the congruence
3x^5 = 1 (mod 17)

I've managed to do the table of indices and that's correct but my answer for the solution is x = 5 (mod17) and it says that the answer is x = 10 (mod17). and i dont know where im going wrong?

any help is much appreciated if you can get to the right answer?

Thanks very much

**Soroban** · January 17th 2009, 11:36 AM

Hello, Kackie!

Write down a table of indices to the base 3 modulo 17. . Why?

Use this to find all the solutions of the congruence: . $3x^5 \equiv 1 \text{(mod 17)}$

. . $\begin{array}{cccc} 3^1 & \equiv & 3 & \text{(mod 17)} \\ 3^2 & \equiv & 9 & \text{(mod 17)} \\ 3^3 & \equiv & 10 & \text{(mod 17)} \\ 3^4 & \equiv & 13 & \text{(mod 17)} \\ 3^5 & \equiv & 5 & \text{(mod 17)} \\ 3^6 & \equiv & 15 & \text{(mod 17)} \\ \vdots & & \vdots \end{array}\qquad\hdots$ I don't see how this helps . . .

We have: . $3x^5 \:\equiv\:1\:\text{(mod 17)}$

Multiply both sides by 6: . $18x^5 \:\equiv\:6\:\text{(mod 17)} \quad\Rightarrow\quad x^5 \:\equiv\:6\:\text{(mod 17)} $

At this point, I was forced to try various fifth powers . . .

. . $\begin{array}{ccccccc}1^5 &=& 1 & \equiv & 1 & \text{(mod 17)} \\ 2^5 &=& 32 & \equiv & 15 & \text{(mod 17)} \\ 3^5 &=& 243 &\equiv& 5 & \text{(mod 17)} \\ 4^5 &=&1024 &\equiv& 4 & \text{(mod 17)} \\ 5^5 &=& 3125 &\equiv& 14 & \text{(mod 17)} \\ \vdots & & \vdots && \vdots \\ 10^5 &=& 100,000 &\equiv& 6 & \text{(mod 17)} & \Longleftarrow\;\text{ There!}\end{array}$

Therefore: . $x \:\equiv\:10\:\text{(mod 17)}$

**Kackie** · January 17th 2009, 12:21 PM

ah brilliant!

Thanks very much for your help

**PaulRS** · January 17th 2009, 12:59 PM

Originally Posted by Soroban

I don't see how this helps . . .

I think the idea is to see that 3 is a primitive root - i.e. generator- module 17.

In fact there's a faster way to see that, just note that 17 is a fermat prime and that $17|(3^8+1)$ the rest follows by this post and Euler's Criterion

If there's a solution x, then $x\equiv{3^k}(\bmod.17)$ for some $k\in \mathbb{Z} $

Then: $3x^5\equiv{3^{5k+1}}\equiv{1}(\bmod.17)$ now, since 3 is a primitive root, this happens iff: $16|(5k+1)$

That is $5k=16n-1$ for some $n\in \mathbb{Z}$

Clearly this is possible iff $n\equiv{1}(\bmod.5)$

Hence $5k=16(5m+1)-1=80m+15$ :-> $k=16m+3$

Thus $x\equiv{3^{16m+3}}\equiv{3^3}\equiv{10}(\bmod.17)$ (by Fermat's little Theorem)

So we've found all the possible solutions.

**Soroban** · January 17th 2009, 01:27 PM

Got it . . . Thanks, PaulRS !

Thread: Index Arithmetic

LinkBack

Thread Tools

Display

Index Arithmetic

Similar Math Help Forum Discussions

Index Arithmetic

Index Arithmetic Questions

Arithmetic Progression or Arithmetic Series Problem

index

10-sec vol index

Search Tags