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.

 

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s