Maths Olympiad Prep

Library / /3 of 16

Number theory Difficulty 5.4 AIME, harder Prove it Bulgaria

Problem:
For any positive integer nn denote by f(n)f(n) the smallest positive integer mm such that the sum 1+2++m1+2+\cdots+m is divisible by nn. Find all nn such that f(n)=n1f(n)=n-1.

Solution

Solution:
If f(n)=n1f(n)=n-1, then nn divides the sum 1+2++(n1)=(n1)n21+2+\cdots+(n-1)=\frac{(n-1)n}{2}, which implies that nn is odd.

The numbers n=psn=p^{s}, where p>2p>2 is a prime number and s1s \geq 1, are solutions. Indeed, if kNk \in \mathbb{N} and k<ps1k<p^{s}-1, then the sum 1+2++k=k(k+1)21+2+\cdots+k=\frac{k(k+1)}{2} is not divisible by psp^{s} because kk and k+1k+1 are coprime and less than psp^{s}.

We shall prove that these are the only solutions. Let nn be an odd positive integer which is not a power of a prime number. Then n=abn=a b, where a>1a>1, b>1b>1 and (a,b)=1(a, b)=1. By the Chinese Remainder Theorem we conclude that there exists an integer k[0,ab1]k \in[0, a b-1] such that aka \mid k and bk+1b \mid k+1. It is clear that k0,kab1k \neq 0, k \neq a b-1 and abk(k+1)2a b \left\lvert\, \frac{k(k+1)}{2}\right.. Therefore n=abn=a b is not a solution.

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.