Question

Find a primitive root, for all positive integral m, modulo each integer below.

(a) 7^m (Hint: Using Corollary 5.15, find a common primitive root r modulo 7 and 7²• The proof of Proposition 5.17 then guarantees that r is a primitive root modulo 7² for all positive integral m.)

(b) 11^m

(c) 13^m

(d) 17^m

Answer 1

Solution:

A number g is a primitive root modulo n if every number co-prime to n is congruent to a power of g modulo n

(a).

Modulo 7

3^0 1 mod 7

3^1 3 mod 7

3^2 2 mod 7

3^3 6 mod 7

3^4 4 mod 7

3^5 5 mod 7

3^6 1 mod 7

Here we get all the possible results 1,2,3,4,5,6 [Numbers co-prime to 7]

Therefore 3 is a primitive root modulo 7

(b).

Modulo 11

2^0 1 mod 11

2^1 2 mod 11

2^2 4 mod 11

2^3 8 mod 11

2^4 5 mod 11

2^5 10 mod 11

2^6 9 mod 11

2^7 7 mod 11

2^8 3 mod 11

2^9 6 mod 11

2^10 1 mod 11

Here we get all the possible results 1,2,3,4,5,6,7,8,9,10 [Numbers co-prime to 11]

Therefore number 2 is primitive root modulo 11

(c).

Modulo 13

2^0 1 mod 13

2^1 2 mod 13

2^2 4 mod 13

2^3 8 mod 13

2^4 3 mod 13

2^5 6 mod 13

2^6 12 mod 13

2^7 11 mod 13

2^8 9 mod 13

2^9 5 mod 13

2^10 10 mod 13

2^11 7 mod 13

2^12 1 mod 13

Here we get all the possible results 1,2,3,4,5,6,7,8,9,10,11,12 [Numbers co-prime to 13]

Therefore 2 is a primitive root modulo 13

(d).

Modulo 17

3^0 1 mod 17

3^1 3 mod 17

3^2 9 mod 17

3^3 10 mod 17

3^4 13 mod 17

3^5 5 mod 17

3^6 15 mod 17

3^7 11 mod 17

3^8 16 mod 17

3^9 14 mod 17

3^10 8 mod 17

3^11 7 mod 17

3^12 4 mod 17

3^13 12 mod 17

3^14 2 mod 17

3^15 6 mod 17

3^16 1 mod 17

We get all the possible results 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

Therefore 3 is a primitive root modulo 17

Thank you