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: . $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)} \\
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)}$

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
$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.

5. Got it . . . Thanks, PaulRS !