Maths Olympiad Prep

Library / HMMT February /568 of 1302

HMMT February

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(2a−1)N=a(2 a-1). The sum 1+2+⋯+(N−1)1+2+\cdots+(N-1) is divisible by kk for every integer 1≤k≤101 \leq k \leq 10.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The second condition implies that 16 divides a(2a−1)(2a2−a−1)a(2 a-1)\left(2 a^{2}-a-1\right), which shows that a≡0a \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(2a−1)(2a2−a−1)a(2 a-1)\left(2 a^{2}-a-1\right). a cannot be 17, because 9 does not divide a(2a−1)(2a2−a−1)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+⋯+(N−1)=24⋅32⋅5⋅7⋅13⋅311+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(2⋅32−1)=2016N=32(2 \cdot 32-1)=2016.

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

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.