Maths Olympiad Prep

Library / /486 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Find the least positive integer N>1N>1 satisfying the following two properties: There exists a positive integer aa such that N=a(2a1)N=a(2 a-1). The sum 1+2++(N1)1+2+\cdots+(N-1) is divisible by kk for every integer 1k101 \leq k \leq 10.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The second condition implies that 16 divides a(2a1)(2a2a1)a(2 a-1)\left(2 a^{2}-a-1\right), which shows that a0a \equiv 0 or 1 modulo 16. The case a=1a=1 would contradict the triviality-avoiding condition N>1N>1. aa cannot be 16, because 7 does not divide a(2a1)(2a2a1)a(2 a-1)\left(2 a^{2}-a-1\right). a cannot be 17, because 9 does not divide a(2a1)(2a2a1)a(2 a-1)\left(2 a^{2}-a-1\right). It can be directly verified that a=32a=32 is the smallest positive integer for which 1+2++(N1)=24325713311+2+\cdots+(N-1)=2^{4} \cdot 3^{2} \cdot 5 \cdot 7 \cdot 13 \cdot 31 which is divisible by 1,2,,101,2, \ldots, 10. For this aa, we compute N=32(2321)=2016N=32(2 \cdot 32-1)=2016.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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