Maths Olympiad Prep

Library / /978 of 1394

Number theory Difficulty 5.5 AIME, harder Prove it United States

Problem:
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(2a - 1).
- The sum 1+2++(N1)1 + 2 + \cdots + (N - 1) is divisible by kk for every integer 1k101 \leq k \leq 10.

Solution

Solution:
Answer: 2016

The second condition implies that 1616 divides a(2a1)(2a2a1)a(2a - 1)(2a^{2} - a - 1), which shows that a0a \equiv 0 or 11 modulo 1616. The case a=1a = 1 would contradict the triviality-avoiding condition N>1N > 1. aa cannot be 1616, because 77 does not divide a(2a1)(2a2a1)a(2a - 1)(2a^{2} - a - 1). aa cannot be 1717, because 99 does not divide a(2a1)(2a2a1)a(2a - 1)(2a^{2} - a - 1). 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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.