Maths Olympiad Prep

Library / /7 of 24

Number theory Difficulty 8.2 Shortlist Prove it Romania

We say that a natural number n3n \ge 3 is almost square-free if there exists a prime number pp, with p1(mod3)p \equiv 1 \pmod 3, such that nn is divisible by p2p^2, and the number np\frac{n}{p} is square-free (i.e., not divisible by the square of any prime number).

Show that, for any natural number nn that is almost square-free, the ratio between twice the sum of the divisors of nn and the number of divisors of nn is a natural number.

Lucian Petrescu

Solution

Consider n=p1pk1pk2pk+1psn = p_1 \cdots p_{k-1} \cdot p_k^2 \cdot p_{k+1} \cdots p_s, with p1<p2<<psp_1 < p_2 < \dots < p_s prime numbers, 1ks1 \le k \le s, and p=pk1(mod3)p = p_k \equiv 1 \pmod 3. Moreover, pp is odd and satisfies p2+p+10(mod3)p^2 + p + 1 \equiv 0 \pmod 3.

The number of divisors of nn, τ(n)\tau(n), is
τ(n)=(1+1)(1+1)(1+1)applied s1 times(2+1)=32s1, \tau(n) = \underbrace{(1+1) \cdot (1+1) \cdots (1+1)}_{\text{applied } s-1 \text{ times}} \cdot (2+1) = 3 \cdot 2^{s-1},
and the sum of the divisors, σ(n)\sigma(n), is:
σ(n)=p121p11pk121pk11pk31pk1pk+121pk+11ps21ps1=(p1+1)(pk1+1)(pk2+pk+1)(pk+1+1)(ps+1). \begin{aligned} \sigma(n) &= \frac{p_1^2-1}{p_1-1} \cdots \frac{p_{k-1}^2-1}{p_{k-1}-1} \cdot \frac{p_k^3-1}{p_k-1} \cdots \frac{p_{k+1}^2-1}{p_{k+1}-1} \cdots \frac{p_s^2-1}{p_s-1} \\ &= (p_1+1) \cdots (p_{k-1}+1) \cdot (p_k^2+p_k+1) \cdot (p_{k+1}+1) \cdots (p_s+1). \end{aligned}

Case I. If nn is even, then p1=2p_1 = 2, and p2<p3<<psp_2 < p_3 < \dots < p_s are odd primes. Hence, 2σ(n)=2(2+1)(p2+1)(pk1+1)(pk2+pk+1)(pk+1+1)(ps+1)2\sigma(n) = 2 \cdot (2+1) \cdot (p_2+1) \cdots (p_{k-1}+1) \cdot (p_k^2+p_k+1) \cdot (p_{k+1}+1) \cdots (p_s+1), so 2σ(n)2\sigma(n) is divisible by 2322s2=3τ(n)2 \cdot 3^2 \cdot 2^{s-2} = 3 \cdot \tau(n).

Case II. If nn is odd, then p1<p2<<psp_1 < p_2 < \dots < p_s are odd primes, so
σ(n)=(p1+1)(pk1+1)(pk2+pk+1)(pk+1+1)(ps+1) \sigma(n) = (p_1 + 1) \cdots (p_{k-1} + 1) \cdot (p_k^2 + p_k + 1) \cdot (p_{k+1} + 1) \cdots (p_s + 1)
is divisible by 32s1=τ(n)3 \cdot 2^{s-1} = \tau(n).

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.