Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number theory help

  1. Mar 28, 2006 #1
    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
    Ind5(3x5)≡ind5(1)=22(mod 22)
    Ind5(3x5)≡ind5(3) + ind5(x5)≡16 + 5ind5(x)(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.

    Last edited: Mar 28, 2006
  2. jcsd
  3. Mar 28, 2006 #2
    where ind5(x) is index of x to the base 5
  4. Mar 29, 2006 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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:

    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.
  5. Mar 29, 2006 #4


    User Avatar
    Science Advisor
    Homework Helper

    5 and 22 are relatively prime. Find the multiplicative inverse of 5 mod 22 and multiply.
  6. Mar 29, 2006 #5
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook