Maths Olympiad Prep

Library / /51 of 82

Number theory Difficulty 5.7 AIME, harder Prove it Croatia

For a given positive integer kk let S(k)S(k) denote the sum of all numbers from the set {1,2,,k}\{1, 2, \dots, k\} relatively prime to kk. Let mm be a positive integer and nn an odd positive integer. Prove that there exist positive integers xx and yy such that mm divides xx and 2S(x)=yn2S(x) = y^n.

Solution

For k=1k = 1, S(k)=1S(k) = 1. For k>1k > 1, note that for a positive integer a<ka < k relatively prime to kk the number kak - a is also relatively prime to kk. Hence the summands in the sum S(k)S(k) can be paired and each pair has sum kk. The number of positive integers relatively prime to kk (and less than kk) is φ(k)\varphi(k), so
S(k)=kφ(k)2. S(k) = \frac{k\varphi(k)}{2}.
Let qq be the largest prime factor of mm, and let 2=p1<p2<<ps=q2 = p_1 < p_2 < \dots < p_s = q be consecutive prime numbers. Then m=p1a1psasm = p_1^{a_1} \dots p_s^{a_s} (where some of aia_i are 0). We will construct a number xx of the form x=p1b1psbsx = p_1^{b_1} \dots p_s^{b_s} satisfying the condition of the problem. Note that
2S(x)=xφ(x)=p1b1psbsp1b11(p11)psbs1(ps1)=p12b11(p11)ps2bs1(ps1). \begin{aligned} 2S(x) &= x\varphi(x) = p_1^{b_1} \dots p_s^{b_s} \cdot p_1^{b_1-1} (p_1-1) \dots p_s^{b_s-1} (p_s-1) \\ &= p_1^{2b_1-1} (p_1-1) \dots p_s^{2b_s-1} (p_s-1). \end{aligned}
Also, for every isi \le s all prime divisors of pi1p_i - 1 are among p1,,psp_1, \dots, p_s, so we choose c1,,csc_1, \dots, c_s such that (p11)(ps1)=p1c1pscs(p_1 - 1) \dots (p_s - 1) = p_1^{c_1} \dots p_s^{c_s}, i.e.
2S(x)=p12b1+c11ps2bs+cs1. 2S(x) = p_1^{2b_1+c_1-1} \dots p_s^{2b_s+c_s-1}.
The number xx satisfies the condition of the problem if and only if 2bi+ci12b_i + c_i - 1 is divisible by nn and biaib_i \ge a_i, for all i{1,,s}i \in \{1, \dots, s\}.
Since nn is odd, its multiples alternate in being even and odd, so for every ii we can choose a large enough kiNk_i \in \mathbb{N} such that kinci1(mod2)k_i n \equiv c_i - 1 \pmod 2 and
bi=kinci+12ai. b_i = \frac{k_i n - c_i + 1}{2} \ge a_i.

Then 2S(x)=p12b1+c11ps2bs+cs1=(p1k1psks)n2S(x) = p_1^{2b_1+c_1-1} \dots p_s^{2b_s+c_s-1} = (p_1^{k_1} \dots p_s^{k_s})^n, which shows that xx satisfies the condition of the problem.

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 and solution reproduced as published; topic and difficulty added by this site.