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.
Original language | English |
---|---|
Journal | Journal of Integer Sequences |
Volume | 15 |
Issue number | 3 |
Publication status | Published - Mar 25 2012 |
Keywords
- Combinatorial identities
- Diophantine equation
- Mertens function
- Möbius function
- Phi function
- Relatively prime set
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics