Define P(n) as the sum of all the positive integers that are less than n and relatively prime to n.
Find all possible positive integer values of n such that P(n) = 3n, and prove that there are no others.
A basic fact for any b,c is gcd(b,c) = gcd(b-c,c).
Then c and b-c are either both coprime to b or both have a common factor with c.
Then P(n) must be a multiple of n for n>=3 since coprime values will come in pairs summing to n.
Proof that there are a finite set of possible values can be done by showing that there is some number N such that if n<=N then P(n)>=4n, or equivalently showing that there are at least four pairs of numbers coprime to n whenever n>=N.
Case 1: n is odd.
All powers of two are all coprime to n.
When n>=17 then each of 1, 2, 4, 8 are less than n/2 and n-8, n-4, n-2, n-1 are greater that n/2.
So (1,n-1), (2,n-2), (4,n-4), (8,n-8) are four pairs of numbers coprime to n.
Case 2: n is even
Trivially, (1, n-1) is a pair coprime to n.
Let f be the largest odd factor of n, then n can be written as 2^j*f for some positive integer j.
gcd(f, 2^k)=1 for any positive integer k (k=1,2, or 3 for this problem).
gcd(f, f+2^k) = gcd(f, 2^k) = 1 and since f and f+2^k are odd then gcd(2^j*f, f+2^k) = gcd(f, 2^k) = 1.
Therefore (1, n-1), (f+2, n-f-2), (f+4, n-f-4), (f+8, n-f-8) are four pairs coprime to n
But there are two subcases to consider to make sure these are four distinct pairs.
Subcase 1: j=1
Then n>=22 will have 1 < n-f-2^k < n/2 < f+2^k < n-1 for k=1,2,3 to ensure four distinct pairs
Subcase 2: j>=2
Then n>=36 will have 1 < f+2^k < n/2 < n-f-2^k < n-1 for k=1,2,3 to ensure four distinct pairs
There are three different upper limits in the cases, so take N to be the largest of 17,22,36 which makes N=36.
So for all numbers n>=36 then f(n)>=4*n.
This proof is readily extendible to show that for any m that there is a finite number of n such that P(n)=m*n, with this problem being m=3 case.
The problem can then be finished by manually checking 1<=n<=35 which Charlie has already done, showing the full set of n such that P(n)=3*n is 7,9,14,18.
Solution with proof
