Solution:

If x has order 2, then x2 = 1 (mod p). Since the only solutions are 1 and p _ 1, and 1 has order 1, the only element of order 2 is p _ 1.

Solution:

38 = 6561 = 17(385) + 16 = 16 = _1 (mod 17).

Since φ(17) = 16, we know that the order of 3 must be a divisor of 16, hence one of 1, 2, 4, 8, or 16. Since 38 /= 1  (mod 17), we know that the order cannot be 8, nor can it be a divisor of 8. Hence 3 must have order 16, and so it is a primitive root.

Solution:

(a) Since 83 is prime φ(83) = 82. Thus the only possible orders are 1, 2, 41 and 82.

Since 23 is not equal to ±1, (and 83 is prime) the only possible orders are 41 and 82.

Testing 41.

232 = 31    (mod 83)

234 = 312 = 48    (mod 83)

238 = 482 = 63    (mod 83)

2316 = 632 = 68    (mod 83)

2332 = 682 = 59    (mod 83)

Hence

2341 = 2332 . 238 . 23 = 59 . 63 . 23 = 1 (mod 83)

Hence the order is 41.

(b) Since the only possible orders of 83 are 1, 2, 41 and 82, the first two only occurs

for 1 and 82, we just need to find an element from 2 to 79 for which 241 /= 1 (mod 83).

Checking 2

28 = 7 (mod 83), thus 241 = 75 . 2 = 33614 = 82.

Hence 2 has order 82 and thus is a primitive root modulo 83.

Solution:

Since a has order t, we know that at = 1 (mod m).

So aat − 1 = 1  (mod m), showing a = at − 1 (mod m).

The order of at − 1 is = t.

So the order of a is the same as the order of a.