Track / Stage 5 / 111 of 400 #711 of 2000

Problem 711

AIME late

Number theory Difficulty 5.3 Find the answer

Let's determine all integer values of $n$ for which: $n\left(n^{2}-1\right)\left(n^{2}-4\right)$ is divisible by 2, 4, 8, 16, 32, 64, 128, and generally by any higher power of 2!

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

$N$ is divisible by $2^{3}$ for every $n$ .

$N$ is divisible by $2^{4}$ if and only if $n=4 k$ , or $n=4 k-2$ , or $n=4 k+2$ .

$N$ is divisible by $2^{5}$ if and only if $n=8 k$ , or $n=4 k-2$ , or $n=4 k+2$ .

$N$ is divisible by $2^{6}$ if and only if $n=16 k$ , or $n=4 k-2$ , or $n=4 k+2$ .

$N$ is divisible by $2^{7}$ if and only if $n=32 k$ , or $n=16 k-2$ , or $n=16 k+2$ .

$N$ is divisible by $2^{8}$ if and only if $n=64 k$ , or $n=32 k-2$ , or $n=32 k+2$ .

$N$ is divisible by $2^{p}$ if and only if $n=2^{p-2} k$ , or $n=2^{p-3} k-2$ , or $n=2^{p-3} k+2$ .

We can verify each statement by direct substitution. Only in the case of divisibility by $2^{6}$ , when $n=4 k+2$ or $n=4 k-2$ , a separate examination is needed.

Let $n=4 k+2$ , then $N=k(4 k+1)(4 k+2)(4 k+3)(4 k+4)=2^{5} \cdot k(k+1)(4 k+1)(4 k+3)(2 k+1)$ , but $k(k+1)$ is divisible by 2 and thus $N q=2^{6} k$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.