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

[Kitty Kat]

Homework Statement

So basically for n ∈ {1, ... , 16}
Find the lowest t to satisfy n^t ≡ 1 (mod 17)

Homework 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}

The Attempt at a Solution

n = 1
1¹ ≡ 1 (mod 17)
t = 1

n = 2
I checked 2² and 2⁴ by hand and they weren't congruent to 1 (mod 17).
2⁸ = 64 ≡ 1 (mod 17)
t = 8

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

n = 5
5¹⁶ = (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:

Thanks!

 

[mfb]

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.