Square-free integer

In mathematics, a square-free integer (or squarefree integer) is an integer that 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

Square-free factorization

Every positive integer

n

{\displaystyle n}

can be factored in a unique way as

n

=

∏

i

=

1

k

q

i

i

,

{\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},}

where the

q

i

{\displaystyle q_{i}}

different from 1 are square-free integers that are pairwise coprime.

This is called the square-free factorization of n.

To construct the square-free factorization, let

n

=

∏

j

=

1

h

p

j

e

j

{\displaystyle n=\prod _{j=1}^{h}p_{j}^{e_{j}}}

be the prime factorization of

n

{\displaystyle n}

, where the

p

j

{\displaystyle p_{j}}

are distinct prime numbers. Then the factors of the square-free factorization are defined as

q

i

=

∏

j

:

e

j

=

i

p

j

.

{\displaystyle q_{i}=\prod _{j:e_{j}=i}p_{j}.}

An integer is square-free if and only if

q

i

=

1

{\displaystyle q_{i}=1}

for all

i

>

1

{\displaystyle i>1}

. An integer greater than one is the

k

{\displaystyle k}

th power of another integer if and only if

k

{\displaystyle k}

is a divisor of all

i

{\displaystyle i}

such that

q

i

≠

1.

{\displaystyle q_{i}\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.