Hard Remainder Problem with Solution

Hard Remainder Problem with Solution

Today I will provide a solution for the difficult remainder problem I asked you to attempt yesterday. Once again, you may want to read some of my older posts about remainders before going over the solution here. You can find those posts by using the following links:

Can We Solve Remainder Problems Without Using Long Division?

The Cyclical Nature of Remainders

Remainders in Disguise

And now here is the question once more, followed by a complete solution.

Level 6 Remainder Problem

Find the remainder when 2¹²⁰ is divided by 3.

Solution by recognizing a pattern:

2¹ = 2, remainder = 2
2² = 4, remainder = 1
2³ = 8, remainder = 2
2⁴ = 16, remainder = 1
2⁵ = 32, remainder = 2
2⁶ = 64, remainder = 1
2⁷ = 128, remainder = 2

Note that we evaluated the first 7 powers of 2, and then gave each of the remainders upon division by 3.

For example, 16 = 3(5) + 1, and so the remainder when 16 is divided by 3 is 1.

Now simply observe that all even powers of 2 give a remainder of 1 when divided by 3. Therefore, the answer is 1.

Remark: So how do we know with absolute certainty that the pattern we produced will continue indefinitely? After all, isn’t it possible that the pattern can stop at any time? Just because a pattern holds for the first 7 positive integers, it may not necessarily still hold for the 8th positive integer, or any other integer thereafter. But in this case it does.

Let’s prove two more general theorems that will imply that the pattern holds.

Theorem 1: If an integer gives a remainder of 1 when divided by 3, then twice that integer gives a reminder of 2 when divided by 3.

Proof: Let n be an integer that gives a remainder of 1 when divided by 3.

Then there is an integer k such that n = 3k + 1.

So 2n = 2(3k + 1) = 6k + 2 = 3(2k) + 2.

Since 2k is an integer, we have shown that 2n gives a remainder of 2 when divided by 3.

Theorem 2: If an integer gives a remainder of 2 when divided by 3, then twice that integer gives a reminder of 1 when divided by 3.

Proof: Let n be an integer that gives a remainder of 2 when divided by 3.

Then there is an integer k such that n = 3k + 2.

So 2n = 2(3k + 2) = 6k + 4 = 6k + 3 + 1 = 3(2k + 1) + 1.

Since 2k + 1 is an integer, we have shown that 2n gives a remainder of 1 when divided by 3.

After going through the proofs of these theorems, you should reflect back and make sure you understand why these two theorems imply that the pattern holds.

Comments

comments