Square-free integer
A square-free integer, also known as a squarefree integer, is a positive integer whose prime factorization contains no squared prime factors, meaning it is not divisible by any perfect square greater than 1.[1] Equivalently, an integer n is square-free if for every prime p, p^2 does not divide n.[2] By convention, 1 is considered square-free, as it has no prime factors at all.[1] Square-free integers play a fundamental role in number theory, appearing in contexts such as the distribution of primes, arithmetic functions, and Diophantine equations. Examples include 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, and so on (OEIS A005117).[1] A key characterization is provided by the Möbius function \mu(n), where |\mu(n)| = 1 if n is square-free and \mu(n) = 0 otherwise; thus, the indicator function for square-freeness is \mu(n)^2.[1] The square-free integers have an asymptotic density of $6/\pi^2 \approx 0.607927, meaning that the proportion of positive integers up to x that are square-free approaches this value as x tends to infinity; more precisely, the count Q(x) satisfies Q(x) = (6x/\pi^2) + [O](/page/O)(\sqrt{x}) .[1] This density arises from the Euler product \prod_p (1 - 1/p^2) = 1/\zeta(2), where \zeta is the Riemann zeta function and the product is over all primes p. Every positive integer can be uniquely expressed as the product of a square-free integer and a perfect square, highlighting their structural importance in the integers.[1]Definition and Basic Concepts
Definition
A square-free integer is a positive integer that is not divisible by any perfect square greater than 1.[1] Equivalently, its prime factorization consists of distinct primes with no repetitions, expressed as n = p_1 p_2 \cdots p_k where the p_i are distinct primes.[3] The term "square-free" was introduced in number theory contexts around the early 20th century, with the equivalent German term "quadratfrei" appearing in 1912 in Edmund Landau's work on the distribution of non-square-free numbers.[4]Examples and Small Square-Free Integers
A square-free integer is exemplified by 1, which is considered square-free vacuously, as it has no prime factors and thus no squared prime dividing it.[1] All prime numbers are square-free, since their prime factorization consists of a single prime raised to the first power.[1] Products of distinct primes, such as $6 = 2 \times 3 and $30 = 2 \times 3 \times 5, are also square-free, as no prime appears more than once in their factorization.[5] In contrast, integers like $12 = 2^2 \times 3, $4 = 2^2, $9 = 3^2, and $8 = 2^3 are not square-free, because they are divisible by the square of a prime.[1] The sequence of the first 20 positive square-free integers is 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31.[6]Basic Properties
A square-free integer is characterized by having no squared prime factors in its prime factorization, which immediately implies certain algebraic closure properties under multiplication. Specifically, if m and n are square-free positive integers with \gcd(m, n) = 1, then their product mn is also square-free, as the prime factors of m and n are distinct and each appears to the first power in mn.[7] This follows directly from the unique factorization theorem in the integers, ensuring no exponent exceeds 1 in the factorization of mn.[8] The set of square-free positive integers is thus closed under multiplication whenever the operands are coprime, forming a multiplicative subsemigroup of the positive integers under this condition. Two square-free integers are coprime if and only if they share no common prime factors, which is equivalent to the general definition of coprimality since the absence of shared primes prevents any common divisor greater than 1.[7] For example, 6 (primes 2 and 3) and 35 (primes 5 and 7) are both square-free and coprime, with their product 210 also square-free. The indicator function for square-freeness, defined as \chi(n) = 1 if n is square-free and \chi(n) = 0 otherwise, is a multiplicative arithmetic function. That is, for coprime positive integers m and n, \chi(mn) = \chi(m) \chi(n).[9] This multiplicativity arises because \chi(n) = |\mu(n)|, where \mu is the Möbius function, which is itself multiplicative, and the absolute value preserves this property for coprime arguments.[7] In the ring of integers \mathbb{Z}, square-free ideals correspond to products of distinct prime ideals. The nonzero principal ideals (n) that are radical—meaning equal to their own radical—are precisely those generated by square-free n > 1, as the radical of (n) consists of multiples of the square-free kernel of n.[10] For instance, the ideal (6) = (2)(3) is radical, while (4) = (2)^2 is not.Factorization and Decomposition
Square-Free Factorization
Every positive integer n > 1 admits a unique decomposition n = k \cdot m^2, where k is a square-free positive integer and m is a positive integer; this is known as the square-free factorization of n.[11] This representation follows directly from the fundamental theorem of arithmetic, which guarantees the uniqueness of the prime factorization of n.[11] Given the prime factorization n = \prod p_i^{a_i} with distinct primes p_i and positive integers a_i, the square-free part k is obtained by including each prime p_i to the first power if a_i is odd and excluding it if a_i is even, yielding k = \prod_{a_i \ odd} p_i. The corresponding m is then \prod p_i^{\lfloor a_i / 2 \rfloor}. This process extracts the square-free component by isolating the "odd residue" of each exponent modulo 2. Note that the radical \mathrm{rad}(n) = \prod_{a_i \geq 1} p_i, which is the product of all distinct primes dividing n, coincides with k precisely when all exponents a_i are odd but generally differs by including primes with even exponents.[12] To compute the square-free part algorithmically, first determine the prime factorization of n using trial division or more advanced methods such as the elliptic curve method; then, for each prime factor p_i^{a_i}, divide out the highest square power p_i^{2 \lfloor a_i / 2 \rfloor} to leave the contribution p_i^{a_i \mod 2}, and multiply these remainders to obtain k. Equivalently, compute the largest square divisor s^2 = \prod p_i^{2 \lfloor a_i / 2 \rfloor} of n and set k = n / s^2.[11] For example, consider n = [72](/page/72) = 2^3 \cdot [3](/page/3)^2. The exponent of 2 is 3 (odd), so include 2; the exponent of 3 is 2 (even), so exclude 3. Thus, the square-free part is k = 2, and m = 2^{\lfloor 3/2 \rfloor} \cdot [3](/page/3)^{\lfloor 2/2 \rfloor} = 2^1 \cdot [3](/page/3)^1 = 6, verifying [72](/page/72) = 2 \cdot 6^2 = 2 \cdot [36](/page/36).Square-Free Core
The square-free core of a positive integer n, denoted c(n), is the unique square-free positive integer such that n = c(n) \cdot k^2 for some positive integer k. This core is obtained by dividing n by its largest square divisor, effectively removing all even powers from the prime factorization while retaining a single factor for each prime with an odd exponent. Formally, c(n) = \frac{n}{\prod_{p \mid n} p^{2 \left\lfloor v_p(n)/2 \right\rfloor}} = \prod_{p \mid n} p^{v_p(n) \mod 2}, where the product is over the distinct primes p dividing n, and v_p(n) denotes the exponent of p in the prime factorization of n.[13][14] By construction, c(n) is always square-free, as its prime factorization consists solely of distinct primes raised to the first power (or 1 if all exponents in n are even). The integer k in the decomposition n = c(n) \cdot k^2 is given by k = \prod_{p \mid n} p^{\left\lfloor v_p(n)/2 \right\rfloor}, representing the "square root" of the square component of n. For n = 1, c(1) = 1. Representative examples include: c(12) = c(2^2 \cdot 3) = 3, since $12 = 3 \cdot 2^2; c(18) = c(2 \cdot 3^2) = 2, since $18 = 2 \cdot 3^2; c(30) = c(2 \cdot 3 \cdot 5) = 30, since $30 = 30 \cdot 1^2; and c(36) = c(2^2 \cdot 3^2) = 1, since $36 = 1 \cdot 6^2. Notably, c(n) = 1 whenever n is a perfect square.[13][14] The square-free core function c(n) is multiplicative: if \gcd(n, m) = 1, then c(nm) = c(n) \cdot c(m). This follows from the independence of prime factors in coprime arguments, preserving the mod-2 exponent structure.Square-Free Factors of Integers
The square-free factors of an integer n > 1 are defined as its square-free divisors, which are the positive divisors of n that are not divisible by any perfect square greater than 1. These factors consist precisely of the products of distinct prime factors of n, and they are exactly the divisors of the radical of n, denoted \mathrm{rad}(n), which is the product of all distinct primes dividing n.[15] The number of square-free factors of n is $2^{\omega(n)}, where \omega(n) denotes the number of distinct prime factors of n. This count arises because each square-free factor corresponds to a subset of the set of distinct primes dividing n; the empty subset yields the divisor 1, while nonempty subsets yield the products of those primes. For instance, if n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} with distinct primes p_i and exponents a_i \geq 1, then the square-free factors are generated by taking all possible products \prod_{i \in S} p_i over subsets S \subseteq \{1, 2, \dots, k\}.[7] As an example, consider n = 30 = 2 \cdot 3 \cdot 5, which has \omega(30) = 3. The square-free factors are 1, 2, 3, 5, $2 \cdot 3 = 6, $2 \cdot 5 = 10, $3 \cdot 5 = 15, and $2 \cdot 3 \cdot 5 = 30, totaling $2^3 = 8. In sieve methods of number theory, the square-free factors of n play a key role in counting square-free multiples of n up to a given bound, as they facilitate inclusion-exclusion arguments over the prime factors to exclude numbers divisible by higher powers of primes.[16]Equivalent Characterizations
Prime Factorization Characterization
A positive integer n > 1 is square-free if and only if its unique prime factorization n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, where the p_i are distinct primes and each e_i \geq 1, satisfies e_i = 1 for all i.[1] This condition ensures that no prime square divides n, as any such square would require an exponent of at least 2. The integer 1 is conventionally considered square-free, having an empty prime factorization.[17] This characterization follows from the fundamental theorem of arithmetic, which asserts that every integer greater than 1 factors uniquely into primes (up to ordering).[17] To see the equivalence, suppose n has an exponent e_i \geq 2; then p_i^2 divides n, so n is not square-free. Conversely, if all e_i = 1, no prime square divides n, confirming square-freeness. The proof of the theorem proceeds by induction on n: primes are trivially factored, and for composites, repeated division by the smallest prime factor yields the full factorization, with uniqueness ensured by the fact that primes are irreducible and any common factor in alternative factorizations must match.[17] In algebraic number theory, this notion extends to Dedekind domains, where every nonzero ideal factors uniquely into prime ideals. An ideal is square-free if it is a product of distinct prime ideals, mirroring the integer case by excluding higher powers of any prime ideal.[18] For example, in the ring of integers of a number field, square-free ideals play a key role in ramification theory and class group computations.[19] In contrast to square-free integers, cube-free integers permit exponents up to 2 in their prime factorization, meaning they are divisible by no cube greater than 1.[20] This characterization relies historically on Euclid's demonstration in the Elements of the infinitude of primes and the existence of prime factorizations (circa 300 BCE), with uniqueness rigorously established by Carl Friedrich Gauss in his Disquisitiones Arithmeticae (1801).[21]Möbius Function Characterization
A positive integer n is square-free if and only if the Möbius function satisfies \mu(n) \neq 0.[7] More precisely, when n is square-free, \mu(n) = (-1)^{\omega(n)}, where \omega(n) denotes the number of distinct prime factors of n; if n has a repeated prime factor, then \mu(n) = 0.[22] This provides a direct arithmetic test for square-freeness using the Möbius function, distinct from examining the exponents in the prime factorization. The Möbius function \mu(n) is defined such that \mu(1) = 1, \mu(n) = 0 if there exists a prime p with p^2 \mid n, and \mu(n) = (-1)^k if n is a product of exactly k distinct primes.[7] Consequently, \mu(n) vanishes precisely when n is not square-free, alternating in sign based on the parity of the number of prime factors otherwise. The absolute value |\mu(n)| thus acts as the characteristic function for square-free integers, equaling 1 if n is square-free and 0 otherwise.[22] This characterization arises directly from the definition of \mu(n), which encodes the inclusion-exclusion principle to detect squared factors in the prime factorization of n.[7] For instance, if n = p_1 p_2 \cdots p_k with distinct primes p_i, then \mu(n) = (-1)^k \neq 0; but if n = p^2 m for some prime p and integer m, the presence of the square forces \mu(n) = 0.[22] The Möbius function's link to square-freeness finds application in sieve methods for counting square-free integers up to a bound x. Specifically, the count is given by \sum_{n \leq x} |\mu(n)| = \sum_{d \leq \sqrt{x}} \mu(d) \left\lfloor \frac{x}{d^2} \right\rfloor, extending the sieve of Eratosthenes by sieving out multiples of squares via the Möbius inversion.[23]Radical and Other Equivalents
A fundamental arithmetic characterization of square-free integers involves the radical function, defined as \mathrm{rad}(n) = \prod_{p \mid n} p, the product of the distinct prime factors of a positive integer n. Since \mathrm{rad}(n) divides n and \mathrm{rad}(n) = n if and only if no prime square divides n, an integer n > 1 is square-free precisely when \mathrm{rad}(n) = n.[24] This equivalence highlights the square-free nature as the absence of higher prime powers in the factorization. The concept of square-freeness extends naturally to polynomials over the rationals. A polynomial f(x) \in \mathbb{Q} is square-free if its irreducible factorization contains no repeated factors, equivalent to \gcd(f, f') = 1 in characteristic zero, ensuring no multiple roots in the algebraic closure. This property can be verified using resultants, as \mathrm{Res}(f, f') = 0 if and only if f and f' share a common factor, indicating a repeated root.[25] Recent research has explored the density of square-free values taken by polynomials at integer points. For instance, Vaughan and Zarhin (2024) established explicit bounds on the square-free density for certain multivariable polynomials, refining earlier asymptotic results and confirming that under mild conditions, the proportion of integer points k \in \mathbb{Z}^s for which f(k) is square-free approaches the expected natural density of $6/\pi^2.[26] Such studies bridge integer and polynomial square-freeness, with applications to Diophantine problems.Analytic Number Theory
Dirichlet Series
The Dirichlet series generating function for the indicator of square-free positive integers is the sum over all n \geq 1 of |\mu(n)| n^{-s}, where \mu denotes the Möbius function. This series equals \zeta(s)/\zeta(2s) for \Re(s) > 1, where \zeta is the Riemann zeta function.[1] The equality follows from the Euler product formula for the zeta function, yielding \frac{\zeta(s)}{\zeta(2s)} = \prod_p \frac{1 - p^{-2s}}{1 - p^{-s}} = \prod_p (1 + p^{-s}), with the infinite product ranging over all primes p. The local factor $1 + p^{-s} at each prime corresponds to the contribution from the empty product (1) and the single prime power p (since higher powers p^k for k \geq 2 are excluded for square-free integers).[1] This Dirichlet series converges absolutely in the half-plane \Re(s) > 1 and admits a meromorphic continuation to the whole complex plane, determined by the meromorphic nature of \zeta(s) and \zeta(2s). It features a simple pole at s = 1, arising from the simple pole of \zeta(s) there (while \zeta(2) is finite and nonzero), and is holomorphic elsewhere except at points where \zeta(2s) vanishes but \zeta(s) does not.[1] Such generating functions emerged as fundamental tools in 19th-century analytic number theory, extending Bernhard Riemann's 1859 investigation of the zeta function to study arithmetic properties like square-freeness through multiplicative structure.Asymptotic Density
The asymptotic density of square-free integers, defined as the natural density \lim_{x \to \infty} Q(x)/x where Q(x) counts the square-free positive integers up to x, equals $6/\pi^2 \approx 0.607927.[27] This value indicates that square-free integers comprise roughly 60.79% of all positive integers.[27] The derivation stems from the Dirichlet series for the characteristic function of square-free integers, \sum_{n=1}^\infty \mu^2(n)/n^s = \zeta(s)/\zeta(2s), evaluated at s=1, yielding $1/\zeta(2). Since \zeta(2) = \pi^2/6, the density simplifies to $6/\pi^2.[27] An elementary proof employs the inclusion-exclusion principle: Q(x) = \sum_{n \leq x} \sum_{d^2 \mid n} \mu(d) = \sum_{d=1}^\infty \mu(d) \lfloor x/d^2 \rfloor. For large x, the sum approximates x \sum_{d=1}^\infty \mu(d)/d^2 = x/\zeta(2) = (6/\pi^2)x, with the main term arising from the Euler product \prod_p (1 - 1/p^2) = 1/\zeta(2).[27] Classical estimates provide the error term Q(x) = (6/\pi^2)x + O(\sqrt{x}), where the O(\sqrt{x}) bound accounts for the finite sum up to d \approx \sqrt{x} and discrepancies from the floor function.[28] This density extends to arithmetic progressions. For residues a modulo q with \gcd(a,q)=1, the number of square-free integers up to x congruent to a modulo q is asymptotically c_{a,q} x, where c_{a,q} > 0 is given by (1/\phi(q)) \sum_{\chi \pmod{q}} \overline{\chi}(a) L(1,\chi)/L(2,\chi) via orthogonality of Dirichlet characters and the series \sum \mu^2(n) \chi(n)/n^s = L(s,\chi)/L(2s,\chi); such densities are positive since L(2,\chi) \neq 0.[29]Gaps Between Square-Free Integers
A gap between square-free integers refers to the difference between consecutive such numbers in the natural number sequence. While the asymptotic density of square-free integers is \frac{6}{\pi^2} \approx 0.6079, implying an average gap of approximately \frac{\pi^2}{6} \approx 1.64493 between them, local fluctuations lead to larger maximal gaps. These gaps often occur in regions dense with multiples of small prime squares, such as near multiples of 4, 9, or 25, where sequences of non-square-free numbers arise due to divisibility by p^2 for small primes p. Upper bounds on the maximal gap between square-free integers up to x have been progressively improved since the mid-20th century. Early results by Fogels (1941) established that every interval (x, x + x^{\theta}] with \theta > \frac{2}{5} contains a square-free integer for sufficiently large x, later refined by Roth (1951) to \theta > \frac{3}{13} \approx 0.2308. A significant advancement came from Filaseta and Trifonov (1990), who proved using elementary methods that there exists a constant c > 0 such that every interval (x, x + c x^{1/5} \log x] contains a square-free integer for sufficiently large x. This exponent of \frac{1}{5} = 0.2 was improved in 2024 by Pandey, who showed that for some \eta > 0, every interval (x, x + x^{1/5 - \eta}] contains a square-free integer for sufficiently large x.[30] Constructions for lower bounds on maximal gaps typically employ the Chinese Remainder Theorem to engineer intervals devoid of square-free numbers. For instance, to create a gap of length at least g, solve the system of congruences m \equiv -k \pmod{p_k^2} for k = 0, 1, \dots, g-1, where p_k are the first r primes and r is chosen appropriately; this ensures each integer in [m, m+g-1] is divisible by some p^2. This construction shows that there exist infinitely many such intervals with h \gg \frac{\log x}{\log \log x}, demonstrating that maximal gaps grow at least like \log x / \log \log x. More refined constructions yield gaps of size \Omega\left( \frac{\log x \log \log \log x}{\log \log x} \right).[31] Recent work has focused on making these upper bounds explicit. In 2023, McNew et al. provided the first explicit version of the Filaseta-Trifonov bound, proving that for any x \geq 2, every interval (x, x + 11 x^{1/5} \log x] contains a square-free integer, with the constant 11 improvable for very large x.[32] This result builds on the original method while incorporating numerical optimizations for practical verification. Ongoing research continues to explore tighter exponents.Distribution and Computation
Computation of the Counting Function Q(x)
The counting function Q(x), which enumerates the number of square-free positive integers not exceeding x, admits the exact formula Q(x) = \sum_{n \le x} |\mu(n)| = \sum_{k=1}^{\lfloor \sqrt{x} \rfloor} \mu(k) \left\lfloor \frac{x}{k^2} \right\rfloor, where \mu denotes the Möbius function.[33] This expression arises from applying Möbius inversion to the characteristic function of square-free integers, which equals |\mu(n)|. For computational purposes, the summation is truncated at k = \lfloor \sqrt{x} \rfloor, as the floor function \left\lfloor x / k^2 \right\rfloor vanishes for larger k.[33] The values of \mu(k) up to \sqrt{x} can be precomputed efficiently using a linear sieve variant of the Sieve of Eratosthenes, which identifies square-free k and counts their distinct prime factors in O(\sqrt{x}) time overall. A naive evaluation of the sum requires O(\sqrt{x}) arithmetic operations after sieving, making it suitable for moderate x. For larger x, optimizations such as input segmentation—dividing the sum into blocks—or adaptations of the Dirichlet hyperbola method can accelerate computation by exploiting symmetries in the floor terms, achieving sublinear time relative to x in practice.[34] Tables of Q(x) for large x (up to $10^{10} or more) have been computed using these summation-based methods since the 1960s, leveraging early electronic computers to verify asymptotic behaviors and error estimates.[35]Tables of Q(x), 6/π² x, and Relative Error
The counting function Q(x), which enumerates the number of square-free integers up to x, is asymptotically approximated by \frac{6}{\pi^2} x, where \frac{6}{\pi^2} \approx 0.607927101854. To illustrate the accuracy of this approximation, the following table presents values for x = 10^k with k = 1 to $10, including Q(x), the approximation \frac{6}{\pi^2} x, and the normalized error measure R(x) = \frac{|Q(x) - \frac{6}{\pi^2} x|}{\sqrt{x}}. These data are sourced from the On-Line Encyclopedia of Integer Sequences (OEIS) A071172.[36]| k | x = 10^k | Q(x) | \frac{6}{\pi^2} x | R(x) |
|---|---|---|---|---|
| 1 | 10 | 7 | 6.07927101854 | 0.291 |
| 2 | 100 | 61 | 60.7927101854 | 0.0207 |
| 3 | 1000 | 608 | 607.927101854 | 0.00231 |
| 4 | 10000 | 6083 | 6079.27101854 | 0.0373 |
| 5 | 100000 | 60794 | 60792.7101854 | 0.00408 |
| 6 | 1000000 | 607926 | 607927.101854 | 0.00110 |
| 7 | 10000000 | 6079291 | 6079271.01854 | 0.00632 |
| 8 | 100000000 | 60792694 | 60792710.1854 | 0.00162 |
| 9 | 1000000000 | 607927124 | 607927101.854 | 0.000700 |
| 10 | 10000000000 | 6079270942 | 6079271018.5403 | 0.000766 |
Algorithms for Testing and Decomposition
To test whether an integer n is square-free, one standard deterministic approach is trial division: for each prime p \leq \sqrt{n}, check if p^2 divides n; if no such p exists, then n is square-free.[1] This method runs in O(\sqrt{n}) time, which is feasible for moderate-sized n but impractical for large cryptographic integers. An alternative deterministic check computes \gcd(n, \prod_{p \leq \sqrt{n}} p^2); if the result is 1, then n is square-free, though constructing the product requires significant preprocessing and remains inefficient for large n.[38] Probabilistic methods can accelerate testing by first applying compositeness tests like Miller-Rabin to identify potential prime factors, followed by verifying that no prime squares divide n.[11] However, fully confirming square-freeness generally requires complete factorization, as partial factorization may miss higher powers. There is no known polynomial-time deterministic algorithm for testing square-freeness or extracting the square-free part of an integer, and the problem is believed to be as hard as integer factorization.[11] Under the Generalized Riemann Hypothesis (GRH), an algorithm using the explicit formula for L-functions can certify square-freeness in subexponential time by bounding the number of small prime factors via analytic estimates.[39] For square-free decomposition—expressing n = k \cdot m^2 where k is square-free (the square-free part of n)—standard methods rely on full factorization using algorithms like the Elliptic Curve Method (ECM) for small factors or the Number Field Sieve (NFS) for large semiprimes, followed by removing squared factors from the prime factorization.[11] ECM is particularly effective for finding factors up to 50-60 digits, with expected running time O(\exp(c \sqrt{\log p \log \log p})) for a prime factor p, while NFS achieves subexponential time O(\exp(c (\log n)^{1/3} (\log \log n)^{2/3})) for general n. Recent advances leverage class groups of binary quadratic forms to compute the decomposition directly without full factorization. In a 2023 algorithm, the square-free part and square part are found by solving representation problems in the class group of discriminant -4ab (where n = a b^2) using reduction and composition operations, achieving heuristic expected time O(\log^4 n) under GRH for class group computations.[40] This class group method has applications in cryptography, particularly for generating square-free discriminants in protocols based on ideal class groups of quadratic fields, such as the CSIDH key exchange, where efficient decomposition ensures secure parameter selection without exposing full factorizations.[40]Representations and Conjectures
Encoding as Binary Numbers
Square-free integers admit a natural encoding as binary strings, where the bits indicate the presence or absence of specific primes in their factorization. The primes are ordered increasingly as p_1 = 2, p_2 = [3](/page/3), p_3 = 5, and so on. For a square-free integer n = \prod_{i \in S} p_i, where S is a finite set of indices, the corresponding binary string has a 1 in the i-th position if i \in S and 0 otherwise. The number 1, being the empty product, corresponds to the all-zero string. This mapping establishes a bijection between the positive square-free integers and the binary numbers with finite support (i.e., only finitely many 1-bits). By the fundamental theorem of arithmetic, every finite subset of primes corresponds uniquely to a square-free integer via their product, and vice versa for square-free integers greater than 1. The bijection facilitates systematic enumeration of square-free integers by generating all binary strings of increasing length and computing the product of primes at positions with 1-bits. For instance:- The string $0\ldots0 (all zeros) maps to 1.
- \ldots001 (1 in binary) maps to p_1 = 2.
- \ldots010 (2 in binary) maps to p_2 = 3.
- \ldots011 (3 in binary) maps to $2 \times 3 = 6.
- \ldots100 (4 in binary) maps to p_3 = 5.