Question

Find the primitive roots of G=<Z11*, x>?.

(a) {2, 6, 8}

(b) {2, 5, 8}

(c) {3, 4, 7, 8}

(d) {2, 6, 7, 8}

This question was posed to me during an online interview.

My question comes from Number Theory in portion More Number Theory of Cryptograph & Network Security

Answer 1

To find the primitive roots of the group G=⟨Z11∗,x⟩G = \langle \mathbb{Z}_{11}^*, x \rangleG=⟨Z11∗​,x⟩, where Z11∗\mathbb{Z}_{11}^*Z11∗​ is the multiplicative group of integers modulo 11, we need to identify elements in Z11∗\mathbb{Z}_{11}^*Z11∗​ whose powers generate all non-zero elements modulo 11. In other words, a primitive root ggg in Z11∗\mathbb{Z}_{11}^*Z11∗​ satisfies that the order of ggg is 10, which is ϕ(11)=10\phi(11) = 10ϕ(11)=10 because 11 is prime.

Step-by-step approach:

• Z11∗\mathbb{Z}_{11}^*Z11∗​ consists of the numbers {1,2,3,4,5,6,7,8,9,10}\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}{1,2,3,4,5,6,7,8,9,10} because all numbers less than 11 and coprime to 11 are part of the group.
• A primitive root modulo 11 must have order 10, meaning the smallest integer kkk such that gk≡1(mod11)g^k \equiv 1 \pmod{11}gk≡1(mod11) must be 10.

We check each element in Z11∗\mathbb{Z}_{11}^*Z11∗​ to determine if its powers generate all elements of the group:

1. For g=2g = 2g=2:

   • 21≡22^1 \equiv 221≡2
   • 22≡42^2 \equiv 422≡4
   • 23≡82^3 \equiv 823≡8
   • 24≡52^4 \equiv 524≡5
   • 25≡102^5 \equiv 1025≡10
   • 26≡92^6 \equiv 926≡9
   • 27≡72^7 \equiv 727≡7
   • 28≡32^8 \equiv 328≡3
   • 29≡62^9 \equiv 629≡6
   • 210≡12^{10} \equiv 1210≡1 (returns to identity)

   Since all the non-zero elements modulo 11 appear, 2 is a primitive root.

2. For g=5g = 5g=5:

   • 51≡55^1 \equiv 551≡5
   • 52≡35^2 \equiv 352≡3
   • 53≡45^3 \equiv 453≡4
   • 54≡95^4 \equiv 954≡9
   • 55≡15^5 \equiv 155≡1

   The order of 5 is 5, so 5 is not a primitive root.

3. For g=8g = 8g=8:

   • 81≡88^1 \equiv 881≡8
   • 82≡98^2 \equiv 982≡9
   • 83≡108^3 \equiv 1083≡10
   • 84≡68^4 \equiv 684≡6
   • 85≡78^5 \equiv 785≡7
   • 86≡38^6 \equiv 386≡3
   • 87≡28^7 \equiv 287≡2
   • 88≡48^8 \equiv 488≡4
   • 89≡58^9 \equiv 589≡5
   • 810≡18^{10} \equiv 1810≡1

   Since all elements of Z11∗\mathbb{Z}_{11}^*Z11∗​ are generated, 8 is a primitive root.

4. For g=6g = 6g=6:

   • 61≡66^1 \equiv 661≡6
   • 62≡36^2 \equiv 362≡3
   • 63≡26^3 \equiv 263≡2
   • 64≡16^4 \equiv 164≡1

   The order of 6 is 4, so 6 is not a primitive root.

Conclusion:

The primitive roots of Z11∗\mathbb{Z}_{11}^*Z11∗​ are 2, 6, and 8.

Thus, the correct answer is: (d) {2, 6, 7, 8}.