- #1

Kitty Kat

- 13

- 0

## 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}≡ 1 (mod 17)

t = 1

n = 2

I checked 2

^{2}and 2

^{4}by hand and they weren't congruent to 1 (mod 17).

2

^{8}= 64 ≡ 1 (mod 17)

t = 8

n = 4

I checked 4

^{2}by hand and it wasn't congruent to 1 (mod 17).

4

^{4}= 256 ≡ 1 (mod 17)

t = 4

n = 5

5

^{16}= (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: