Square-free integer


Square-free integer

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 = 32. 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, ... OEIS|id=A005117

Ring theory generalizes the concept of being square-free.

Equivalent characterizations of square-free numbers

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 factor "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 Dirichlet series that generates the square-free numbers is

: frac{zeta(s)}{zeta(2s) } = sum_{n=1}^{infty}frac{ |mu(n){n^{s where ζ("s") is the Riemann zeta function.

This is easily seen from the Euler product: frac{zeta(s)}{zeta(2s) } =prod_{p} frac{(1-p^{-2s})}{(1-p^{-s})}=prod_{p} (1+p^{-s}).

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 / "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.

The radical of an integer is always square-free.

Distribution of square-free numbers

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

:Q(x) = frac{6x}{pi^2} + Oleft(sqrt{x} ight)

(see pi and big O notation). Under the Riemann hypothesis, the error term can be reduced: [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, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf A Survey on "k"-freeness] ; also see Kaneenika Sinha, " [http://www.math.ualberta.ca/~kansinha/maxnrevfinal.pdf Average orders of certain arithmetical functions] ", "Journal of the Ramanujan Mathematical Society" 21:3 (2006), pp. 267–277.] :Q(x) = frac{6x}{pi^2} + Oleft(x^{17/54+varepsilon} ight).

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

:lim_{x oinfty} frac{Q(x)}{x} = frac{6}{pi^2} = frac{1}{zeta(2)}

where ζ is the Riemann zeta function.

Likewise, if "Q"("x","n") denotes the number of "n"-free integers between 1 and "x", one can show:Q(x,n) = frac{x}{zeta(n)} + Oleft(sqrt [n] {x} ight).

Encoding as Binary Numbers

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

:prod_{n=0}^infty {p_{n+1^{a_n}, a_n in lbrace 0, 1 brace, and p_n is the "n"th prime.

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

:sum_{n=0}^infty {a_n}cdot 2^n

e.g. The square-free number 42 has factorisation 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 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 20 · 31 · 50 · 71 · 110 · 131 = 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 and in the OEIS

Erdős Squarefree Conjecture

The central binomial coefficient

{2n choose n}

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

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Square-free — In mathematics, an element r of a unique factorization domain R is called square free if it is not divisible by a non trivial square. That is, every s such that s^2mid r is a unit of R .Square free elements may be also characterized using their… …   Wikipedia

  • Square number — In mathematics, a square number, sometimes also called a perfect square, is an integer that can be written as the square of some other integer; in other words, it is the product of some integer with itself. So, for example, 9 is a square number,… …   Wikipedia

  • Square root — Measured fall time of a small steel sphere falling from various heights. The data is in good agreement with the predicted fall time of , where h is the height and g is the acceleration of gravity. In mathematics, a square root of a number x is a… …   Wikipedia

  • Square root of 2 — The square root of 2, also known as Pythagoras constant, often denoted by:sqrt{2} or √2but can also be written as:2^{1/2},,is the positive real number that, when multiplied by itself, gives the number 2. Its numerical value approximated to 65… …   Wikipedia

  • Free abelian group — In abstract algebra, a free abelian group is an abelian group that has a basis in the sense that every element of the group can be written in one and only one way as a finite linear combination of elements of the basis, with integer coefficients …   Wikipedia

  • Algebraic integer — This article deals with the ring of complex numbers integral over Z. For the general notion of algebraic integer, see Integrality .In number theory, an algebraic integer is a complex number which is a root of some monic polynomial (leading… …   Wikipedia

  • Radical of an integer — In mathematics, the radical of a positive integer n is defined as the product of the prime numbers dividing n ::displaystylembox{rad}(n)=prod {p|n}p.,For example,:504=2^3cdot3^2cdot7 mbox{ and } mbox{rad}(504)=2cdot3cdot7=42.,The radical of any… …   Wikipedia

  • On-Line Encyclopedia of Integer Sequences — URL oeis.org Created by Neil Sloane Launched 1996 ( …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • Algebraic number field — In mathematics, an algebraic number field (or simply number field) F is a finite (and hence algebraic) field extension of the field of rational numbers Q. Thus F is a field that contains Q and has finite dimension when considered as a vector… …   Wikipedia