Editing Square-free integer (section)

==Square-free factors of integers==
The [[radical of an integer]] is its largest square-free factor, that is <math>\textstyle \prod_{i=1}^k q_i</math> with notation of the preceding section. An integer is square-free [[if and only if]] it is equal to its radical.

Every positive integer <math>n</math> 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 <math>q_1,</math> and the powerful number is <math>\textstyle \prod_{i=2}^k q_i^i.</math>

The ''square-free part'' of <math>n</math> is <math>q_1,</math> which is the largest square-free divisor <math>k</math> of <math>n</math> that is coprime with <math>n/k</math>. The square-free part of an integer may be smaller than the largest square-free divisor, which is <math>\textstyle \prod_{i=1}^k q_i.</math>

Any arbitrary positive integer <math>n</math> can be represented in a unique way as the product of a [[square]] and a square-free integer:
<math display=block> n=m^2 k</math>
In this factorization, <math>m</math> is the largest divisor of <math>n</math> such that <math>m^2</math> is a divisor of <math>n</math>.

In summary, there are three square-free factors that are naturally associated to every integer: the square-free part, the above factor <math>k</math>, 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
<math display=block>n=\prod_{i=1}^h p_i^{e_i}=\prod_{i=1}^k q_i^i</math>
are the prime factorization and the square-free factorization of <math>n</math>, where <math>p_1, \ldots, p_h</math> are distinct prime numbers, then the square-free part is
<math display=block>\prod_{e_i=1} p_i =q_1,</math>
The square-free factor such the quotient is a square is 
<math display=block>\prod_{e_i \text{ odd}} p_i=\prod_{i \text{ odd}} q_i,</math>
and the largest square-free factor is 
<math display=block>\prod_{i=1}^h p_i=\prod_{i=1}^k q_i.</math>

For example, if <math>n=75600=2^4\cdot 3^3\cdot 5^2\cdot 7,</math> one has <math>q_1=7,\; q_2=5,\;q_3=3,\;q_4=2.</math> 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 [[decision problem|determining]] whether an integer is square-free.<ref>{{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
 }}</ref>  In contrast, polynomial-time algorithms are known for [[primality testing]].<ref>{{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}}</ref> This is a major difference between the arithmetic of the integers, and the arithmetic of the [[univariate polynomial]]s, 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 [[polynomial greatest common divisor|greatest common divisor]] of the polynomial and its [[formal derivative]]).<ref>{{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}}</ref>