1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

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

    shmoe

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number theory help
  1. Number theory help (Replies: 1)

  2. Number Theory Help (Replies: 40)

  3. Number theory help (Replies: 3)

  4. Number theory help (Replies: 26)

Loading...