galois.is_square_free(value: int) → bool
galois.is_square_free(value: Poly) → bool

Determines if an integer or polynomial is square-free.

Parameters:
value: int
value: Poly

An integer \(n\) or polynomial \(f(x)\).

Returns:

True if the integer or polynomial is square-free.

See also

is_prime_power, is_perfect_power

Notes

A square-free integer \(n\) is divisible by no perfect squares. As a consequence, the prime factorization of a square-free integer \(n\) is

\[n = \prod_{i=1}^{k} p_i^{e_i} = \prod_{i=1}^{k} p_i .\]

A square-free polynomial \(f(x)\) has no irreducible factors with multiplicity greater than one. Therefore, its canonical factorization is

\[f(x) = \prod_{i=1}^{k} g_i(x)^{e_i} = \prod_{i=1}^{k} g_i(x) .\]

This test is also available in Poly.is_square_free().

Examples

Determine if integers are square-free.

In [1]: galois.is_square_free(10)
Out[1]: True

In [2]: galois.is_square_free(18)
Out[2]: False

Generate irreducible polynomials over \(\mathrm{GF}(3)\).

In [3]: GF = galois.GF(3)

In [4]: f1 = galois.irreducible_poly(3, 3); f1
Out[4]: Poly(x^3 + 2x + 1, GF(3))

In [5]: f2 = galois.irreducible_poly(3, 4); f2
Out[5]: Poly(x^4 + x + 2, GF(3))

Determine if composite polynomials are square-free over \(\mathrm{GF}(3)\).

In [6]: galois.is_square_free(f1 * f2)
Out[6]: True

In [7]: galois.is_square_free(f1**2 * f2)
Out[7]: False