(a) Determine the order of $81 \pmod {105}$.
(b) Determine the order of $81 \pmod {106}$.
(a) Since $\gcd(81,105)=3 \ne 1$, the order does not exist.
(b) Since $\gcd(81, 106)=1$, the order of 81 modulo 105 exists.
Noting that $81=3^4$, we'll work in base 3, and first find the order of $3 \pmod {106}$. The order is a factor of $\phi(106)=52$. These factors are 1, 2, 4, 13, 26, 52, and these are the only ones we need to test.
The following calculations show that the order of $3 \pmod {106}$ is not 2, 4 or 13. The numbers become too large for testing factors 26 and 52.
| n | 3^n | 3^n mod 106 |
| 2 | 9 | 9 |
| 4 | 81 | 81 |
| 13 | 1594323 | 83 |
Let's try a different approach.
$$ 3^{26} \equiv (3^{13})^2 \equiv (83)^2 \equiv 6889 \equiv 105 \pmod {106} $$
So 26 is not the order of 3 modulo 106.
$$ 3^{52} \equiv (3^{13})^4 \equiv (83)^4 \equiv 47458321 \equiv 1 \pmod {106} $$
So the order of 3 modulo 106 is 52.
The Order Formula (6.8) tells us that if $k$ is the order of $a \pmod n$, then the order of $a^s \pmod n$ is $k / \gcd(s,k)$. And so the order of $81 \pmod {106}$ is $52 / \gcd(4,52) = 52/4 = 13$.
The order of $81 \pmod {106}$ is 13.