square-free integer

Every positive integer $n$ can be factored in a unique way as

$$n=\backslash prod\_\{i=1\}^k\; q\_i^i,$$

where the $q\_i$ different from one are square-free integers that are pairwise coprime.

This is called the square-free factorization of {{mvar|n}}.

To construct the square-free factorization, let

$$n=\backslash prod\_\{j=1\}^h\; p\_j^\{e\_j\}$$

be the prime factorization of $n$, where the $p\_j$ are distinct prime numbers. Then the factors of the square-free factorization are defined as

$$q\_i=\backslash prod\_\{j:\; e\_j=i\}p\_j.$$

An integer is square-free if and only if $q\_i=1$ for all $i\; >\; 1$. An integer greater than one is the $k$th power of another integer if and only if $k$ is a divisor of all $i$ such that $q\_i\backslash neq\; 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 $\backslash textstyle\; \backslash prod\_\{i=1\}^k\; q\_i$ with notation of the preceding section. An integer is square-free if and only if it is equal to its radical.

Every positive integer $n$ can be represented in a unique way as the product of a powerful number (that is an integer such that is divisible by the square of every prime factor) and a square-free integer, which are coprime. In this factorization, the square-free factor is $q\_1,$ and the powerful number is $\backslash textstyle\; \backslash prod\_\{i=2\}^k\; q\_i^i.$

The square-free part of $n$ is $q\_1,$ which is the largest square-free divisor $k$ of $n$ that is coprime with $n/k$. The square-free part of an integer may be smaller than the largest square-free divisor, which is $\backslash textstyle\; \backslash prod\_\{i=1\}^k\; q\_i.$

Any arbitrary positive integer $n$ can be represented in a unique way as the product of a square and a square-free integer:

$$n=m^2\; k$$

In this factorization, $m$ is the largest divisor of $n$ such that $m^2$ is a divisor of $n$.

In summary, there are three square-free factors that are naturally associated to every integer: the square-free part, the above factor $k$, and the largest square-free factor. Each is a factor of the next one. All are easily deduced from the prime factorization or the square-free factorization: if

$$n=\backslash prod\_\{i=1\}^h\; p\_i^\{e\_i\}=\backslash prod\_\{i=1\}^k\; q\_i^i$$

are the prime factorization and the square-free factorization of $n$, where $p\_1,\; \backslash ldots,\; p\_h$ are distinct prime numbers, then the square-free part is

$$\backslash prod\_\{e\_i=1\}\; p\_i\; =q\_1,$$

The square-free factor such the quotient is a square is

$$\backslash prod\_\{e\_i\; \backslash text\{\; odd\}\}\; p\_i=\backslash prod\_\{i\; \backslash text\{\; odd\}\}\; q\_i,$$

and the largest square-free factor is

$$\backslash prod\_\{i=1\}^h\; p\_i=\backslash prod\_\{i=1\}^k\; q\_i.$$

