Question

Which among the following values:  17, 20, 38, and 50, does not have primitive roots in the group G = <Zn∗, ×>?

(a) 17

(b) 20

(c) 38

(d) 50

This question was addressed to me in an online interview.

This intriguing question comes from Overview in portion Cryptography Overview, TCP/IP and Communication Networks of Cryptograph & Network Security

Answer 1

Correct option is (b) 20

Explanation: The group G = <Zn*, ×> has primitive roots only if n is 2, 4, pt, or 2pt

‘p’ is an odd prime and‘t’ is an integer.

G = <Z17∗, ×> has primitive roots, 17 is a prime.

G = <Z20∗, ×> has no primitive roots.

G = <Z38∗, ×> has primitive roots, 38 = 2 × 19 prime.

G = <Z50∗, ×> has primitive roots, 50 = 2 × 52 and 5 is a prime.