On Relatively Prime Subsets, Combinatorial Identities, and Diophantine Equations
Mohamed El Bachraoui
Department of Mathematical Sciences
United Arab Emirates University
P.O. Box 17551
United Arab Emirates
Let n be a positive integer and let A be a nonempty finite set of
positive integers. We say that A is relatively prime if
gcd(A) = 1,
and that A is relatively prime to n if gcd(A,n)=1.
In this work
we count the number of nonempty subsets of A that are relatively
prime and the number of nonempty subsets of A that are relatively
prime to n. Related formulas are also obtained for the number of such
subsets having some fixed cardinality. This extends previous work for
the case where A is an interval of successive integers. As an
application we give some identities involving Möbius and Mertens
functions, which provide solutions to certain Diophantine equations.
Full version: pdf,
Received September 23 2011;
revised version received February 2 2012; March 14 2012.
Published in Journal of Integer Sequences, March 25 2012.
Journal of Integer Sequences home page