How many incongruent primitive roots do 13 has Find these pr

How many incongruent primitive roots do 13 has? Find these primitive roots.

Solution

To do this, we have to compute powers. Itís convenient to note that multiples of 13 are 26; 39; 52; 65; 78; 91; 104; 117

now

The powers of 2 are: 2; 4; 8; 3; 6; 1; 2; 4; 8; 3; 6; 1. So 2 has order 12, hence is a primitive root

The powers of 3 are: 3; 9; 1. So 3 has order 3, hence is not a primitive root

The powers of 4 are: 4; 3; 1; 4; 3; 1. So 4 has order 6, hence is not a primitive root.

The powers of 5 are: 5; 1; 5; 1. So 5 has order 4, hence is not a primitive root.

The powers of 6 are: 6; 10; 8; 9; 2. But we know 2 is a primitive root, hence so is 6.

The powers of 7 are: 7; 10; 5; 9; 11; 12 = 1; 7; 10; 5; 9; 11; 1. So 7 has order 12, hence is a primitive root.

The powers of 8 are: 8; 1; 8; 1. So 8 has order 4, hence is not a primitive root.

The powers of 9 are 9; 3; 1. So 9 has order 3, hence is not a primitive root.

The powers of 10 are 10; 9; 1; 10; 9; 1. So 10 has order 6, hence is not a primitive root.

The powers of 11 are 11; 4; 5; 3; 7; 1; 11; 4; 5; 3; 7; 1. So 11 has order 12, hence is a primitive root

The powers of 12 are 12; 1. So 12 has order 2, hence is not a primitive root.

So the primitive roots are 2, 6, 7, and 11.