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

I got this question in an interview.

I'm obligated to ask this question of Number Theory in portion More Number Theory of Cryptograph & Network Security

Answer 1

Right option is (b) 20

To explain: 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.