In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, is square-free, but is not, because 18 is divisible by . The smallest positive square-free numbers are
Every positive integer
n
qi
To construct the square-free factorization, let be the prime factorization of
n
pj
An integer is square-free if and only if
qi=1
i>1
k
k
i
qi ≠ 1.
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.
The radical of an integer is its largest square-free factor, that is
k | |
style\prod | |
i=1 |
qi
Every positive integer
n
q1,
k | |
style\prod | |
i=2 |
i. | |
q | |
i |
The square-free part of
n
q1,
k
n
n/k
k | |
style\prod | |
i=1 |
qi.
Any arbitrary positive integer
n
m
n
m2
n
In summary, there are three square-free factors that are naturally associated to every integer: the square-free part, the above factor
k
n
p1,\ldots,ph
For example, if
n=75600=24 ⋅ 33 ⋅ 52 ⋅ 7,
q1=7, q2=5, q3=3, q4=2.
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]
A positive integer
n
n
p
n
p
n/p
n
n=ab
a
b
A positive integer
n
n
A integer
n
Z/nZ
Z/kZ
k
For every positive integer
n
n
n
A positive integer
n
\mu(n)\ne0
\mu
The absolute value of the Möbius function is the indicator function for the square-free integers - that is, is equal to 1 if is square-free, and 0 if it is not. The Dirichlet series of this indicator function is
infty | |
\sum | |
n=1 |
|\mu(n)| | |
ns |
=
\zeta(s) | |
\zeta(2s) |
,
\zeta(s) | |
\zeta(2s) |
=\prodp
(1-p-2s) | |
(1-p-s) |
=\prodp(1+p-s),
Let Q(x) denote the number of square-free integers between 1 and x (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:
\begin{align}Q(x)& ≈ x\prodp prime\left(1-
1 | |
p2 |
\right)=x\prodp prime
1 | ||||
|
\\ &=x\prodp prime
1 | |||||||
|
=
x | ||||||||||||
|
=
x | |
\zeta(2) |
=
6x | |
\pi2 |
.\end{align}
This argument can be made rigorous for getting the estimate (using big O notation)
Q(x)=
6x | |
\pi2 |
+O\left(\sqrt{x}\right).
Sketch of a proof: the above characterization gives
Q(x)=\sumn\leq
\sum | |
d2\midn |
\mu(d)=\sumd\leq
\mu(d)\sum | |
n\leqx,d2\midn |
1=\sumd\leq\mu(d)\left\lfloor
x | |
d2 |
\right\rfloor;
d>\sqrt{x}
\begin{align}Q(x)&=\sumd\leq\sqrt{x
By exploiting the largest known zero-free region of the Riemann zeta function Arnold Walfisz improved the approximation to[4]
Q(x)=
6x | |
\pi2 |
+O\left(x1/2\exp\left(-c
(logx)3/5 | |
(loglogx)1/5 |
\right)\right),
Under the Riemann hypothesis, the error term can be reduced to[5]
Q(x)=
x | |
\zeta(2) |
+O\left(x17/54+\varepsilon\right)=
6 | |
\pi2 |
x+O\left(x17/54+\varepsilon\right).
In 2015 the error term was further reduced (assuming also Riemann hypothesis) to[6]
Q(x)=
6 | |
\pi2 |
x+O\left(x11/35+\varepsilon\right).
The asymptotic/natural density of square-free numbers is therefore
\limx\toinfty
Q(x) | |
x |
=
6 | |
\pi2 |
≈ 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[7]
Q(x,n)=
x | ||||||||||||
|
+O\left(\sqrt[n]{x}\right)=
x | |
\zeta(n) |
+O\left(\sqrt[n]{x}\right).
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
Q(x)\leq
x | |
2 |
+C
Q(x)
There exist sequences of consecutive non-square-free integers of arbitrary length. Indeed, if n satisfies a simultaneous congruence
n\equiv
2} | |
-i\pmod{p | |
i |
(i=1,2,\ldots,l)
p1,p2,\ldots,pl
n+i
Q(x)=6x/\pi2+O\left(\sqrt{x}\right)
x+c\sqrt{x}
x+c\sqrt{x}
x+cx1/5logx.
x+xo(1)
The table shows how
Q(x)
6 | |
\pi2 |
x
R(x)=Q(x)-
6 | |
\pi2 |
x
\Delta(x)
x | Q(x) |
x | R(x) | |||
---|---|---|---|---|---|---|
10 | 7 | 6.1 | 0.9 | |||
102 | 61 | 60.8 | 0.2 | |||
103 | 608 | 607.9 | 0.1 | |||
104 | 6,083 | 6,079.3 | 3.7 | |||
105 | 60,794 | 60,792.7 | 1.3 | |||
106 | 607,926 | 607,927.1 | ||||
107 | 6,079,291 | 6,079,271.0 | 20.0 | |||
108 | 60,792,694 | 60,792,710.2 | ||||
109 | 607,927,124 | 607,927,101.9 | 22.1 | |||
1010 | 6,079,270,942 | 6,079,271,018.5 | ||||
1011 | 60,792,710,280 | 60,792,710,185.4 | 94.6 | |||
1012 | 607,927,102,274 | 607,927,101,854.0 | 420.0 | |||
1013 | 6,079,271,018,294 | 6,079,271,018,540.3 | ||||
1014 | 60,792,710,185,947 | 60,792,710,185,402.7 | 544.3 | |||
1015 | 607,927,101,854,103 | 607,927,101,854,027.0 | 76.0 | |||
R(x)
x
The absolute value of
R(x)
x
If we represent a square-free number as the infinite product
infty | |
\prod | |
n=0 |
(pn+1
an | |
) |
,an\in\lbrace0,1\rbrace,andpnisthenthprime,
then we may take those
an
infty | |
\sum | |
n=0 |
{an} ⋅ 2n.
The square-free number 42 has factorization, or as an infinite product 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
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.)
The central binomial coefficient
{2n\choosen}
is never squarefree for n > 4. This was proven in 1985 for all sufficiently large integers by András Sárközy,[12] and for all integers > 4 in 1996 by Olivier Ramaré and Andrew Granville.[13]
Let us call "t-free" a positive integer that has no t-th power in its divisors. In particular, the 2-free integers are the square-free integers.
coret(n)
e) | |
core | |
t(p |
=pe\bmod.
The integer
coret(n)
coret.
The Dirichlet generating function of the sequence
\left(coret(n)\right)n\in
\sumn\ge
coret(n) | |
ns |
=
\zeta(ts)\zeta(s-1) | |
\zeta(ts-t) |
See also (t=2), (t=3) and (t=4).