Exercise (6.2).5

(i) Show that

$$ 7^1, 7^2, 7^3, \ldots , 7^{\phi(11)} \pmod {11} $$

produce a reduced residue system modulo 11 and complete the following table:

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

(ii) By using your results of part (i), complete the following table:

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

(i) The following calculations show that $7^n$ for $n =1, 2, \ldots, \phi(11)$ produces a reduced residue system. That is, the right-most column contains, just once, every factor of 11 that is co-prime to it.

n	7^n	7^n mod 11
1	7	7
2	49	5
3	343	2
4	2401	3
5	16807	10
6	117649	4
7	823543	6
8	5764801	9
9	40353607	8
10	282475249	1

The following is the completed table.

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

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

We can see from (i) above that the order of $7 \pmod {11}$ is 10, so $a=7, k=10$. 

We consider $a^s \equiv 7^s \pmod n$. The table from (i) shows that $7^s \pmod {11}$ can be equivalent to every number from 1 to 10, for values of $s$ from 1 to 10. So the Order Formula as $10/\gcd(s,10)$ gives us the order for every number from 1 to 10 modulo 11.

The results of this calculation gives us the required table.

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