From Wikipedia, the free encyclopedia

Divisibility-based sets of integers

Form of factorization:

Prime number

Composite number

Powerful number

Square-free number

Achilles number

Constrained divisor sums:

Perfect number

Almost perfect number

Quasiperfect number

Multiply perfect number

Hyperperfect number

Unitary perfect number

Semiperfect number

Primitive semiperfect number

Practical number

Numbers with many divisors:

Abundant number

Highly abundant number

Superabundant number

Colossally abundant number

Highly composite number

Superior highly composite number

Other:

Deficient number

Weird number

Amicable number

Friendly number

Sociable number

Solitary number

Sublime number

Harmonic divisor number

Frugal number

Equidigital number

Extravagant number

See also:

Divisor function

Divisor

Prime factor

Factorization

In mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 3². The smallest 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 OEIS)

Contents 1 Equivalent characterizations of square-free numbers 2 Distribution of square-free numbers 3 Encoding as Binary Numbers 4 Erdős Squarefree Conjecture

The positive integer n is square-free if and only if in the prime factorization of n, no prime number occurs more than once. Another way of stating the same is that for every prime multiple p of n, the prime p does not divide n / p. Yet another formulation: n is square-free if and only if in every factorization n=ab, the factors a and b are coprime.

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

The 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.

The 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.

The radical of an integer is always square-free.

If Q(x) denotes the number of square-free integers between 1 and x, then

(see pi and big O notation). The asymptotic/natural density of square-free numbers is therefore

where ζ is the Riemann zeta function.

Likewise, if Q(x,n) denotes the number of nth power-free integers between 1 and x, one can show

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

, and p_n is the nth prime.

then we may take those a_n and use them as bits in a binary number, i.e. with the encoding:

e.g. The square-free number 42 has factorisation 2 × 3 × 7, or as an infinite product: 2¹ · 3¹ · 5⁰ · 7¹ · 11⁰ · 13⁰ ·...; 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 factorisation of every number is unique, so then 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 become 2⁰ · 3¹ · 5⁰ · 7¹ · 11⁰ · 13¹ = 3 × 7 × 13 = 273.

Among other things, this implies that the set of all square-free integers has the same cardinality as the set of all integers. In turn that leads to the fact that the in-order encodings of the square-free integers are a permutation of the set of all integers.

See sequences A048672 and A064273 in the OEIS

The central binomial coefficient

is never squarefree for n > 4. This was proven in 1996 by Olivier Ramaré and Andrew Granville.