Results 1 to 5 of 5

Thread: 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
    12,028
    Thanks
    848
    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: .$\displaystyle 3x^5 \equiv 1 \text{(mod 17)}$

    . . $\displaystyle \begin{array}{cccc}
    3^1 & \equiv & 3 & \text{(mod 17)} \\
    3^2 & \equiv & 9 & \text{(mod 17)} \\
    3^3 & \equiv & 10 & \text{(mod 17)} \\
    3^4 & \equiv & 13 & \text{(mod 17)} \\
    3^5 & \equiv & 5 & \text{(mod 17)} \\
    3^6 & \equiv & 15 & \text{(mod 17)} \\
    \vdots & & \vdots \end{array}\qquad\hdots$
    I don't see how this helps . . .



    We have: .$\displaystyle 3x^5 \:\equiv\:1\:\text{(mod 17)} $

    Multiply both sides by 6: .$\displaystyle 18x^5 \:\equiv\:6\:\text{(mod 17)} \quad\Rightarrow\quad x^5 \:\equiv\:6\:\text{(mod 17)}
    $


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

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


    Therefore: .$\displaystyle 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
    $\displaystyle 17|(3^8+1)$ the rest follows by this post and Euler's Criterion

    If there's a solution x, then $\displaystyle x\equiv{3^k}(\bmod.17)$ for some $\displaystyle k\in
    \mathbb{Z}
    $

    Then: $\displaystyle 3x^5\equiv{3^{5k+1}}\equiv{1}(\bmod.17)$ now, since 3 is a primitive root, this happens iff: $\displaystyle 16|(5k+1)$

    That is $\displaystyle 5k=16n-1$ for some $\displaystyle n\in \mathbb{Z}$

    Clearly this is possible iff $\displaystyle n\equiv{1}(\bmod.5)$

    Hence $\displaystyle 5k=16(5m+1)-1=80m+15$ :-> $\displaystyle k=16m+3$


    Thus $\displaystyle 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
    12,028
    Thanks
    848

    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: Jul 6th 2011, 11:57 PM
  2. Index Arithmetic Questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 10th 2010, 04:54 PM
  3. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Oct 8th 2009, 12:36 AM
  4. index
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Oct 11th 2008, 03:36 PM
  5. 10-sec vol index
    Posted in the Statistics Forum
    Replies: 0
    Last Post: Jun 16th 2008, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum