Number theoryDifficulty 6.2National olympiadFind the answer
25. For n∈N∗, let f(n) denote the smallest positive integer such that: n∣∑k=1f(n)k. Find all n∈N∗ such that f(n)=2n−1.
A number or a short expression. Spacing and $ signs are ignored.
Solution
25. First, we prove: If n=2m,m∈N, then f(n)=2n−1.
In fact, on one hand, k=1∑2n−1k=(2n−1)n=(2m+1−1)2m is divisible by n. On the other hand, if l⩽2n−2, then k=1∑lk=21l(l+1) Since one of l and l+1 is odd, and l+1⩽2n−1=2m+1−1, the above sum cannot be divisible by 2m (because 2m+1×l(l+1)). Next, we prove: When n is not a power of 2, f(n)<2n−1. Let n=2mp, where p is an odd number. We show that there exists l<2n−1 such that 2m+1∣l and p∣(l+1) (in this case, of course, 2mp2l(l+1), thus f(n)<2n−1).
Since (2m+1,p)=1, by the Chinese Remainder Theorem, l≡0(mod2m+1),l≡p−1(modp), has a solution l≡x0(mod2m+1p). Therefore, there exists l0,0<l0⩽2m+1p satisfying the above system of congruences. Note that 2n−1=0(mod2m+1), and 2n+1≡0(modp), so 2n−1 and 2n are not solutions to this system of congruences, hence 0<l0<2n−1, i.e., f(n)<2n−1.
In summary, f(n)=2n−1 if and only if 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.