Journal of Integer Sequences, Vol. 15 (2012), Article 12.3.6

On Relatively Prime Subsets, Combinatorial Identities, and Diophantine Equations


Mohamed El Bachraoui
Department of Mathematical Sciences
United Arab Emirates University
P.O. Box 17551
Al-Ain
United Arab Emirates

Abstract:

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,    dvi,    ps,    latex    


Received September 23 2011; revised version received February 2 2012; March 14 2012. Published in Journal of Integer Sequences, March 25 2012.


Return to Journal of Integer Sequences home page