Divisibility problem from Manhattan

[jcmsolis]

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.

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

[DWarrior]

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.

[krusta80]

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.

© 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

[DWarrior]

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.

[krusta80]

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? :)

[DWarrior]

Damn, that's sick. I figured out the "remainders add" (your first part) by doing some problems here, but kudos on the other 2.

[kevinspain]

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.

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

[hina_0611]

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