1. ## Index Arithmetic

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

2. 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: .$\displaystyle 3x^5 \equiv 1 \text{(mod 17)}$

. . $\displaystyle \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: .$\displaystyle 3x^5 \:\equiv\:1\:\text{(mod 17)}$

Multiply both sides by 6: .$\displaystyle 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 . . .

. . $\displaystyle \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: .$\displaystyle x \:\equiv\:10\:\text{(mod 17)}$

3. ah brilliant!

Thanks very much for your help

4. 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
$\displaystyle 17|(3^8+1)$ the rest follows by this post and Euler's Criterion

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

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

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

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

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

Thus $\displaystyle 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.

5. Got it . . . Thanks, PaulRS !