- #1
Kitty Kat
- 13
- 0
Homework Statement
So basically for n ∈ {1, ... , 16}
Find the lowest t to satisfy nt ≡ 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
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:
Thanks!
Last edited: