Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Square-free integer
Summary
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, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 32. The smallest positive square-free numbers are
Every positive integer can be factored in a unique way as
where the different from one are square-free integers that are pairwise coprime.
This is called the square-free factorization of n.
To construct the square-free factorization, let
be the prime factorization of , where the are distinct prime numbers. Then the factors of the square-free factorization are defined as
An integer is square-free if and only if for all . An integer greater than one is the th power of another integer if and only if is a divisor of all such that
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 with notation of the preceding section. An integer is square-free if and only if it is equal to its radical.
Every positive integer 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 and the powerful number is
The square-free part of is which is the largest square-free divisor of that is coprime with .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (47)