For example, if $n=75600=2^4\backslash cdot\; 3^3\backslash cdot\; 5^2\backslash cdot\; 7,$ one has $q\_1=7,\backslash ;\; q\_2=5,\backslash ;q\_3=3,\backslash ;q\_4=2.$ The square-free part is {{math|7}}, the square-free factor such that the quotient is a square is {{math|1=3 ⋅ 7 = 21}}, and the largest square-free factor is {{math|1=2 ⋅ 3 ⋅ 5 ⋅ 7 = 210}}.

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.{{cite conference

| last1 = Adleman | first1 = Leonard M.

| last2 = McCurley | first2 = Kevin S.

| editor1-last = Adleman | editor1-first = Leonard M.

| editor2-last = Huang | editor2-first = Ming-Deh A.

| contribution = Open problems in number theoretic complexity, II

| doi = 10.1007/3-540-58691-1_70

| pages = 291–322

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, May 6–9, 1994, Proceedings

| volume = 877

| year = 1994| isbn = 978-3-540-58691-3

}} In contrast, polynomial-time algorithms are known for primality testing.{{Cite journal|last1=Agrawal|first1=Manindra|last2=Kayal|first2=Neeraj|last3=Saxena|first3=Nitin|date=1 September 2004|title=PRIMES is in P|journal=Annals of Mathematics|language=en-US|volume=160|issue=2|pages=781–793|doi=10.4007/annals.2004.160.781|doi-access=free|issn=0003-486X|mr=2123939|zbl=1071.11070|url=https://www.cse.iitk.ac.in/users/manindra/algebra/primality_original.pdf}} 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).{{cite thesis |last=Richards |first=Chelsea |title=Algorithms for factoring square-free polynomials over finite fields |type=Master's thesis |publisher=Simon Fraser University |location=Canada |year=2009 |url=http://www.cecm.sfu.ca/CAG/theses/chelsea.pdf}}

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 any such group is cyclic. This follows from the classification of finitely generated abelian groups.

A integer $n$ is square-free if and only if the factor ring $\backslash mathbb\{Z\}/n\backslash mathbb\{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 $\backslash mathbb\{Z\}/k\backslash mathbb\{Z\}$ is a field if and only if $k$ is 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 $\backslash mu(n)\backslash ne\; 0$, where $\backslash mu$ denotes the Möbius function.

The absolute value of the Möbius function is the indicator function for the square-free integers – that is, {{math|{{mabs|μ(n)}}}} is equal to 1 if {{mvar|n}} is square-free, and 0 if it is not. The Dirichlet series of this indicator function is

:$\backslash sum\_\{n=1\}^\{\backslash infty\}\backslash frac$

where {{math|ζ(s)}} is the Riemann zeta function. This follows from the Euler product

:$\backslash frac\{\backslash zeta(s)\}\{\backslash zeta(2s)\; \}\; =\backslash prod\_p\; \backslash frac\{(1-p^\{-2s\})\}\{(1-p^\{-s\})\}=\backslash prod\_p\; (1+p^\{-s\}),$

where the products are taken over the prime numbers.

Let Q(x) denote the number of square-free integers between 1 and x ({{OEIS2C|A013928}} 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:

:

&=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)} = \frac{6x}{\pi^2}.\end{align}

This argument can be made rigorous for getting the estimate (using big O notation)

:$Q(x)\; =\; \backslash frac\{6x\}\{\backslash pi^2\}\; +\; O\backslash left(\backslash sqrt\{x\}\backslash right).$

Sketch of a proof: the above characterization gives

:$Q(x)=\backslash sum\_\{n\backslash leq\; x\}\; \backslash sum\_\{d^2\backslash mid\; n\}\; \backslash mu(d)=\backslash sum\_\{d\backslash leq\; x\}\; \backslash mu(d)\backslash sum\_\{n\backslash leq\; x,\; d^2\backslash mid\; n\}1=\backslash sum\_\{d\backslash leq\; x\}\; \backslash mu(d)\backslash left\backslash lfloor\backslash frac\{x\}\{d^2\}\backslash right\backslash rfloor;$

observing that the last summand is zero for $d>\backslash sqrt\{x\}$, it follows that

{{NumBlk|:|$Q(x)\; =\; \backslash sum\_\{d\backslash leq\backslash sqrt\{x\}\}\; \backslash mu(d)\backslash left\backslash lfloor\backslash frac\{x\}\{d^2\}\backslash right\backslash rfloor$|{{EquationRef|1}}}}

:

=x\sum_{d\leq\sqrt{x}} \frac{\mu(d)}{d^2}+O(\sqrt{x})\\

&=x\sum_{d} \frac{\mu(d)}{d^2}+O\left(x\sum_{d>\sqrt{x}}\frac{1}{d^2}+\sqrt{x}\right)

=\frac{x}{\zeta(2)}+O(\sqrt{x}).

\end{align}

By exploiting the largest known zero-free region of the Riemann zeta function Arnold Walfisz improved the approximation to{{cite book |last1=Walfisz |first1=A. |title=Weylsche Exponentialsummen in der neueren Zahlentheorie |date=1963 |publisher=VEB Deutscher Verlag der Wissenschaften |location=Berlin}}

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

for some positive constant {{math|c}}.

Under the Riemann hypothesis, the error term can be reduced toJia, 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)\; =\; \backslash frac\{x\}\{\backslash zeta(2)\}\; +\; O\backslash left(x^\{17/54+\backslash varepsilon\}\backslash right)\; =\; \backslash frac\{6\}\{\backslash pi^2\}x\; +\; O\backslash left(x^\{17/54+\backslash varepsilon\}\backslash right).$

In 2015 the error term was further reduced (assuming also Riemann hypothesis) to{{cite journal |last1=Liu |first1=H.-Q. |title=On the distribution of squarefree numbers |journal=Journal of Number Theory |date=2016 |volume=159 |pages=202–222|doi=10.1016/j.jnt.2015.07.013 |doi-access=free }}

:$Q(x)\; =\; \backslash frac\{6\}\{\backslash pi^2\}x\; +\; O\backslash left(x^\{11/35+\backslash varepsilon\}\backslash right).$

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

:$\backslash lim\_\{x\backslash to\backslash infty\}\; \backslash frac\{Q(x)\}\{x\}\; =\; \backslash frac\{6\}\{\backslash pi^2\}\backslash approx\; 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{{cite journal | first1 = E. H. | last1 = Linfoot | author-link1 = Edward Linfoot | first2 = C. J. A. | last2 = Evelyn | title = On a Problem in the Additive Theory of Numbers | journal = Mathematische Zeitschrift | date = 1929 | volume = 30 | pages = 443–448 | doi = 10.1007/BF01187781 | s2cid = 120604049 | url = https://gdz.sub.uni-goettingen.de/id/PPN266833020_0030?tify={%22pages%22:[437],%22view%22:%22info%22} }}

:$Q(x,n)\; =\; \backslash frac\{x\}\{\backslash sum\_\{k=1\}^\backslash infty\; \backslash frac\{1\}\{k^n\}\}\; +\; O\backslash left(\backslash sqrt[n]\{x\}\backslash right)\; =\; \backslash frac\{x\}\{\backslash zeta(n)\}\; +\; O\backslash left(\backslash sqrt[n]\{x\}\backslash right).$

Since a multiple of 4 must have a square factor 4=2², 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)\; \backslash leq\; \backslash frac\{x\}\{2\}+C$ for some constant C,

contrary to the above asymptotic estimate for $Q(x)$.

There exist sequences of consecutive non-square-free integers of arbitrary length. Indeed, for every tuple {{math|1=(p₁, ..., p_l)}} of distinct primes, the Chinese remainder theorem guarantees the existence of an {{mvar|n}} that satisfies the simultaneous congruence

:$n\backslash equiv\; -i\backslash pmod\{p\_i^2\}\; \backslash qquad\; (i=1,\; 2,\; \backslash ldots,\; l).$

Each {{math|1=n + i}} is then divisible by {{math|1=p{{su|b=i|p=2}}}}.{{cite book | last1= Parent | first1=D. P. |title=Exercises in Number Theory | publisher=Springer-Verlag New York | isbn=978-1-4757-5194-9 | url=https://www.springer.com/book/9780387960630 | doi=10.1007/978-1-4757-5194-9 | year=1984| series=Problem Books in Mathematics }} On the other hand, the above-mentioned estimate $Q(x)\; =\; 6x/\backslash pi^2\; +\; O\backslash left(\backslash sqrt\{x\}\backslash right)$ implies that, for some constant c, there always exists a square-free integer between x and $x+c\backslash sqrt\{x\}$ for positive x. Moreover, an elementary argument allows us to replace $x+c\backslash sqrt\{x\}$ by $x+cx^\{1/5\}\backslash log\; x.${{cite journal

| last1 = Filaseta | first1 = Michael

| last2 = Trifonov | first2 = Ognian

| doi = 10.1112/jlms/s2-45.2.215

| issue = 2

| journal = Journal of the London Mathematical Society

| mr = 1171549

| pages = 215–221

| series = Second Series

| title = On gaps between squarefree numbers. II

| volume = 45

| year = 1992}} The abc conjecture would allow $x+x^\{o(1)\}$.{{cite journal |last1=Granville |first1=Andrew |author-link=Andrew Granville |year=1998 |title=ABC allows us to count squarefrees |journal=Int. Math. Res. Not. |volume=1998 |issue=19 |pages=991–1009 |doi=10.1155/S1073792898000592 |doi-access=}}

The squarefree integers {{Math|≤ x}} can be identified and counted in {{Math|Õ(x)}} time by using a modified Sieve of Eratosthenes. If only {{Math|Q(x)}} is desired, and not a list of the numbers that it counts, then ({{EquationNote|1}}) can be used to compute {{Math|Q(x)}} in {{Math|Õ({{radical|x}})}} time. The largest known value of {{Math|Q(x)}}, for {{Math|1=x = 10³⁶}}, was computed by Jakub Pawlewicz in 2011 using an algorithm that achieves {{Math|Õ(x^2/5)}} time,{{cite arXiv |eprint=1107.4890 |last1=Pawlewicz |first1=Jakub |title=Counting Square-Free Numbers |date=2011 |class=math.NT }} and an algorithm taking {{Math|Õ(x^1/3)}} time has been outlined but not implemented.{{r|HirschKesslerMendlovic2024|at=§5.5}}

The table shows how $Q(x)$ and $\backslash frac\{6\}\{\backslash pi^2\}x$ (with the latter rounded to one decimal place) compare at powers of 10.

$R(x)\; =\; Q(x)\; -\backslash frac\{6\}\{\backslash pi^2\}x$ , also denoted as $\backslash Delta(x)$.

:

$R(x)$ changes its sign infinitely often as $x$ tends to infinity.{{cite journal |last1=Minoru |first1=Tanaka |title=Experiments concerning the distribution of squarefree numbers |journal=Proceedings of the Japan Academy, Series A, Mathematical Sciences |year=1979 |volume=55 |issue=3 |doi=10.3792/pjaa.55.101 |s2cid=121862978 |url=https://projecteuclid.org/euclid.pja/1195517398|doi-access=free }}

The absolute value of $R(x)$ is astonishingly small compared with $x$.

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

:$\backslash prod\_\{n=0\}^\backslash infty\; (p\_\{n+1\})^\{a\_n\},\; a\_n\; \backslash in\; \backslash lbrace\; 0,\; 1\; \backslash rbrace,\backslash text\{\; and\; \}p\_n\backslash text\{\; is\; the\; \}n\backslash text\{th\; prime\},$

then we may take those $a\_n$ and use them as bits in a binary number with the encoding

:$\backslash sum\_\{n=0\}^\backslash infty\; \{a\_n\}\backslash cdot\; 2^n\; .$

The square-free number 42 has factorization {{nowrap|2 × 3 × 7}}, or as an infinite product {{nowrap|2¹ · 3¹ · 5⁰ · 7¹ · 11⁰ · 13⁰ ···}} 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 {{nowrap|2⁰ · 3¹ · 5⁰ · 7¹ · 11⁰ · 13¹ {{=}} 3 × 7 × 13 {{=}} 273.}}

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\; \backslash choose\; n\}$

is never squarefree for n > 4. This was proven in 1985 for all sufficiently large integers by András Sárközy,{{cite journal

| last = Sárközy | first = A. | author-link = András Sárközy

| doi = 10.1016/0022-314X(85)90017-4 | doi-access=free

| issue = 1

| journal = Journal of Number Theory

| mr = 777971

| pages = 70–80

| title = On divisors of binomial coefficients. I

| volume = 20

| year = 1985}} and for all integers > 4 in 1996 by Olivier Ramaré and Andrew Granville.{{cite journal

| last1=Ramaré | first1=Olivier | last2=Granville | first2=Andrew

| title=Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients

| journal=Mathematika

| volume=43

| date=1996

| issue=1

| pages=73–107

| doi=10.1112/S0025579300011608}}

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.

The multiplicative function $\backslash mathrm\{core\}\_t(n)$ maps every positive integer n to the quotient of n by its largest divisor that is a t-th power. That is,

: $\backslash mathrm\{core\}\_t(p^e)\; =\; p^\{e\backslash bmod\; t\}.$

The integer $\backslash mathrm\{core\}\_t(n)$ is t-free, and every t-free integer is mapped to itself by the function $\backslash mathrm\{core\}\_t.$

The Dirichlet generating function of the sequence $\backslash left(\backslash mathrm\{core\}\_t(n)\; \backslash right)\_\{n\backslash in\; \backslash N\}$ is

: $\backslash sum\_\{n\backslash ge\; 1\}\backslash frac\{\backslash mathrm\{core\}\_t(n)\}\{n^s\}$

= \frac{\zeta(ts)\zeta(s-1)}{\zeta(ts-t)}.

See also {{OEIS2C|A007913}} (t=2), {{OEIS2C|A050985}} (t=3) and {{OEIS2C|A053165}} (t=4).

{{reflist | refs=

{{Cite journal

|last1=Hirsch

|first1=Dean

|last2=Kessler

|first2=Ido

|last3=Mendlovic

|first3=Uri

|date=2024

|title=Computing {{math|1=π(N)}}: An elementary approach in {{math|1=Õ({{radical|N}})}} time

|url=https://www.ams.org/journals/mcom/0000-000-00/S0025-5718-2024-04039-5/

|journal=Mathematics of Computation

|language=English

|arxiv=2212.09857

|doi=10.1090/mcom/4039

|issn=0025-5718

}}

}}

• {{cite book | last1=Shapiro | first1=Harold N. |title=Introduction to the theory of numbers | publisher=Oxford University Press Dover Publications | isbn=978-0-486-46669-9 | year=1983}}
• {{cite journal | first1=Andrew | last1=Granville | first2=Olivier | last2=Ramaré | title=Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients | mr=1401709 | zbl=0868.11009 | year=1996 | journal=Mathematika | volume=43 | pages=73–107 | doi=10.1112/S0025579300011608 | citeseerx=10.1.1.55.8 }}
• {{cite book |last=Guy | first=Richard K. | author-link=Richard K. Guy | title=Unsolved problems in number theory | publisher=Springer-Verlag |edition=3rd | year=2004 |isbn=978-0-387-20860-2 | zbl=1058.11001 }}
• {{cite web

|url= http://oeis.org/wiki/Squarefree_numbers

|title= OEIS Wiki

|last=

|first=

|date=

|website=

|publisher=

|access-date= September 24, 2021

|quote=}}

{{Divisor classes}}

{{Use dmy dates|date=September 2019}}

{{DEFAULTSORT:Square-Free Integer}}

Category:Number theory

Category:Integer sequences