Maths Olympiad Prep

Library / /10 of 12

Number theory Difficulty 8.7 Shortlist Prove it Netherlands

For a positive integer nn, we define α(n)\alpha(n) as the average of all positive divisors of nn, and β(n)\beta(n) as the average of all positive integers knk \le n such that gcd(k,n)=1\gcd(k, n) = 1.
Find all positive integers nn for which α(n)=β(n)\alpha(n) = \beta(n).

Solution

Answer: n=1n = 1 and n=6n = 6.

We first note that n=1n = 1 satisfies.

We now prove that β(n)=n2\beta(n) = \frac{n}{2} for n2n \ge 2. Indeed, gcd(k,n)=gcd(kn,n)=gcd(nk,n)\gcd(k, n) = \gcd(k - n, n) = \gcd(n - k, n), so gcd(k,n)=1\gcd(k, n) = 1 if and only if gcd(nk,n)=1\gcd(n - k, n) = 1. This yields a partition of the positive integers 1kn11 \le k \le n - 1 with gcd(k,n)=1\gcd(k, n) = 1 into pairs (k,nk)(k, n - k), which have mean n2\frac{n}{2}. For n2n \ge 2, gcd(n,n)>1\gcd(n, n) > 1, so we see that the average of all the numbers 1kn1 \le k \le n with gcd(k,n)=1\gcd(k, n) = 1 is also equal to n2\frac{n}{2}. The number n2\frac{n}{2} might have been double counted, but that does not matter since the average is n2\frac{n}{2}.

Prime numbers do not satisfy, because then α(n)=n+12\alpha(n) = \frac{n+1}{2} and β(n)=n2\beta(n) = \frac{n}{2}.

Now suppose dd is a positive divisor of nn with dd unequal to 11 and nn. Then we have 2dn22 \le d \le \frac{n}{2}, so (n2d)(d2)0(\frac{n}{2} - d)(d - 2) \ge 0, so n2d+2dn+d2\frac{n}{2}d + 2d \ge n + d^2, so n2+2nd+d\frac{n}{2} + 2 \ge \frac{n}{d} + d.

Now suppose n>6n > 6 is compound. We can divide the positive divisors of nn into pairs (d,nd)(d, \frac{n}{d}). The pair (1,n)(1, n) has average n+12\frac{n+1}{2}, all other pairs have average nd+d2n2+22<n12\frac{\frac{n}{d}+d}{2} \le \frac{\frac{n}{2}+2}{2} < \frac{n-1}{2}, or it is just the number nn3<n22\sqrt{n} \le \frac{n}{3} < \frac{n-2}{2} (in this case, n9n \ge 9 holds). If nn is not the square of a prime number, we have a pair with average n+12\frac{n+1}{2}, a pair with average smaller than n12\frac{n-1}{2}, and even possibly more pairs (or a single number) all with average smaller than n12\frac{n-1}{2}, making the total average smaller than n2\frac{n}{2}. If nn is the square of a prime number, we find α(n)=1+n+n3<1+n22+n3=3n6=n2\alpha(n) = \frac{1+\sqrt{n}+n}{3} < \frac{1+\frac{n-2}{2}+n}{3} = \frac{3n}{6} = \frac{n}{2}. So n>6n > 6 does not satisfy.

Also n=4n = 4 does not satisfy, because α(4)=1+2+43=73\alpha(4) = \frac{1+2+4}{3} = \frac{7}{3} while β(4)=42=2\beta(4) = \frac{4}{2} = 2.

Finally, we check that n=1n = 1 and n=6n = 6 indeed satisfy:

* n=1n = 1: We have α(1)=β(1)=1\alpha(1) = \beta(1) = 1.
* n=6n = 6: We have α(6)=1+2+3+64=3\alpha(6) = \frac{1+2+3+6}{4} = 3 and β(6)=1+52=3\beta(6) = \frac{1+5}{2} = 3.

We conclude that α(n)=β(n)\alpha(n) = \beta(n) if and only if n=1n = 1 or n=6n = 6. \square

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.