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!

Finding the orders of 1, 2, ... , 16 (mod 17)

  1. Feb 25, 2017 #1
    1. The problem statement, all variables and given/known data
    09a665408f471be471c142d306160d84.png
    So basically for n ∈ {1, ... , 16}
    Find the lowest t to satisfy nt ≡ 1 (mod 17)

    2. Relevant equations
    Euler's Theorem tells us that the order, t, must be a divisor of φ(17), which is Euler's Phi Function.
    φ(17) = 16
    t ∈ {1, 2, 4, 8, 16}

    3. The attempt at a solution
    n = 1
    11 ≡ 1 (mod 17)
    t = 1

    n = 2
    I checked 22 and 24 by hand and they weren't congruent to 1 (mod 17).
    28 = 64 ≡ 1 (mod 17)
    t = 8

    n = 4
    I checked 42 by hand and it wasn't congruent to 1 (mod 17).
    44 = 256 ≡ 1 (mod 17)
    t = 4

    n = 5
    516 = (16 * 16) ≡ 1 (mod 17)
    t = 16

    My answers seem to be quite different from the answer key, and I'm not sure why.
    Also, my textbook's answer key implies that only 1, 2, 4, 5, 7, and 8 actually have a solution; so is there a quick way to verify for which n there is a solution? (Other than checking all the values of t, and finding that none of them satisfy the congruence.)

    I know that gcd(n, m) = 1 will have a solution, but 17 is a prime so gcd(n, 17) for all n {1 ... 16} will be 1, which should imply that all n will have a solution?

    Answer key:
    e505ede26c437928a083454b9e71294e.png

    Thanks!
     
    Last edited: Feb 25, 2017
  2. jcsd
  3. Feb 26, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The answer of the book doesn't make sense, so I did reverse engineering:
    If 8 has order 2, then 64=1 mod X, which means X is a divisor of 63 = 7*9. We get the same condition for "2 has order 6" and "4 has order 3".
    If 7 has order 3, then X is a divisor of 342 = 2*9*19
    If 5 has order 6, then X is a divisor of 15624 = 8*9*7*31.
    At this point it gets clear that the book considers X=9.
    φ(9) = 6
    3 and 6 don't have an order as they share the factor 3 with X=9, all other numbers smaller than 9 are covered in the book's answer. The book simply answers a different question.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Finding the orders of 1, 2, ... , 16 (mod 17)
Loading...