In mathematics, a square-free, or quadratfrei (from German language) integer, is an integer which is divisible by no other perfect square than 1. For example, 10 is square-free but 18 is not, as 18 is divisible by 9 = 32. The smallest positive square-free numbers are
Contents
- Square free factors of integers
- Equivalent characterizations
- Dirichlet generating function
- Distribution
- Encoding as binary numbers
- Erds squarefree conjecture
- Squarefree core
- References
Square-free factors of integers
The radical of an integer is its largest square-free factor. An integer is square-free if and only if it is equal to its radical.
Any arbitrary positive integer n can be represented in a unique way as the product of a powerful number and a square-free integer, which are coprime. The square-free factor is the largest square-free divisor k of n that is coprime with n/k.
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 m2 is a divisor of n.
Equivalent characterizations
Every prime number is square-free.
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 all of them are 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 / nZ (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 / kZ 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.
A positive integer n is squarefree if and only if
This results from the properties of Möbius function, and the fact that this sum is equal to
Dirichlet generating function
The Dirichlet generating function for the square-free numbers is
This is easily seen from the Euler product
Distribution
Let Q(x) denote the number of square-free integers between 1 and x. 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 events are independent, we obtain the approximation:
This argument can be made rigorous, and a very elementary estimate yields
(see pi and big O notation) since we use the above characterization to obtain
and, observing that the last summand is zero for
By exploiting the largest known zero-free region of the Riemann zeta function, due to Ivan Matveyevich Vinogradov, N.M. Korobov and Hans-Egon Richert, the maximal size of the error term has been reduced by Arnold Walfisz and we have
for some positive constant c. Under the Riemann hypothesis, the error term can be further reduced to yield
The asymptotic/natural density of square-free numbers is therefore
where ζ is the Riemann zeta function and 1/ζ(2) is approximately 0.6079. 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=22, it cannot occur that four consecutive integers are all square-free. On the other hand, there exist infinitely many integers n for which 4n +1, 4n +2, 4n +3 are all square-free. Otherwise, observing that 4n and at least one of 4n +1, 4n +2, 4n +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
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
Encoding as binary numbers
If we represent a square-free number as the infinite product
then we may take those
The square-free number 42 has factorization 2 × 3 × 7, or as an infinite product 21 · 31 · 50 · 71 · 110 · 130 ··· Thus the number 42 may be encoded as the binary sequence ...001011 or 11 decimal. (Note that 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 20 · 31 · 50 · 71 · 110 · 131 = 3 × 7 × 13 = 273.
Thus the in-order encodings of the square-free integers are a permutation of the set of all 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, and for all integers > 4 in 1996 by Olivier Ramaré and Andrew Granville.
Squarefree core
The multiplicative function
The value set of
OEIS representatives are A007913 (t=2), A050985 (t=3) and A053165 (t=4).