Sponsored Ad:
Results 1 to 8 of 8

Thread: Divisibility problem from Manhattan

  1. #1
    Incorrigible
    Join Date
    Jul 2007
    Posts
    164
    Rep Power
    0


    Good post? Yes | No

    Divisibility problem from Manhattan

    Sponsored Ad:
    Is x divisible by 30?

    (1) x = k(m^3 - m), where m and k are both integers > 9

    (2) x = n^5 - n, where n is an integer > 9


    (A) Statement (1) alone is sufficient, but statement (2) alone is not sufficient.
    (B) Statement (2) alone is sufficient, but statement (1) alone is not sufficient.
    (C) BOTH statements TOGETHER are sufficient, but NEITHER statement ALONE is sufficient.
    (D) Each statement ALONE is sufficient.
    (E) Statements (1) and (2) TOGETHER are NOT sufficient.

  2. #2
    An Urch Guru Pundit Swami Sage DWarrior's Avatar
    Join Date
    Oct 2007
    Location
    New Jersey
    Posts
    665
    Rep Power
    15


    Good post? Yes | No
    Statement 1:
    Factors into k*m*(m^2-1)=k*m(m-1)(m+1). The factors will always be (m-1), m, and (m+1), meaning one of them will be divisible by 3. I don't see any way to determine if it's divisible by 10.

    I can show that Statement 2 will always be divisible by 10:
    We want the last digit to be divisible by 10. The last digit of n^5 will always be its first digit, then when you subtract n from that, the result's last digit will always be 0, thus it will be divisible by 10:
    last digit of n=1: 1, 1, 1, 1, 1
    last digit of n=2: 2, 4, 8, 6, 2
    last digit of n=3: 3, 9, 7, 1, 3
    last digit of n=4: 4, 6, 4, 6, 4
    last digit of n=5: 5, 5, 5, 5, 5
    last digit of n=6: 6, 6, 6, 6, 6
    last digit of n=7: 7, 9, 3, 1, 7
    last digit of n=8: 8, 4, 2, 6, 8
    last digit of n=9: 9, 1, 9, 1, 9

    We can also factor the right side of the equation: n(n^4-1), which can be further broken into: n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1). Once again, it's divisible by 3 because n, (n-1), and (n+1) are all factors, one of which must be divisible by 3. Maybe this can somehow be used to prove divisibility by 10, but I don't see it.

    Thus, 2 will be sufficient.

    B

    PS, are Manhattan problems supposed to be doable in 2 minutes? I doubt if there are more than 10 people in the world who can solve this one in 2 minutes.
    If you have questions about my solutions, PM me.

    Some gre/gmat stuff (mostly Math):
    My del.icio.us bookmarks
    My Clipmarks bookmarks

  3. #3
    An Urch Guru Pundit Swami Sage
    Join Date
    Aug 2007
    Posts
    696
    Rep Power
    15


    Good post? Yes | No
    Quote Originally Posted by jcmsolis View Post
    Is x divisible by 30?

    (1) x = k(m^3 - m), where m and k are both integers > 9

    (2) x = n^5 - n, where n is an integer > 9

    (A) Statement (1) alone is sufficient, but statement (2) alone is not sufficient.
    (B) Statement (2) alone is sufficient, but statement (1) alone is not sufficient.
    (C) BOTH statements TOGETHER are sufficient, but NEITHER statement ALONE is sufficient.
    (D) Each statement ALONE is sufficient.
    (E) Statements (1) and (2) TOGETHER are NOT sufficient.
    x mod 30 = 0?

    (1) x = k(m^3 - m), where m and k are both integers > 9

    k*m*(m - 1)*(m+1) mod 30 = 0?

    k doesn't really help us here. It could be anything from a multiple of 30 to a prime number like 11.

    30 = 6*5 = 2*3*5

    From m*(m-1)*(m+1), we know that we have a multiple of 2 and a multiple of 3. But there is nothing to indicate divisibility by 5. INSUFF

    (2) x = n^5 - n, where n is an integer > 9

    n^5 - n mod 30 = 0?

    n*(n^2 - 1)*(n^2 + 1) mod 30 = 0?

    n*(n+1)*(n-1)*(n^2+1) mod 30 = 0?

    Again, we know that 2 and 3 are factors...let's take a look at n^2+1:

    n^2 + 1 mod 5 = (n^2 mod 5 + 1) mod 5 = [(n mod 5)^2 mod 5 + 1] mod 5

    Now we'll quickly look at all possibilities for n mod 5:

    n mod 5 = 0 --> done
    n mod 5 = 1 --> (n-1) mod 5 = 0 --> done
    n mod 5 = 2 --> n^2+1 mod 5 = 0 --> done
    n mod 5 = 3 --> n^2+1 mod 5 = 0 --> done
    n mod 5 = 4 = -1 --> (n+1) mod 5 = 0 --> done

    SUFFICIENT!

    B

  4. #4
    An Urch Guru Pundit Swami Sage DWarrior's Avatar
    Join Date
    Oct 2007
    Location
    New Jersey
    Posts
    665
    Rep Power
    15


    Good post? Yes | No
    Your solution implies that numbers multiplied together get their remainders multiplied.

    Is there any guide to basic modular arithmetic? I've never had it in school, and someone told me it's a topic of abstract algebra, so I didn't even bother.
    If you have questions about my solutions, PM me.

    Some gre/gmat stuff (mostly Math):
    My del.icio.us bookmarks
    My Clipmarks bookmarks

  5. #5
    An Urch Guru Pundit Swami Sage
    Join Date
    Aug 2007
    Posts
    696
    Rep Power
    15


    Good post? Yes | No
    Quote Originally Posted by DWarrior View Post
    Your solution implies that numbers multiplied together get their remainders multiplied.

    Is there any guide to basic modular arithmetic? I've never had it in school, and someone told me it's a topic of abstract algebra, so I didn't even bother.
    I came up with these myself (with "proofs" no less). I will follow up with some details soon, but here are the rules for mods:

    (a+b) mod c = [(a mod c) + (b mod c)] mod c
    (a*b) mod c = [(a mod c) * (b mod c)] mod c
    (a^b) mod c = [(a mod c)^b] mod c

    Cool, huh?

  6. #6
    An Urch Guru Pundit Swami Sage DWarrior's Avatar
    Join Date
    Oct 2007
    Location
    New Jersey
    Posts
    665
    Rep Power
    15


    Good post? Yes | No
    Damn, that's sick. I figured out the "remainders add" (your first part) by doing some problems here, but kudos on the other 2.
    If you have questions about my solutions, PM me.

    Some gre/gmat stuff (mostly Math):
    My del.icio.us bookmarks
    My Clipmarks bookmarks

  7. #7
    Within my grasp!
    Join Date
    Sep 2005
    Posts
    371
    Rep Power
    16


    Good post? Yes | No
    Quote Originally Posted by jcmsolis View Post
    Is x divisible by 30?

    (1) x = k(m^3 - m), where m and k are both integers > 9

    (2) x = n^5 - n, where n is an integer > 9


    (A) Statement (1) alone is sufficient, but statement (2) alone is not sufficient.
    (B) Statement (2) alone is sufficient, but statement (1) alone is not sufficient.
    (C) BOTH statements TOGETHER are sufficient, but NEITHER statement ALONE is sufficient.
    (D) Each statement ALONE is sufficient.
    (E) Statements (1) and (2) TOGETHER are NOT sufficient.
    Note that x=(n-1)n(n+1)(n^2+1), a multiple of 2 and 3 (as n - 1, n and n+1 are three consecutive integers). x is not a multiple of 30 if and only if x is not a multiple of 5. If none of the three consecutive integers n-1,n,n+1 is a multple of 5, n= 5m + 2 or n= 5m + 3, (i.e. either 2 or 3 greater than a multiple of 5). In either case, n^2 + 1 is a multiple of 5.
    Kevin Armstrong
    GMAT Instructor
    Manhattan Review

  8. #8
    Within my grasp!
    Join Date
    Aug 2008
    Posts
    472
    Rep Power
    13


    Good post? Yes | No
    let me try another way to prove n^5 - n Is devisible by 30:

    n^5 -n = n(n-1)(n+1)( n^2 +1)= n(n-1)(n+1)(n^2 - 4 +5)
    = (n-2)(n-1)n(n+1)(n+2) + 5(n-1)n(n+1)
    product of 5 sucessive intergers must be divisible by 5,3,2 => divisible by 30
    Product of 3 sucessive intergers must divisible by 3 and 2 => divisible by 6

    => n^5 -n divisible by 30

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Divisibility / interger problem
    By ACETARGET in forum GMAT Data Sufficiency
    Replies: 2
    Last Post: 02-11-2009, 06:59 AM
  2. GMAT Prep Problem (divisibility)
    By steadystate88 in forum GMAT Data Sufficiency
    Replies: 10
    Last Post: 02-23-2008, 09:29 PM
  3. integer problem Manhattan
    By jcmsolis in forum GMAT Problem Solving
    Replies: 10
    Last Post: 11-03-2007, 02:52 AM
  4. Manhattan Gmat Problem
    By bdutt in forum GMAT Problem Solving
    Replies: 8
    Last Post: 05-21-2006, 08:37 PM
  5. Manhattan GMAT problem 12/29
    By manish2003 in forum GMAT Problem Solving
    Replies: 4
    Last Post: 01-06-2004, 06:21 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •