Problem 11161
(American Mathematical Monthly, Vol.112, June-July 2005) Proposed by E. Deutsch (USA).
Show that for all integers n ≥ 3 the number of compositions of n into relatively prime parts is a multiple of 3. (A composition of n into k parts is a list of k positive integers that sum to n.) Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
The number of compositions of n into k parts is the number of positive integral solutions of the equation x1+ x2+ · · · + xk= n which is equal to nk−1−1. Therefore the total number of compositions of n is
t(n) =
n
X
k=2
n − 1 k − 1
= 2n−1−1.
Let cd(n) be the number of compositions of n such that the greatest common divisor of its parts is equal to d. We want to prove that c1(n) ≡ 0 (mod 3) for n ≥ 3. Since
x1+ · · · + xk = n and gcd(x1, . . . , xk) = d iff xd1 + · · · +xdk =nd and gcd(xd1, . . . ,xdk) = 1 then cd(n) = c1(n/d) for any divisor d of n. Hence
t(n) =X
d|n
cd(n) =X
d|n
c1(n/d) =X
d|n
c1(d)
and by the M¨obius Inversion Formula c1(n) =X
d|n
µ(n/d)t(d) =X
d|n
µ(n/d)(2d−1−1) ≡X
d|n
µ(n/d)((−1)d−1−1) ≡X
d|n
µ(n/d)p(d) (mod 3)
where p(n) is the characteristic function of the set of the even numbers p(n) =
1 if n is even 0 if n is odd . Since p(n) =P
d|nδd,2, where δd,2 is the characteristic function of the point 2, then by the M¨obius Inversion Formula
δn,2=X
d|n
µ(n/d)p(d)
and finally c1(n) ≡ δn,2 (mod 3).
