In mathematics, a **square-free integer** (or **squarefree integer**) is an integer which is divisible by no perfect square other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 3^{2}. The smallest positive square-free numbers are

- 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, ... (sequence A005117 in the OEIS)

## Square-free factorization

Every positive integer n can be factored in a unique way as

where the different from one are square-free integers that are pairwise coprime.

This is called the *square-free factorization* of n.

Let

be the prime factorization of n, where the p_{j} are distinct prime numbers. Then the factors of the square-free factorization are defined as

An integer is square-free if and only if for all *i* > 1. An integer greater than one is the kth power of another integer if and only if k is a divisor of all i such that

The use of the square-free factorization of integers is limited by the fact that its computation is as difficult as the computation of the prime factorization. More precisely every known algorithm for computing a square-free factorization computes also the prime factorization. This is a notable difference with the case of polynomials for which the same definitions can be given, but, in this case, the square-free factorization is not only easier to compute than the complete factorization, but it is the first step of all standard factorization algorithms.

## Square-free factors of integers

The radical of an integer is its largest square-free factor, that is with notation of the preceding section. An integer is square-free if and only if it is equal to its radical.

Every positive integer n can be represented in a unique way as the product of a powerful number (that is an integer such that is divisible by the square of every prime factor) and a square-free integer, which are coprime. In this factorization, the square-free factor is and the powerful number is

