Relatively Prime Sets and a Phi Function for Subsets of {1, 2, …, n}

Min Tang^{1}

Department of Mathematics Anhui Normal University Wuhu 241000 P. R. China

                       tmzzz2000@163.com

Abstract

A nonempty subset A of {1, 2, …, n} is said to be relatively prime if gcd(A) = 1. Let f(n) and f_{k}(n) denote respectively the number of relatively prime subsets and the number of relatively prime subsets of cardinality k of {1, 2, …, n}. Let Φ(n) and Φ_{k}(n) denote respectively the number of nonempty subsets and the number of subsets of cardinality k of {1, 2, …, n} such that gcd(A) is relatively prime to n. In this paper, we obtain some properties of these functions.

1 Introduction

A nonempty subset A of {1, 2, …, n} is said to be relatively prime if gcd(A) = 1. Nathanson [5] defined f(n) to be the number of relatively prime subsets of {1, 2, …, n}, and for k ≥ 1, he defined f_{k}(n) to be the number of relatively prime subsets of cardinality k of {1, 2, …, n}. Nathanson [5] defined Φ(n) and Φ_{k}(n), respectively, to be the number of nonempty subsets and the number of subsets of cardinality k of {1, 2, …, n} such that gcd(A) is relatively prime to n. Sloane’s sequence \underline{A085945} enumerates f(n) and \underline{A027375} enumerates Φ(n). Let ⌊x⌋ denote the greatest integer less than or equal to x, φ(n) the Euler phi function and μ(n) the Möbius function. Nathanson [5] obtained the following explicit formulas for these functions.

1Supported by the National Natural Science Foundation of China, Grant No. 10901002.

Theorem 1. The following hold:

(a) For all positive integers n,

f(n) = ∑_{d=1}^{n} μ(d)(2^{⌊n/d⌋} − 1).  (1)

(b) For all positive integers n ≥ 2,

Φ(n) = ∑_{d|n} μ(d)2^{n/d}.  (2)

(c) For all integers n and k,

f_{k}(n) = ∑_{d=1}^{n} μ(d)\binom{⌊n/d⌋}{k}.  (3)

(d) For all integers n and k,

Φ_{k}(n) = ∑_{d|n} μ(d)\binom{n/d}{k}.  (4)

Generalizations may be found in [2, 3, 4]. In 2009, Ayad and Kihel [1] studied some properties of the functions f(n) and Φ(n). They showed that f(n) is never a square if n ≥ 2, and for any prime l ≠ 3, f(n) is not periodic modulo l. Moreover, they proved the following equality.

Theorem 2. For any integer n ≥ 1, we have

f(n + 1) − f(n) = \frac{1}{2}Φ(n + 1).  (5)

In this paper, we give a new simple proof of the above result and obtain some properties of these functions.

Theorem 3. For all integers n and k, we have

Φ_{k}(n + 1) = f_{k}(n + 1) − f_{k}(n) + f_{k+1}(n + 1) − f_{k+1}(n).  (6)

Remark 4. Note that for any positive integers n, f_{1}(n + 1) = f_{1}(n) = 1. By Theorem 3, we have f_{2}(n+1)−f_{2}(n) = Φ_{1}(n+1) = φ(n+1). Thus for n ≥ 2, we have f_{2}(n+1)−f_{2}(n) ≡ 0 (mod 2), and f_{2}(2) = 1, thus f_{2}(n) ≡ 1 (mod 2) for all n ≥ 2. Remark 5. By Theorem 3, for all n ≥ 2 we have f_{2}(n) − f_{2}(n − 1) = φ(n). Thus

∑_{2≤i≤n} φ(i) = ∑_{2≤i≤n} (f_{2}(i) − f_{2}(i − 1)) = f_{2}(n),

hence

f_{2}(n) = \frac{3n^{2}}{π^{2}} + O(n log n).

Remark 6. Let p, q be primes. Note that Φ(p) = 2^{p} − 2 and Φ(pq) = 2^{pq} − 2^{p} − 2^{q} + 2. Thus Φ(p) ≡ Φ(pq) ≡ 2 (mod 4). And Φ(n) ≡ 0 (mod 3) for all n ≥ 3 (see [1]); thus Φ(p) ≡ Φ(pq) ≡ 6 (mod 12). Hence Φ(p) and Φ(pq) are neither a square nor a cube.

To prove Theorem 2 and 3, we need the following lemma.

Lemma 7. For all integers n and k,

