Maths Olympiad Prep

Library / /323 of 520

Number theory Difficulty 6.2 National olympiad Find the answer

25. For nNn \in \mathbf{N}^{*}, let f(n)f(n) denote the smallest positive integer such that: nk=1f(n)kn \mid \sum_{k=1}^{f(n)} k. Find all nNn \in \mathbf{N}^{*} such that f(n)=2n1f(n)=2 n-1.

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

Solution

25. First, we prove: If n=2m,mN n=2^{m}, m \in \mathbf{N} , then f(n)=2n1 f(n)=2 n-1 .

In fact, on one hand,
k=12n1k=(2n1)n=(2m+11)2m \sum_{k=1}^{2 n-1} k=(2 n-1) n=\left(2^{m+1}-1\right) 2^{m}
is divisible by n n . On the other hand, if l2n2 l \leqslant 2 n-2 , then
k=1lk=12l(l+1) \sum_{k=1}^{l} k=\frac{1}{2} l(l+1)
Since one of l l and l+1 l+1 is odd, and
l+12n1=2m+11, l+1 \leqslant 2 n-1=2^{m+1}-1,
the above sum cannot be divisible by 2m 2^{m} (because 2m+1×l(l+1) 2^{m+1} \times l(l+1) ).
Next, we prove: When n n is not a power of 2, f(n)<2n1 f(n) < 2 n-1 . Let n=2mp n=2^{m} p , where p p is an odd number. We show that there exists l<2n1 l < 2 n-1 such that 2m+1l 2^{m+1} \mid l and p(l+1) p \mid (l+1) (in this case, of course, 2mpl(l+1)2 2^{m} p \left\lvert\, \frac{l(l+1)}{2}\right. , thus f(n)<2n1 f(n) < 2 n-1 ).

Since (2m+1,p)=1 \left(2^{m+1}, p\right)=1 , by the Chinese Remainder Theorem,
l0(mod2m+1),lp1(modp), l \equiv 0\left(\bmod 2^{m+1}\right), \quad l \equiv p-1(\bmod p),
has a solution lx0(mod2m+1p) l \equiv x_{0}\left(\bmod 2^{m+1} p\right) . Therefore, there exists l0,0<l02m+1p l_{0}, 0 < l_{0} \leqslant 2^{m+1} p satisfying the above system of congruences. Note that 2n10(mod2m+1) 2 n-1 \neq 0\left(\bmod 2^{m+1}\right) , and 2n+1≢0(modp) 2 n+1 \not \equiv 0(\bmod p) , so 2n1 2 n-1 and 2n 2 n are not solutions to this system of congruences, hence 0<l0<2n1 0 < l_{0} < 2 n-1 , i.e., f(n)<2n1 f(n) < 2 n-1 .

In summary, f(n)=2n1 f(n) = 2 n-1 if and only if n n is a power of 2.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.