Number theoryDifficulty 8.7ShortlistProve itNetherlands
For a positive integer n, we define α(n) as the average of all positive divisors of n, and β(n) as the average of all positive integers k≤n such that gcd(k,n)=1. Find all positive integers n for which α(n)=β(n).
Solution
Answer:n=1 and n=6.
We first note that n=1 satisfies.
We now prove that β(n)=2n for n≥2. Indeed, gcd(k,n)=gcd(k−n,n)=gcd(n−k,n), so gcd(k,n)=1 if and only if gcd(n−k,n)=1. This yields a partition of the positive integers 1≤k≤n−1 with gcd(k,n)=1 into pairs (k,n−k), which have mean 2n. For n≥2, gcd(n,n)>1, so we see that the average of all the numbers 1≤k≤n with gcd(k,n)=1 is also equal to 2n. The number 2n might have been double counted, but that does not matter since the average is 2n.
Prime numbers do not satisfy, because then α(n)=2n+1 and β(n)=2n.
Now suppose d is a positive divisor of n with d unequal to 1 and n. Then we have 2≤d≤2n, so (2n−d)(d−2)≥0, so 2nd+2d≥n+d2, so 2n+2≥dn+d.
Now suppose n>6 is compound. We can divide the positive divisors of n into pairs (d,dn). The pair (1,n) has average 2n+1, all other pairs have average 2dn+d≤22n+2<2n−1, or it is just the number n≤3n<2n−2 (in this case, n≥9 holds). If n is not the square of a prime number, we have a pair with average 2n+1, a pair with average smaller than 2n−1, and even possibly more pairs (or a single number) all with average smaller than 2n−1, making the total average smaller than 2n. If n is the square of a prime number, we find α(n)=31+n+n<31+2n−2+n=63n=2n. So n>6 does not satisfy.
Also n=4 does not satisfy, because α(4)=31+2+4=37 while β(4)=24=2.
Finally, we check that n=1 and n=6 indeed satisfy:
* n=1: We have α(1)=β(1)=1. * n=6: We have α(6)=41+2+3+6=3 and β(6)=21+5=3.
We conclude that α(n)=β(n) if and only if n=1 or n=6. □
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.