## Divided by 5

Find the reminder when $3^{98}$ is divided by $5$?
Source: NCTM Mathematics Teacher, October 2006

Solution
$3^{98}$ is such a large number that it is impractical to use modulo $5$ arithmetic to find the remainder. So we are going to find the remainders of a few powers of $3$ and hope to see a pattern emerge.
Remainders when $3^x$ are divided by $5$
$3^0\qquad\qquad 1$
$3^1\qquad\qquad 3$
$3^2\qquad\qquad 4$
$3^3\qquad\qquad 2$
$3^4\qquad\qquad 1$
$3^5\qquad\qquad 3$
$3^6\qquad\qquad 4$
$3^7\qquad\qquad 2$
$3^8\qquad\qquad 1$
$3^9\qquad\qquad 3$
$3^{10}\qquad\quad\:\:\, 4$
$3^{11}\qquad\quad\:\:\, 2$
$\cdots$
The pattern of remainders is $1,3,4,2,1,3,4,2,\cdots$. The remainder equals $1$ when the even exponent is the product of $2$ and an even number, for example, the remainder of $3^8$ equals $1$ because $8=2\times 4$. The remainder equals $4$ when the even exponent is the product of $2$ and an odd number, for example, the remainder of $3^{10}$ equals $4$ because $10=2\times 5$.
Since $98=2\times 49$, the remainder of $3^{98}$ divided by $5$ equals $4$.

Answer: $4$

Alternative solution
We can group the powers $3^x$ according to their remainders as follows:
$1\!: 3^0,3^4,3^8,3^{12},\cdots$
$3\!: 3^1,3^5,3^9,3^{13},\cdots$
$4:\! 3^2,3^6,3^{10},3^{14},\cdots$
$2:\! 3^3,3^7,3^{11},3^{15},\cdots$
This is exactly what modulo $4$ arithmetic does, divide the whole numbers $0,1,2,3,4,\cdots$ into four groups
$0,4,8,12,\cdots$
$1,5,9,13,\cdots$
$2,6,10,14,\cdots$
$3,7,11,15,\cdots$
Since $98\equiv 2\bmod 4, 3^{98}$ divided by $5$ will have the same remainder as $3^2$ divided by $5$.