Exercise (6.2).6

Complete the following table which gives the orders of integers modulo 13.

Integer a	1	2	3	4	5	6	7	8	9	10	11	12
Order of a(mod 13)

We use the same approach as the previous exercise.

The following table shows that $2^n \pmod {13}$ generates all the integers from 1 to 12.

n	2^n	2^n mod 13
1	2	2
2	4	4
3	8	8
4	16	3
5	32	6
6	64	12
7	128	11
8	256	9
9	512	5
10	1024	10
11	2048	7
12	4096	1

We can therefore construct a table showing which indices of 2 modulo 13 generate each integer from 1 to 12.

Integer a	1	2	3	4	5	6	7	8	9	10	11	12
s where 2^s ≡ a (mod 13)	12	1	4	2	9	5	11	3	8	10	7	6

We now use the Order Formula (6.8) which states that if the order of $a \pmod n$ is $k$,  then the order of $a^s \pmod n$ is $k/\gcd(s,k)$. 

From the calculations above we have the order of 3 modulo 13 as $k=12$. By calculating $12/\gcd(s,12)$ for the $s$ associated with each $a^s$, we find the orders of every integer from 1 to 12.

The following table summarises these calculations, with the bottom row being the order of the numbers in the top row.

Integer a	1	2	3	4	5	6	7	8	9	10	11	12
s where 2^s ≡ a (mod 13)	12	1	4	2	9	5	11	3	8	10	7	6
k / gcd(s,k)	1	12	3	6	4	12	12	4	3	6	12	2

We note that these orders are factors of $\phi(13)=12$, as expected.