Editing Square-free integer (section)

==Square-free factorization==
Every positive integer <math>n</math> can be factored in a unique way as
<math display=block>n=\prod_{i=1}^k q_i^i,</math>
where the <math>q_i</math> 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
<math display=block>n=\prod_{j=1}^h p_j^{e_j}</math> 
be the [[prime factorization]] of <math>n</math>, where the <math>p_j</math> are distinct [[prime number]]s. Then the factors of the square-free factorization are defined as 
<math display=block>q_i=\prod_{j: e_j=i}p_j.</math>

An integer is square-free if and only if <math>q_i=1</math> for all <math>i > 1</math>. An integer greater than one is the <math>k</math>th power of another integer if and only if <math>k</math> is a divisor of all <math>i</math> such that <math>q_i\neq 1.</math>

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 [[polynomial]]s 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.