Divisibility by 7

[jeffboaz]

Does anyone have a better explanation for this problem?

If x is a positive integer, what is the remainder when 7^12x+3 + 3 is divided by 5?

I understand the explanation given, but I'm not sure I understand it enough to replicate it in a future problem.

Thx
Jeff

[andrew.k.john]

We want to start by breaking it up into parts. Consider what the remainders of both 7^(12x+3) and 3 will be when divided by 5. The second one is easy. It will be 3. First one is more difficult, but here's how I do it.

Any time I see a problem about remainders of numbers when divided by a single digit number (in this case 5), I only care about the last digit of the number being divided. In this case, we want to identify a pattern in the single's digit for 7^(?). Below is the pattern...

7^1 = 7
7^2 = 9
7^3 = 3
7^4 = 1

Once we get a single's digit of 1, we know the pattern will repeat. In this example, the pattern is every 4, and since 12 is divisible by 4, we know that taking 7 to the (12x+3) power will always result in a number that has singles digit of 3.

With this info, we know the remainders of both 3 and 7^(12x+3) will be 3 when divided by 5, so the remainder of the sum will be 1.

There is an alternative strategy as well for this type of problem. Simply consider the case of x=1. We know that it must hold true for ALL positive integers of x, so we can test for the easiest x. Unfortunately, 7^15 is still too large for us to test, but in other examples, you may have an easier time testing one number.

Does this help?

[RonPurewal]

first, you have to realize that you really don't have to know that much about a number in order to determine the remainder upon dividing it by 5.
specifically:
to determine the remainder upon division by 5, all you need is the units digit of the number.
if the units digit is 0 or 5, the remainder is 0.
if the units digit is 1 or 6, the remainder is 1.
if the units digit is 2 or 7, the remainder is 2.
if the units digit is 3 or 8, the remainder is 3.
if the units digit is 4 or 9, the remainder is 4.

this pattern is easy to discover by just testing the remainders upon dividing a whole bunch of integers by 5, but, ideally, it's something that you'll know (or can recognize) going into the problem.

There is an alternative strategy as well for this type of problem. Simply consider the case of x=1. We know that it must hold true for ALL positive integers of x, so we can test for the easiest x. Unfortunately, 7^15 is still too large for us to test, but in other examples, you may have an easier time testing one number.

actually, if you make the units-digit realization above, then 7^15 isn't that obnoxious at all. it's boring, to be sure, but you can just keep multiplying units digits by 7 (and then discarding all the digits to the left of the units digit, since you don't care about those digits) until you've multiplied together fifteen 7's.
7^1 = 7
multiply by 7 = 49
... so 7^2 has units digit 9
multiply by 7 = 63
... so 7^3 has units digit 3
multiply by 7 = 21
... so 7^4 has units digit 1
...so you've just discovered the pattern:
7, 9, 3, 1, 7, 9, 3, 1, ...
so it follows that 7^15 must end with the digit '3'.
therefore, 7^15 + 3 ends with '6', so the remainder when you divide this number by 5 is 1.

if you had to find the actual number, of course, then yeah that would be an obnoxious amount of work. the gmat will NEVER make you do that much work.