⌊\frac{n + 1}{k}⌋ − ⌊\frac{n}{k}⌋ = \{ \begin{matrix}1, if k | (n + 1); \\ 0, otherwise. \end{matrix}

2 Proof of Theorem 2.

By (1) we have

\begin{aligned}f(n + 1) − f(n) & = ∑_{d=1}^{n+1} μ(d)(2^{⌊ \frac{n+1}{d} ⌋} − 1) − ∑_{d=1}^{n} μ(d)(2^{⌊n/d⌋} − 1) \\ & = ∑_{d=1}^{n} μ(d)(2^{⌊ \frac{n+1}{d} ⌋} − 2^{⌊n/d⌋}) + μ(n + 1). \end{aligned}

By (2) and Lemma 7,

f(n + 1) − f(n) = ∑_{\begin{matrix}d=1 \\ d|n+1 \end{matrix}}^{n} μ(d)2^{⌊ \frac{n}{d} ⌋} + μ(n + 1)

= ∑_{d|n+1} μ(d)2^{⌊n/d⌋}

= \frac{1}{2} ∑_{d|n+1} μ(d)2^{\frac{n+1}{d}} = \frac{1}{2}Φ(n + 1).

This completes the proof of Theorem 2.

3 Proof of Theorem 3.

Case 1: k = 1. f_{1}(n + 1) = f_{1}(n) = 1. By (3) we have

\begin{aligned}f_{2}(n + 1) − f_{2}(n) & = ∑_{d=1}^{n+1} μ(d)\binom{⌊\frac{n+1}{d}⌋}{2} − ∑_{d=1}^{n} μ(d)\binom{⌊n/d⌋}{2} \\ & = ∑_{d=1}^{n} μ(d)(\binom{⌊\frac{n+1}{d}⌋}{2} − \binom{⌊n/d⌋}{2}). \end{aligned}

By (2) and Lemma 7, we have

f_{2}(n + 1) − f_{2}(n) = ∑_{\begin{matrix}d=1 \\ d|n+1 \end{matrix}}^{n} μ(d)\binom{\frac{n+1}{d} − 1}{1}

= ∑_{\begin{matrix}d=1 \\ d|n+1 \end{matrix}}^{n} μ(d)(\frac{n + 1}{d} − 1)

= ∑_{d|n+1} μ(d)(\frac{n + 1}{d} − 1)

= ∑_{d|n+1} μ(d)\frac{n + 1}{d} = Φ_{1}(n + 1).

Case 2: k ≥ 2. By (3) and Lemma 7, we have

f_{k}(n + 1) − f_{k}(n) = ∑_{d=1}^{n+1} μ(d)\binom{⌊\frac{n+1}{d}⌋}{k} − ∑_{d=1}^{n} μ(d)\binom{⌊n/d⌋}{k}

= ∑_{d=1}^{n} μ(d)(\binom{⌊\frac{n+1}{d}⌋}{k} − \binom{⌊n/d⌋}{k})

= ∑_{d|n+1} μ(d)\binom{⌊\frac{n}{d}⌋}{k − 1}.

Thus by (4) and Lemma 7, we have

f_{k}(n + 1) − f_{k}(n) + f_{k+1}(n + 1) − f_{k+1}(n) = ∑_{d|n+1} μ(d)(\binom{⌊\frac{n}{d}⌋}{k − 1} + \binom{⌊\frac{n}{d}⌋}{k})

= ∑_{d|n+1} μ(d)\binom{⌊\frac{n}{d}⌋ + 1}{k}

= ∑_{d|n+1} μ(d)\binom{\frac{n+1}{d}}{k} = Φ_{k}(n + 1).

This completes the proof of Theorem 3.

4 Acknowledgements

We would like to thank the referees for their helpful comments.

References

[1] M. Ayad and O. Kihel, The number of relatively prime subsets of {1, 2, …, n}, Integers 9 (2009), A14. Available electronically at http://integers-ejcnt.org/vol9.html.

[2] M. Ayad and O. Kihel, On the number of subsets relatively prime to an integer, J. Integer Sequences 11 (2008), Paper 08.5.5.

[3] M. Ayad and O. Kihel, On relatively prime sets, Integers 9 (2009), A28. Available

electronically at http://integers-ejcnt.org/vol9.html.

[4] M. El Bachraoui, On the number of subsets of [1, m] relatively prime to n and asymptotic estimates, Integers 8 (2008), A41. Available electronically at

http://integers-ejcnt.org/vol8.html.

[5] M. B. Nathanson, Affine invariants, relatively prime sets, and a phi function for subsets of {1, 2, …, n}, Integers 7 (2007), A01. Available electronically at

http://integers-ejcnt.org/vol7.html.

2000 Mathematics Subject Classification: Primary 11A25; Secondary 11B75. Keywords: relatively prime subset, Euler phi function.

(Concerned with sequences \underline{A027375} and \underline{A085945}.)

Received March 27 2010; revised version received July 9 2010. Published in Journal of Integer Sequences, July 16 2010.

Return to Journal of Integer Sequences home page.