The *square-free part* of n is which is the largest square-free divisor k of n that is coprime with *n*/*k*. The square-free part of an integer may be smaller than the largest square-free divisor, which is

Any arbitrary positive integer n can be represented in a unique way as the product of a square and a square-free integer:

In this factorization, m is the largest divisor of n such that *m*^{2} is a divisor of n.

In summary, there are three square-free factors that are naturally associated to every integer: the square-free part, the above factor k, and the largest square-free factor. Each is a factor of the next one. All are easily deduced from the prime factorization or the square-free factorization: if

are the prime factorization and the square-free factorization of n, where are distinct prime numbers, then the square-free part is

The square-free factor such the quotient is a square is

and the largest square-free factor is

For example, if one has The square-free part is 7, the square-free factor such that the quotient is a square is 3 ⋅ 7 = 21, and the largest square-free factor is 2 ⋅ 3 ⋅ 5 ⋅ 7 = 210.

No algorithm is known for computing any of these square-free factors which is faster than computing the complete prime factorization. In particular, there is no known polynomial-time algorithm for computing the square-free part of an integer, or even for determining whether an integer is square-free.^{[1]} In contrast, polynomial-time algorithms are known for primality testing.^{[2]} This is a major difference between the arithmetic of the integers, and the arithmetic of the univariate polynomials, as polynomial-time algorithms are known for square-free factorization of polynomials (in short, the largest square-free factor of a polynomial is its quotient by the greatest common divisor of the polynomial and its formal derivative).^{[3]}

## Equivalent characterizations

A positive integer *n* is square-free if and only if in the prime factorization of *n*, no prime factor occurs with an exponent larger than one. Another way of stating the same is that for every prime factor *p* of *n*, the prime *p* does not evenly divide *n* / *p*. Also *n* is square-free if and only if in every factorization *n* = *ab*, the factors *a* and *b* are coprime. An immediate result of this definition is that all prime numbers are square-free.

A positive integer *n* is square-free if and only if all abelian groups of order *n* are isomorphic, which is the case if and only if any such group is cyclic. This follows from the classification of finitely generated abelian groups.

A integer *n* is square-free if and only if the factor ring **Z** / *n***Z** (see modular arithmetic) is a product of fields. This follows from the Chinese remainder theorem and the fact that a ring of the form **Z** / *k***Z** is a field if and only if *k* is a prime.

For every positive integer *n*, the set of all positive divisors of *n* becomes a partially ordered set if we use divisibility as the order relation. This partially ordered set is always a distributive lattice. It is a Boolean algebra if and only if *n* is square-free.

A positive integer *n* is square-free if and only if *μ*(*n*) ≠ 0, where *μ* denotes the Möbius function.

## Dirichlet series

The absolute value of the Möbius function is the indicator function for the square-free integers – that is, |*μ*(*n*)| is equal to 1 if n is square-free, and 0 if it is not. The Dirichlet series of this indicator function is

where *ζ*(*s*) is the Riemann zeta function. This follows from the Euler product

where the products are taken over the prime numbers.

## Distribution

Let *Q*(*x*) denote the number of square-free integers between 1 and *x* (OEIS: A013928 shifting index by 1). For large *n*, 3/4 of the positive integers less than *n* are not divisible by 4, 8/9 of these numbers are not divisible by 9, and so on. Because these ratios satisfy the multiplicative property (this follows from Chinese remainder theorem), we obtain the approximation:

This argument can be made rigorous for getting the estimate (using big O notation)

*Sketch of a proof:* the above characterization gives

observing that the last summand is zero for , it results that

By exploiting the largest known zero-free region of the Riemann zeta function Arnold Walfisz improved the approximation to^{[4]}

for some positive constant *c*.

Under the Riemann hypothesis, the error term can be reduced to^{[5]}

Recently (2015) the error term has been further reduced to^{[6]}

The asymptotic/natural density of square-free numbers is therefore

Therefore over 3/5 of the integers are square-free.

Likewise, if *Q*(*x*,*n*) denotes the number of *n*-free integers (e.g. 3-free integers being cube-free integers) between 1 and *x*, one can show

Since a multiple of 4 must have a square factor 4=2^{2}, it cannot occur that four consecutive integers are all square-free. On the other hand, there exist infinitely many integers *n* for which 4*n* +1, 4*n* +2, 4*n* +3 are all square-free. Otherwise, observing that 4*n* and at least one of 4*n* +1, 4*n* +2, 4*n* +3 among four could be non-square-free for sufficiently large *n*, half of all positive integers minus finitely many must be non-square-free and therefore

- for some constant
*C*,

contrary to the above asymptotic estimate for .

There exist sequences of consecutive non-square-free integers of arbitrary length. Indeed, if *n* satisfies a simultaneous congruence

for distinct primes , then each is divisible by *p _{i }*

^{2}.

^{[7]}On the other hand, the above-mentioned estimate implies that, for some constant

*c*, there always exists a square-free integer between

*x*and for positive

*x*. Moreover, an elementary argument allows us to replace by

^{[8]}The ABC conjecture would allow .

^{[9]}

### Table of and

The table shows how and compare at powers of 10.

, also denoted as .

10 7 6.1 0.9 10 ^{2}61 60.8 0.2 10 ^{3}608 607.9 0.1 10 ^{4}6,083 6,079.3 3.7 10 ^{5}60,794 60,792.7 1.3 10 ^{6}607,926 607,927.1 - 1.3 10 ^{7}6,079,291 6,079,271.0 20.0 10 ^{8}60,792,694 60,792,710.2 - 16.2 10 ^{9}607,927,124 607,927,101.9 22.1 10 ^{10}6,079,270,942 6,079,271,018.5 - 76.5 10 ^{11}60,792,710,280 60,792,710,185.4 94.6 10 ^{12}607,927,102,274 607,927,101,854.0 420.0 10 ^{13}6,079,271,018,294 6,079,271,018,540.3 - 246.3 10 ^{14}60,792,710,185,947 60,792,710,185,402.7 544.3 10 ^{15}607,927,101,854,103 607,927,101,854,027.0 76.0

changes its sign infinitely often as tends to infinity.^{[10]}

The absolute value of is astonishingly small compared with .

## Encoding as binary numbers

If we represent a square-free number as the infinite product

then we may take those and use them as bits in a binary number with the encoding

The square-free number 42 has factorization 2 × 3 × 7, or as an infinite product 2^{1} · 3^{1} · 5^{0} · 7^{1} · 11^{0} · 13^{0} ··· Thus the number 42 may be encoded as the binary sequence `...001011` or 11 decimal. (The binary digits are reversed from the ordering in the infinite product.)

Since the prime factorization of every number is unique, so also is every binary encoding of the square-free integers.

The converse is also true. Since every positive integer has a unique binary representation it is possible to reverse this encoding so that they may be decoded into a unique square-free integer.

Again, for example, if we begin with the number 42, this time as simply a positive integer, we have its binary representation `101010`. This decodes to 2^{0} · 3^{1} · 5^{0} · 7^{1} · 11^{0} · 13^{1} = 3 × 7 × 13 =��273.

Thus binary encoding of squarefree numbers describes a bijection between the nonnegative integers and the set of positive squarefree integers.

(See sequences A019565, A048672 and A064273 in the OEIS.)

## Erdős squarefree conjecture

The central binomial coefficient

is never squarefree for *n* > 4. This was proven in 1985 for all sufficiently large integers by András Sárközy,^{[11]} and for all integers > 4 in 1996 by Olivier Ramaré and Andrew Granville.^{[12]}

## Squarefree core

The multiplicative function is defined
to map positive integers *n* to *t*-free numbers by reducing the
exponents in the prime power representation modulo *t*:

The value set of , in particular, are the square-free integers. Their Dirichlet generating functions are

- .

OEIS representatives are OEIS: A007913 (*t*=2), OEIS: A050985 (*t*=3) and OEIS: A053165 (*t*=4).

## Notes

**^**Adleman, Leonard M.; Mccurley, Kevin S. "Open Problems in Number Theoretic Complexity, II".*Lecture Notes in Computer Science*: 9. CiteSeerX 10.1.1.48.4877.**^**Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (1 September 2004). "PRIMES is in P" (PDF).*Annals of Mathematics*.**160**(2): 781–793. doi:10.4007/annals.2004.160.781. ISSN 0003-486X. MR 2123939. Zbl 1071.11070.**^**Richards, Chelsea (2009).*Algorithms for factoring square-free polynomials over finite fields*(PDF) (Master's thesis). Canada: Simon Fraser University.**^**Walfisz, A. (1963).*Weylsche Exponentialsummen in der neueren Zahlentheorie*. Berlin: VEB Deutscher Verlag der Wissenschaften.**^**Jia, Chao Hua. "The distribution of square-free numbers",*Science in China Series A: Mathematics***36**:2 (1993), pp. 154–169. Cited in Pappalardi 2003, A Survey on*k*-freeness; also see Kaneenika Sinha, "Average orders of certain arithmetical functions",*Journal of the Ramanujan Mathematical Society***21**:3 (2006), pp. 267–277.**^**Liu, H.-Q. (2016). "On the distribution of squarefree numbers".*Journal of Number Theory*.**159**: 202–222. doi:10.1016/j.jnt.2015.07.013.**^**Parent, D. P. (1984).*Exercises in Number Theory*. Problem Books in Mathematics. Springer-Verlag New York. doi:10.1007/978-1-4757-5194-9. ISBN 978-1-4757-5194-9.**^**Michael, Filaseta; Ognian, Trifonov (1992). "On gaps between squarefree numbers II".*J. London Math. Soc*. (2) 45: 215–221.**^**Andrew, Granville (1998). "ABC allows us to count squarefrees".*Int. Math. Res. Notices*.**1998**(19): 991–1009. doi:10.1155/S1073792898000592.**^**Minoru, Tanaka. "Experiments concerning the distribution of squarefree numbers".**^**András Sárközy. On divisors of binomial coefficients, I. J. Number Theory 20 (1985), no. 1, 70–80.**^**Olivier Ramaré and Andrew Granville. Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. Mathematika 43 (1996), no. 1, 73–107

## References

- Shapiro, Harold N. (1983).
*Introduction to the theory of numbers*. Oxford University Press Dover Publications. ISBN 978-0-486-46669-9. - Granville, Andrew; Ramaré, Olivier (1996). "Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients".
*Mathematika*.**43**: 73–107. CiteSeerX 10.1.1.55.8. doi:10.1112/S0025579300011608. MR 1401709. Zbl 0868.11009. - Guy, Richard K. (2004).
*Unsolved problems in number theory*(3rd ed.). Springer-Verlag. ISBN 978-0-387-20860-2. Zbl 1058.11001.