# Homework Help: Number theory help

1. Mar 28, 2006

### buzzmath

Can anyone help me with this problem?

Find all solutions of the following congruence 3x^5≡1(mod 23)

This is what I have so far
I know 5 is a primitive root and I made a table of indices modulo 23 with respect to 5
then
Φ(23)=22
Ind5(3x5)≡ind5(1)=22(mod 22)
Ind5(3x5)≡ind5(3) + ind5(x5)≡16 + 5ind5(x)(mod22)
16+5ind5(x)≡22(mod22)
5ind5(x)≡6(mod22)
I'm stuck here because I'm not really sure how to get rid of the 5 on the left side or if I even have to.

Thanks

Last edited: Mar 28, 2006
2. Mar 28, 2006

### buzzmath

where ind5(x) is index of x to the base 5

3. Mar 29, 2006

### matt grime

Why don'y you just work out 3x^5 for all x in 1,..,22? (of course you can omit many of these since they can't be solutions). If you had magma handy it could be done by

for i in [1..22] do
print "x=",i,"3x^5=", Modexp(i,5,23);
end for;

for python:

R=range(1,22)
for x in R:
... print x, 3*(x**5)%23
...

of course this is a silly way to do it as it doesn't teach you much.

Better, find 3^(-1) mod 23 (euclid)
find a fifth root of this number (you know what it is as a power of 5, right?) now multiply by all the 5th roots of unity, just like you'd do in the complex number case.

4. Mar 29, 2006

### shmoe

5 and 22 are relatively prime. Find the multiplicative inverse of 5 mod 22 and multiply.

5. Mar 29, 2006

### neurocomp2003

ummm use linear Congruence Th'm..if your already onto primitive roots you should have learned that theorem already. When you've solved the LinCong...then look back at your Index table and get the number your actually looking for.