BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Remainder from large integer

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Junior | Next Rank: 30 Posts
Posts: 22
Joined: Wed Sep 20, 2017 5:42 pm
Thanked: 2 times

Remainder from large integer

by pannalal » Sun Sep 24, 2017 6:16 am
Let N = 301302303304....448449450.
Clearly N is a large integer containing 450 digits.
What will be remainder when N is divided by 91?
(A) 74
(B) 75
(C) 76
(D) 77
(E) None of the above

OA will be given later.

Note: The question is not difficult and can be solved using simple number properties.
Top
Source: — Problem Solving |
Junior | Next Rank: 30 Posts
Posts: 22
Joined: Wed Sep 20, 2017 5:42 pm
Thanked: 2 times

by pannalal » Sun Sep 24, 2017 6:48 pm
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.
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

it's a subject

by Matt@VeritasPrep » Tue Sep 26, 2017 7:44 pm
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.
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Tue Sep 26, 2017 8:00 pm
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.
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

yo yo subject

by Matt@VeritasPrep » Tue Sep 26, 2017 8:02 pm
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.)
Top
Junior | Next Rank: 30 Posts
Posts: 22
Joined: Wed Sep 20, 2017 5:42 pm
Thanked: 2 times

by pannalal » Tue Sep 26, 2017 9:04 pm
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.
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Tue Sep 26, 2017 10:48 pm
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.
Top
Post new topic Post Reply
• Page 1 of 1