Problem Solving

What is the least possible value that can be subtracted from 2^586 so that the result is a multiple of 7?

A. 2
B. 3
C. 5
D. 7
E. 11

What is the best way to solve? any shortcut??

Mo2men wrote:What is the least possible value that can be subtracted from 2^586 so that the result is a multiple of 7?

A. 2
B. 3
C. 5
D. 7
E. 11

What is the best way to solve? any shortcut??

Hmmm, I attacked this as follows.

First, notice (D) is obviously wrong. If you subtract 7 from a number and the resulting number is a multiple of 7 - well the initial number must also be a multiple of 7. Likewise (E) can be eliminated because it is larger than 7. At most, the number being subtracted could possibly be is 6...

Now, I wasn't 100% sure, but I decided to see if I could find a pattern.

2^0 = 1 Subtract 1 to get a multiple of 7
2^1 = 2 Subtract 2
2^2 = 4 Subtract 4
2^3 = 8 Subtract 1
2^4 = 16 Subtract 2
2^5 = 32 Subtract 4

A pattern should be emerging. In order to get a multiple of 7 from a power of 2, you will either subtract 1, 2 or 4. Only answer choice (A) contains one of these integers. Hence, (A) should be the answer.

What is the OA?

Mo2men wrote:What is the least possible value that can be subtracted from 2^586 so that the result is a multiple of 7?

A. 2
B. 3
C. 5
D. 7
E. 11

TEST EASY CASES and LOOK FOR A PATTERN.

2³ - 1 = 7.
2� - 2 = 14.
2� - 4 = 28.

2� - 1 = 63.
2� - 2 = 126.
2� - 4 = 252.

The subtracted numbers exhibit the following pattern:
1, 2, 4.
Implication:
To yield a multiple of 7, we must subtract 1, 2, or 4.

The correct answer is A.

Here's a very straightforward approach:

We want the remainder of 2��� when divided by 7. Notice that 2��� = (2³)¹�� = (remainder 1)¹��.

Since 2��� = 2 * 2��� = (remainder 2) * (remainder 1), our number has a remainder of 2 when divided by 7. Subtracting 2 will do it, so we're set.

Matt@VeritasPrep wrote:Here's a very straightforward approach:

We want the remainder of 2��� when divided by 7. Notice that 2��� = (2³)¹�� = (remainder 1)¹��.

Since 2��� = 2 * 2��� = (remainder 2) * (remainder 1), our number has a remainder of 2 when divided by 7. Subtracting 2 will do it, so we're set.

Thanks for your answer.

However, after solving this question, I have another question. what if the same number is divided by 5? what would the reminder? why your approach did not work well here with me???

2��� = (2³)¹�� * 2 = (5+3)¹�� * 2

(5+3)¹�� will leave reminder 3 when divided by 5

so final reminder = 3 * 2= 6

While I have solved with Mitch's approach

2^1) / 5 will have remainder 2
(2^2) / 5 will have remainder 4
(2^3) / 5 will have remainder 3
(2^4) / 5 will have remainder 1
(2^5) / 5 will have remainder 2

Thus cyclicity of 2^n / 5 is 4

2^286 = 2^2 * 2^284

2^2/5 will have reminder 4

2^284/5 will have reminder 1

so reminder 4*1=4

Thanks [/list]

Mo2men wrote:

Matt@VeritasPrep wrote:Here's a very straightforward approach:

We want the remainder of 2��� when divided by 7. Notice that 2��� = (2³)¹�� = (remainder 1)¹��.

Since 2��� = 2 * 2��� = (remainder 2) * (remainder 1), our number has a remainder of 2 when divided by 7. Subtracting 2 will do it, so we're set.

Thanks for your answer.

However, after solving this question, I have another question. what if the same number is divided by 5? what would the reminder? why your approach did not work well here with me???

The key idea is to find power of 2 that we know has a remainder of 1 when divided by 5, then work from there.

For instance, we know that 2� has a remainder of 1 when divided by 5. From there

2��� =
2��� * 2² =
(2�)¹�� * 2² =
(remainder 1)¹�� * (remainder 4) =
(remainder 1) * (remainder 4) =
(remainder 4)

And here's a harder example: suppose we want to know the remainder 2��� when divided by 14.

We start with the same approach: looking for a power of 2 that has a remainder of 1 when divided by 14. But we won't be able to find one, since 14 is even and all our powers of 2 will be even. With that in mind, we'll look for something with a fairly small remainder, such as 2.

Since 2� / 14 has remainder 2, let's work with that.

2��� =
2��� * 2² =
(2�)¹�� * 2² =
(remainder 2)¹�� * (remainder 4)

Now we can work with our remainder 2, treating it as a base. We know that 2¹�� breaks down in the same fashion:

2¹�� * 2² =
(2�)³� * 2² * 2² =
(2�)³� =
(remainder 2)³�

Then we repeat:

2³� =
(2�)� * 2 =
(remainder 2)� * 2

And one more time:

2¹� =
(2�)² * 2² =
(remainder 2)² * 2² =
2 * 2 * 2 * 2 = 16

16 / 14 has remainder 2, so we're set: the remainder is 2.

Once you get the hang of this, you can skip a lot of the steps above, but it's a powerful process that generalizes well to any integer base and integer exponent you're likely to see.

suppose we want to know the remainder 2��� when divided by 14.

An alternate approach is to determine the cycle of remainders.

2¹/14 --> remainder of 2
2²/14 --> remainder of 4
2³/14 --> remainder of 8
2�/14 --> remainder of 2

Since 2� yields the same remainder as 2¹ -- implying the beginning of a new cycle -- the cycle of remainders is as follows:
2, 4, 8...2, 4, 8...2, 4, 8...

Implication:
Every exponent that is a multiple of 3 will yield a remainder of 8, with the next biggest exponent beginning a new cycle and yielding a remainder of 2.

285 is a multiple of 3 since the sum of its digits is a multiple of 3.
Thus:
2²�� --> remainder of 8
2²�� --> remainder of 2 (the start of a new cycle).