Remainder from large integer

As nobody has posted any solution, I am giving first hint.

Hint 1: Please note that 1001 = 7x11x13. So, when you divide 1000 by 7 or 13 or 91, you get remainder of -1. If you divide 1000x1000 by 91, you get remainder of 1. This will help you to solve the above problem.

Note: I hope, many viewers will be able to find solution with the above hint. If I don't get solution in another 12 hours, I shall post second hint.

This isn't anything close to a GMAT problem, so no students are likely to answer it. It doesn't seem like any instructors are interested either, but I'm game. It took me a while to find an elegant solution, but here's one that absolutely rules

We want 301,302,303,...,449,450 mod 91. Let's break this up into:

(301,000,000,...,000 + 302,000,000,...,000 + ... + 449,000 + 450) mod 91

Playing around with the last two terms, we notice something:

450 mod 91 = 86 mod 91
449,000 mod 91 = 6 mod 91, or, more nicely for our purposes, = -85 mod 91

Hmmm! So 449,450 mod 91 = (86 + 6) mod 91 = (86 + -85) mod 91 = 1

What if we go further?

448,000,000 mod 91 = 84 mod 91
447,000,000,000 mod 91 = 8 mod 91 = -83 mod 91
so 447,448,000,000 mod 91 = (84 + -83) mod 91 = 1 mod 91

Aha! Every time we add two consecutive terms, starting from the right, the remainder of that sum will be 1 mod 91.

We have 75 such sets of consecutive terms, so our remainder = (1 * 75) mod 91, or 75.

For those wondering why that property holds, here's an explanation.

Each of our summands can be expressed in the form (451 - n) * 10³��³, and we have all such summands from n=1 to n = 150.

Notice that each of those summands is multiplied by 10 raised to some multiple of 3. Now notice what happens when we consider the first few such powers of 10:

10� mod 91 = 1 mod 91
10³ mod 91 = 90 mod 91 = -1 mod 91

This cycle will repeat, since the subsequent power will be the previous power, multiplied by 1000. That means that

10� mod 91 = 1 mod 91
10� mod 91 = -1 mod 91
etc. etc.

That means that each of our powers of 10, considered modulo 91, multiplies the term before it by 1 or by -1. For example:

450 * 10� => 450 mod 91 * 10� mod 91 = 450 mod 91 * 1 = 86
449 * 10³ => 449 mod 91 * 10³ mod 91 = 449 mod 91 * -1 = -85
448 * 10� => 448 mod 91 * 10� mod 91 = 448 mod 91 * 1 = 84
447 * 10� => 447 mod 91 * 10� mod 91 = 447 mod 91 * -1 = -83
etc.

From there, we can see that the sum of the remainders of any two consecutive terms, starting from the right, will be 1, and that we have 75 such sums.

If you're feeling too lazy, skeptical, or bored to check the above, here's a computer verification:

https://www.wolframalpha.com/input/?i=(sum+(451+-+n)*10%5E(3n+-+3)+from+n+%3D+1+to+n+%3D+150)+mod+91

(Apologies for the formatting - for some reason this wouldn't cooperate with the url tag.)

Matt@VeritasPrep wrote:This isn't anything close to a GMAT problem, so no students are likely to answer it. It doesn't seem like any instructors are interested either, but I'm game. It took me a while to find an elegant solution, but here's one that absolutely rules

Matt, you are right. I give slightly difficult problem to my students once in a while so that when they encounter difficult problems in exam, they are able to handle these with confidence.

Now, I give a simple solution:

10³ = 1000 = -1 (mod 91)
So, 10� mod 91 = 1 mod 91

This means, instead of 450 digits number, we are handling 75 groups of 6 digit numbers. We can take 6 digits numbers from right and keep adding on to get the remainder.

Now, second part of simplification:
Each 6-digit number is of the form 301302, 303304, ..., 449450.
You can write these: 1000*n + n + 1 = 1001*n + 1
As 1001 is divisible by 91 (7 or 11 or 13). So, the remainder is 1.

Thus, the sum of remainders = 1*75 = 75.

So, the answer is B.

pannalal wrote:Matt, you are right. I give slightly difficult problem to my students once in a while so that when they encounter difficult problems in exam, they are able to handle these with confidence.

Sure, but with respect:

1) This problem is harder and more technical than any official GMAT problem and not at all within the scope or spirit of the test. It's "slightly difficult" relative to certain tests, such as our American AMC 12, but those tests require far more mathematical sophistication than the GMAT, which is more a test of mathematical instincts than mathematical learning;

2) With that in mind, posting it on a GMAT forum without explicit warnings is counterproductive, and referring to it as "slightly difficult" before an audience that finds "what's the % change from 100 to 250" slightly difficult isn't going to help or encourage any students. If you're tutoring the Indian CAT this kind of problem may be in bounds, but that's a different test with a different set of expectations.