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

[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]

Originally Posted by 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.
(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

[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]

Originally Posted by 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.

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]

Originally Posted by 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.
(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.

[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

[mr.sanjogm]

I picked numbers and got B . I took one even and odd number greater than 9 to test the choices.....but kevin's approach is bow wow yippee yay