Results 1 to 5 of 5

Math Help - Index Arithmetic

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,864
    Thanks
    744
    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}<br />
3^1 & \equiv & 3 & \text{(mod 17)} \\<br />
3^2 & \equiv & 9 & \text{(mod 17)} \\<br />
3^3 & \equiv & 10 & \text{(mod 17)} \\<br />
3^4 & \equiv & 13 & \text{(mod 17)} \\<br />
3^5 & \equiv & 5 & \text{(mod 17)} \\<br />
3^6 & \equiv & 15 & \text{(mod 17)} \\<br />
\vdots & & \vdots \end{array}\qquad\hdots
    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)} <br />


    At this point, I was forced to try various fifth powers . . .

    . . \begin{array}{ccccccc}1^5 &=& 1 & \equiv & 1 & \text{(mod 17)} \\<br />
2^5 &=& 32 & \equiv & 15 & \text{(mod 17)} \\<br />
3^5 &=& 243 &\equiv& 5 & \text{(mod 17)} \\<br />
4^5 &=&1024 &\equiv& 4 & \text{(mod 17)} \\<br />
5^5 &=& 3125 &\equiv& 14 & \text{(mod 17)} \\<br />
\vdots & & \vdots && \vdots \\<br />
10^5 &=& 100,000 &\equiv& 6 & \text{(mod 17)} & \Longleftarrow\;\text{ There!}\end{array}


    Therefore: . x \:\equiv\:10\:\text{(mod 17)}


    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    2
    ah brilliant!

    Thanks very much for your help
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote 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 <br />
\mathbb{Z}<br />

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,864
    Thanks
    744

    Got it . . . Thanks, PaulRS !

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Index Arithmetic
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 7th 2011, 12:57 AM
  2. Index Arithmetic Questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 10th 2010, 05:54 PM
  3. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 8th 2009, 01:36 AM
  4. index
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 11th 2008, 04:36 PM
  5. 10-sec vol index
    Posted in the Statistics Forum
    Replies: 0
    Last Post: June 16th 2008, 02:47 PM

Search Tags


/mathhelpforum @mathhelpforum