• EMPOWERgmat Slider
    1 Hour Free
    BEAT THE GMAT EXCLUSIVE

    Available with Beat the GMAT members only code

    MORE DETAILS
    EMPOWERgmat Slider
  • Target Test Prep
    5-Day Free Trial
    5-day free, full-access trial TTP Quant

    Available with Beat the GMAT members only code

    MORE DETAILS
    Target Test Prep
  • Varsity Tutors
    Award-winning private GMAT tutoring
    Register now and save up to $200

    Available with Beat the GMAT members only code

    MORE DETAILS
    Varsity Tutors
  • Veritas Prep
    Free Veritas GMAT Class
    Experience Lesson 1 Live Free

    Available with Beat the GMAT members only code

    MORE DETAILS
    Veritas Prep
  • e-gmat Exclusive Offer
    Get 300+ Practice Questions
    25 Video lessons and 6 Webinars for FREE

    Available with Beat the GMAT members only code

    MORE DETAILS
    e-gmat Exclusive Offer
  • Economist Test Prep
    Free Trial & Practice Exam
    BEAT THE GMAT EXCLUSIVE

    Available with Beat the GMAT members only code

    MORE DETAILS
    Economist Test Prep
  • Kaplan Test Prep
    Free Practice Test & Review
    How would you score if you took the GMAT

    Available with Beat the GMAT members only code

    MORE DETAILS
    Kaplan Test Prep
  • PrepScholar GMAT
    5 Day FREE Trial
    Study Smarter, Not Harder

    Available with Beat the GMAT members only code

    MORE DETAILS
    PrepScholar GMAT
  • examPAL
    Most awarded test prep in the world
    Now free for 30 days

    Available with Beat the GMAT members only code

    MORE DETAILS
    examPAL
  • Magoosh
    Magoosh
    Study with Magoosh GMAT prep

    Available with Beat the GMAT members only code

    MORE DETAILS
    Magoosh

Remainder from large integer

This topic has 4 expert replies and 2 member replies
pannalal Junior | Next Rank: 30 Posts Default Avatar
Joined
20 Sep 2017
Posted:
22 messages
Upvotes:
2

Remainder from large integer

Post 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.

  • +1 Upvote Post
  • Quote
  • Flag
pannalal Junior | Next Rank: 30 Posts Default Avatar
Joined
20 Sep 2017
Posted:
22 messages
Upvotes:
2
Post 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 Smile
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.

  • +1 Upvote Post
  • Quote
  • Flag

GMAT/MBA Expert

Matt@VeritasPrep GMAT Instructor
Joined
12 Sep 2012
Posted:
2640 messages
Followed by:
113 members
Upvotes:
625
Target GMAT Score:
V51
GMAT Score:
780
Post 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.

  • +1 Upvote Post
  • Quote
  • Flag
Enroll in a Veritas Prep GMAT class completely for FREE. Wondering if a GMAT course is right for you? Attend the first class session of an actual GMAT course, either in-person or live online, and see for yourself why so many students choose to work with Veritas Prep. Find a class now!
pannalal Junior | Next Rank: 30 Posts Default Avatar
Joined
20 Sep 2017
Posted:
22 messages
Upvotes:
2
Post 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.

  • +1 Upvote Post
  • Quote
  • Flag

GMAT/MBA Expert

Matt@VeritasPrep GMAT Instructor
Joined
12 Sep 2012
Posted:
2640 messages
Followed by:
113 members
Upvotes:
625
Target GMAT Score:
V51
GMAT Score:
780
Post 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 Smile

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.

  • +1 Upvote Post
  • Quote
  • Flag
Enroll in a Veritas Prep GMAT class completely for FREE. Wondering if a GMAT course is right for you? Attend the first class session of an actual GMAT course, either in-person or live online, and see for yourself why so many students choose to work with Veritas Prep. Find a class now!

GMAT/MBA Expert

Matt@VeritasPrep GMAT Instructor
Joined
12 Sep 2012
Posted:
2640 messages
Followed by:
113 members
Upvotes:
625
Target GMAT Score:
V51
GMAT Score:
780
Post 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.

  • +1 Upvote Post
  • Quote
  • Flag
Enroll in a Veritas Prep GMAT class completely for FREE. Wondering if a GMAT course is right for you? Attend the first class session of an actual GMAT course, either in-person or live online, and see for yourself why so many students choose to work with Veritas Prep. Find a class now!

GMAT/MBA Expert

Matt@VeritasPrep GMAT Instructor
Joined
12 Sep 2012
Posted:
2640 messages
Followed by:
113 members
Upvotes:
625
Target GMAT Score:
V51
GMAT Score:
780
Post 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:

http://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.)

  • +1 Upvote Post
  • Quote
  • Flag
Enroll in a Veritas Prep GMAT class completely for FREE. Wondering if a GMAT course is right for you? Attend the first class session of an actual GMAT course, either in-person or live online, and see for yourself why so many students choose to work with Veritas Prep. Find a class now!

Best Conversation Starters

1 lheiannie07 108 topics
2 Roland2rule 63 topics
3 ardz24 63 topics
4 LUANDATO 50 topics
5 AAPL 42 topics
See More Top Beat The GMAT Members...

Most Active Experts

1 image description GMATGuruNY

The Princeton Review Teacher

152 posts
2 image description Jeff@TargetTestPrep

Target Test Prep

106 posts
3 image description Rich.C@EMPOWERgma...

EMPOWERgmat

104 posts
4 image description Scott@TargetTestPrep

Target Test Prep

96 posts
5 image description Max@Math Revolution

Math Revolution

87 posts
See More Top Beat The GMAT Experts