In each of the following cases determine the least non-negative residue $x$:
(a) $3^{1000} \equiv x \pmod {17} $
(b) $3^{970} \equiv x \pmod {98} $
(a) Since $\gcd(3,17)=1$, Euler's Theorem gives us $3^{\phi(17)} \equiv 1 \pmod{17}$. This means the order of 3 modulo 17 is a factor of $\phi(17)=16$. These factors are 1, 2, 4, 8, 16, and these are the only ones we need to test.
The following calculations show that $2^{16}\equiv 1 \pmod {17}$.
| n | 3^n | 3^n mod 17 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 4 | 81 | 13 |
| 8 | 6561 | 16 |
| 16 | 43046721 | 1 |
The order of 3 modulo 17 is 16.
This gives us $3^{16} \equiv 1 \pmod {17}$. Using Proposition (6.6) we have
$$ \begin{align} 3^{1000} & \equiv 3^{(1000 \bmod 16)} \pmod {17} \\ \\ & \equiv 3^8 \pmod {17} \\ \\ 3^{1000} & \equiv 16 \pmod {17} \end{align} $$
So the least non-negative residue is $x=16$.
(b) Since $\gcd(3, 98)=1$, Euler's Theorem tells us $3^{\phi(98)} \equiv 1 \pmod{98}$. This means the order of 3 modulo 98 is a factor of $\phi(98)=42$. These factors are 1, 2, 3, 6, 7, 14, 21, 42, and these are the only ones we need to test.
The following calculations show that $4^n \neg \equiv 1 \pmod {98}$ for $n=1, 2, 3, 6, 7, 14, 21$.
| n | 3^n | 3^n mod 98 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 3 | 27 | 27 |
| 6 | 729 | 43 |
| 7 | 2187 | 31 |
| 14 | 4782969 | 79 |
| 21 | 10460353203 | 97 |
This leave only 42 as the order of 3 modulo 98.
We now have $3^{42} \equiv 1 \pmod {98}$. Using Proposition (6.6) we have
$$ \begin{align} 3^{970} & \equiv 3^{(970 \bmod 42)} \pmod {98} \\ \\ & \equiv 3^4 \pmod {98} \\ \\ 3^{1000} & \equiv 81 \pmod {98} \end{align} $$
So the least non-negative residue is $x=81$.