2018 AMC 10B Problem 16

P16-20~4 minPrint

Modular Arithmetic Number Properties Apply an identity: SFFT, sum of squares, difference of cubes, Vieta Compute small cases, spot the pattern, generalize

Let $a_1,a_2,\dots,a_{2018}$ be a strictly increasing sequence of positive integers such that $a_1+a_2+\cdots+a_{2018}=2018^{2018}.$ What is the remainder when $a_1^3+a_2^3+\cdots+a_{2018}^3$ is divided by $6$ ?

Show solution without answering

Key insight

A number and its cube always leave the same remainder when divided by 6, so the sum of cubes acts like the plain sum.

Solution

We cannot possibly find the $2018$ numbers, so the answer must depend only on their sum. Look for a link between a number and its cube when dividing by $6$ .

Try small numbers.

$n$	$0$	$1$	$2$	$3$	$4$	$5$
$n^3$	$0$	$1$	$8$	$27$	$64$	$125$
remainder of $n^3$ when divided by $6$	$0$	$1$	$2$	$3$	$4$	$5$

Each cube leaves the same remainder as the number itself.
2. Why it is always true. The difference is
$n^3 - n = (n-1) \times n \times (n+1),$
the product of three numbers in a row. Among three numbers in a row, one is even and one is a multiple of $3$ . So the product is a multiple of $6$ . That means $n^3$ and $n$ always leave the same remainder when divided by $6$ .
3. Add them up. Since each cube differs from its number by a multiple of $6$ , the sum of the cubes differs from the plain sum by a multiple of $6$ . So the sum of cubes has the same remainder as
$a_1 + a_2 + \cdots + a_{2018} = 2018^{2018}.$
4. Remainder of $2018^{2018}$ . $2018 = 6 \times 336 + 2$ , so only the $2$ matters. Powers of $2$ divided by $6$ :
- $2 \to 2$ , $4 \to 4$ , $8 \to 2$ , $16 \to 4$ , $32 \to 2$ , ...

Odd powers leave $2$ and even powers leave $4$ . The power $2018$ is even, so the remainder is $4$ .

The answer is $\boxed{\textbf{(E)}\ 4}$ .

Why this works

When a problem gives far too little information to find the numbers, it is asking about something that does not depend on them. Here that is the fact that a number and its cube always leave the same remainder when divided by $6$ . The words "strictly increasing" do not matter at all.

Alternative approach

Find the remainder of $2018^{2018}$ by thinking about $2$ and $3$ separately. It is even, so its remainder when divided by $2$ is $0$ . Also $2018$ is one less than a multiple of $3$ , and an even power of such a number is one more than a multiple of $3$ . Among $0, 1, 2, 3, 4, 5$ , the only number that is even and one more than a multiple of $3$ is $4$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The sequence itself is nowhere near determined, so the answer must depend only on the given sum. The bridge between a number and its cube modulo $6$ is the identity
$n^3 - n = (n-1)\,n\,(n+1),$
a product of three consecutive integers, which always contains a multiple of $2$ and a multiple of $3$ . Hence $n^3 \equiv n \pmod 6$ for every integer $n$ .

Applying this to each term and adding,
$a_1^3 + \cdots + a_{2018}^3 \equiv a_1 + \cdots + a_{2018} = 2018^{2018} \pmod 6.$

Now $2018 = 6 \cdot 336 + 2$ , so $2018^{2018} \equiv 2^{2018} \pmod 6$ . Powers of $2$ modulo $6$ go $2, 4, 2, 4, \dots$ : odd exponents give $2$ , even exponents give $4$ . Since $2018$ is even, $2^{2018} \equiv 4 \pmod 6$ .

The answer is $\boxed{\textbf{(E)}\ 4}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Algebra, Chapter 11: Special Factorizations
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)