World Library  
Flag as Inappropriate
Email this Article

Square-free integer

Article Id: WHEBN0000029525
Reproduction Date:

Title: Square-free integer  
Author: World Heritage Encyclopedia
Language: English
Subject: Amicable numbers, List of unsolved problems in mathematics, Multiplicative partition, Quadratic integer, Sieve of Atkin
Collection: Integer Sequences, Number Theory
Publisher: World Heritage Encyclopedia

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 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 OEIS)


  • Equivalent characterizations 1
  • Dirichlet generating function 2
  • Distribution 3
  • Encoding as binary numbers 4
  • Erdős squarefree conjecture 5
  • Squarefree core 6
  • Notes 7
  • References 8

Equivalent characterizations

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 evenly 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. An immediate result of this definition is that all prime numbers are square-free.

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: an integer is square-free if it is equal to its radical.

Dirichlet generating function

The Dirichlet generating function for 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}).


Let Q(x) denote the number of square-free ("quadratfreie") 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:

Q(x) \approx x\prod_{p\ \text{prime}} \left(1-\frac{1}{p^2}\right) = x\prod_{p\ \text{prime}} \frac{1}{(1-\frac{1}{p^2})^{-1}}
Q(x) \approx x\prod_{p\ \text{prime}} \frac{1}{1+\frac{1}{p^2}+\frac{1}{p^4}+\cdots} = \frac{x}{\sum_{k=1}^\infty \frac{1}{k^2}} = \frac{x}{\zeta(2)}

This argument can be made rigorous, and a very elementary estimate yields

Q(x) = \frac{x}{\zeta(2)} + O\left(\sqrt{x}\right) = \frac{6x}{\pi^2} + O\left(\sqrt{x}\right)

(see pi and big O notation). By exploiting the largest known zero-free region of the Riemann zeta function, due to Ivan Matveyevich Vinogradov, M.N. Korobov and Hans-Egon Richert, the maximal size of the error term has been reduced by Arnold Walfisz[1] and we have

Q(x) = \frac{6x}{\pi^2} + O\left(x^{1/2}\exp\left(-c\frac{(\log x)^{3/5}}{(\log\log x)^{1/5}}\right)\right).

for some positive constant c. Under the Riemann hypothesis, the error term can be further reduced[2] to yield

Q(x) = \frac{x}{\zeta(2)} + O\left(x^{17/54+\varepsilon}\right) = \frac{6x}{\pi^2} + O\left(x^{17/54+\varepsilon}\right).

See the race between the number of square-free numbers up to n and round(n/ζ(2)) on the OEIS:

A158819 – (Number of square-free numbers ≤ n) minus round(n/ζ(2)). ]

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

\lim_{x\to\infty} \frac{Q(x)}{x} = \frac{6}{\pi^2} = \frac{1}{\zeta(2)}

where ζ is the Riemann zeta function and 1/ζ(2) is approximately 0.6079 (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

Q(x,n) = \frac{x}{\sum_{k=1}^\infty \frac{1}{k^n}} + O\left(\sqrt[n]{x}\right) = \frac{x}{\zeta(n)} + O\left(\sqrt[n]{x}\right).

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 \rbrace,\text{ and }p_n\text{ is the }n\text{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 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 become 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

{2n \choose n}

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

Squarefree core

The multiplicative function \mathrm{core}_t(n) is defined to map positive integers n to t-free numbers by reducing the exponents in the prime power representation modulo t:

\mathrm{core}_t(p^e) = p^{e\mod t}.

The value set of \mathrm{core}_2, in particular, are the square-free integers. Their Dirichlet generating functions are

\sum_{n\ge 1}\frac{\mathrm{core}_t(n)}{n^s} = \frac{\zeta(ts)\zeta(s-1)}{\zeta(ts-t)}.

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


  1. ^ A. Walfisz. "Weylsche Exponentialsummen in der neueren Zahlentheorie" (VEB deutscher Verlag der Wissenschaften, Berlin 1963.
  2. ^ 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, -freenesskA Survey on ; also see Kaneenika Sinha, "Average orders of certain arithmetical functions", Journal of the Ramanujan Mathematical Society 21:3 (2006), pp. 267–277.
  3. ^ András Sárközy. On divisors of binomial coefficients, I. J. Number Theory 20 (1985), no. 1, 70–80.
  4. ^ Olivier Ramaré and Andrew Granville. Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. Mathematika 43 (1996), no. 1, 73–107


  • Granville, Andrew; Ramaré, Olivier (1996). "Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients". Mathematika 43: 73–107.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.