• 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
  • PrepScholar GMAT
    5 Day FREE Trial
    Study Smarter, Not Harder

    Available with Beat the GMAT members only code

    MORE DETAILS
    PrepScholar GMAT
  • 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
  • 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
  • EMPOWERgmat Slider
    1 Hour Free
    BEAT THE GMAT EXCLUSIVE

    Available with Beat the GMAT members only code

    MORE DETAILS
    EMPOWERgmat Slider
  • Magoosh
    Magoosh
    Study with Magoosh GMAT prep

    Available with Beat the GMAT members only code

    MORE DETAILS
    Magoosh
  • Economist Test Prep
    Free Trial & Practice Exam
    BEAT THE GMAT EXCLUSIVE

    Available with Beat the GMAT members only code

    MORE DETAILS
    Economist Test Prep
  • Veritas Prep
    Free Veritas GMAT Class
    Experience Lesson 1 Live Free

    Available with Beat the GMAT members only code

    MORE DETAILS
    Veritas Prep

Remainder from large integer

This topic has 4 expert replies and 2 member replies

Remainder from large integer

Post Sun Sep 24, 2017 6:16 am
Elapsed Time: 00:00
  • Lap #[LAPCOUNT] ([LAPTIME])
    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.

    Need free GMAT or MBA advice from an expert? Register for Beat The GMAT now and post your question in these forums!
    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.

    GMAT/MBA Expert

    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.

    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

    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.

    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

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

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

    GMAT/MBA Expert

    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.

    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 Vincen 180 topics
    2 lheiannie07 61 topics
    3 Roland2rule 54 topics
    4 ardz24 44 topics
    5 VJesus12 14 topics
    See More Top Beat The GMAT Members...

    Most Active Experts

    1 image description Brent@GMATPrepNow

    GMAT Prep Now Teacher

    155 posts
    2 image description Rich.C@EMPOWERgma...

    EMPOWERgmat

    105 posts
    3 image description GMATGuruNY

    The Princeton Review Teacher

    101 posts
    4 image description Jay@ManhattanReview

    Manhattan Review

    82 posts
    5 image description Matt@VeritasPrep

    Veritas Prep

    80 posts
    See More Top Beat The GMAT Experts