# Thread: [SOLVED] Solutions of Congruences

1. ## [SOLVED] Solutions of Congruences

Problem: Find all the solutions of the following congruence:
$3x^5 \equiv 1 ( \mod{23} )$

Since 5 is a primitive root of 23. I constructed an index table modulo 23 for the p.r. 5.

Number: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Index : 22, 2, 16, 4, 1, 18, 19, 6, 10, 3, 9, 20, 14, 21, 17, 8, 7, 12, 15, 5, 13, 11

Now, since $3x^5 \equiv 1 ( \pmod{23} )$ can be rewritten in indices as

$ind_{5}3+5ind_{5}x \equiv ind_{5}1 \pmod{22}$

By looking at the index table, we get

$16 + 5ind_{5}x \equiv 22 \pmod{22}$

Let $y = 5ind_{5}x$,

we get

$16 + 5y \equiv 22 \pmod{22}$

Then, subtract 16 from both sides

$5y \equiv 6 \pmod{22}$

From here I am stuck. I believe I am supposed to multiply 5 by some number to get 1 mod 22. From here I can solve for y and then for x.

Any help is greatly appreciated. Thank you.

2. I would start by saying that $3\times8=24\equiv1\!\!\!\pmod{23}$. Then if you multiply both sides of the congruence $3x^5\equiv1\!\!\!\pmod{23}$ by 8, it becomes $x^5\equiv8\!\!\!\pmod{23}$, and you can read off the answer for x directly from the index table.

3. Opalg, I understand all of the parts until you said the answer can be read directly off the index table.

The only connection I get is this
$5ind_{5}x \equiv 6 \pmod{22}$ and
$x^5 \equiv 8 \pmod{23}$

4. Originally Posted by Paperwings
Opalg, I understand all of the parts until you said the answer can be read directly off the index table.

The only connection I get is this
$5ind_{5}x \equiv 6 \pmod{22}$ and
$x^5 \equiv 8 \pmod{23}$
Pay no attention to my comment. I was being stupid. I was trying to solve $5^x\equiv8\!\!\!\pmod{23}$ rather than $x^5\equiv8\!\!\!\pmod{23}$.

But if it's any help, I notice that $5\times 10 = 50\equiv6\!\!\!\pmod{22}$, so you can take y=10.

Edit ... and from the index table, that gives x=9, which works!! $3\times9^5 = 177147 = 1 + 23\times7702$

5. Ah, thank you. I also got y = 10 and subsequently 9 although I used "guess-and-check"