= Square-free integer
{wiki}
= Squarefree integer
{synonym}
= Squarefree
{synonym}
= Squarefreeness
{synonym}
A <positive integer> $n$ is \b[square-free] when no <square number> greater than one is a <divisor> of $n$. It suffices to exclude squares of <prime numbers>; equivalently, every <prime valuation> is zero or one:
$$
n\text{ is square-free}\quad\Longleftrightarrow\quad
p^2\nmid n\text{ for every prime }p
\quad\Longleftrightarrow\quad v_p(n)\in\{0,1\}\text{ for every prime }p.
$$
Thus the <prime factorization> of a <square-free integer> is a <product> of distinct <prime factors>, with no repetitions. One is included: its <prime factorization> is an <empty product> and all its <prime valuations> are zero. These equivalent tests are stated in Grinberg's notes. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781, Floor and arithmetic functions, Definition 2.1.2 and footnote 6]{ref}
For signed <integers>, extend the definition by requiring $|n|$ to be a <square-free integer>, where $|n|$ denotes <absolute value>. Hence $-30$ and both $1,-1$ qualify. Zero does not: every <prime number> has its square as a <divisor> of zero. The <Möbius function> and <radical of an integer> below use their existing <positive integer> domains, so apply them to $|n|$ when handling a negative <integer>.
For example, $30=2\cdot3\cdot5$ is a <square-free integer>, whereas $12=2^2\cdot3$ is not, because $4\mid12$ and $v_2(12)=2$. Being a <composite number> causes no problem: $6,10,15$ are all <square-free integers>. A <square-free integer> need not be <coprime> to another <integer>: $6$ and $10$ are both <square-free integers> but have <greatest common divisor> two. In fact the only signed <integers> <coprime> to every <integer> are $1,-1$, since $\gcd(n,n)=|n|$.
\Image[/coprime-squarefree-integers-square-sieve.png]
{title=Exact <square-free integer> classification of the <integers> from one to sixty}
{description=Green cells are <square-free integers>; each red cell displays a <prime number> square that divides its label, choosing the smallest such <prime number>. Only $4,9,25,49$ need testing in this range. There are $37$ green cells. This original finite arithmetic diagram is an exact enumeration, not a measurement or an assertion about a limiting frequency.}
For <positive integers> $a,b$, the useful <product> criterion is
$$
ab\text{ is square-free}\quad\Longleftrightarrow\quad
a,b\text{ are square-free and }\gcd(a,b)=1.
$$
The proof outline is just <addition> of <prime valuations>: $v_p(ab)=v_p(a)+v_p(b)$ can stay at most one only if neither input repeats a <prime factor> and no <prime factor> occurs in both. Thus $6\cdot5=30$ is a <square-free integer>, but $6\cdot10=60$ is not. An equivalent characterization is that \b[every] factorization $n=ab$ into <positive integers> has <coprime> factors. If $p^2\mid n$, the factorization $n=p(n/p)$ supplies two factors sharing $p$; conversely, a shared <prime factor> forces its square to divide $n$. For $30$, the unordered factor pairs $(1,30),(2,15),(3,10),(5,6)$ all have <greatest common divisor> one; for $12$, the pair $(2,6)$ fails.
Two existing <arithmetic functions> turn the definition into practical tests:
$$
\operatorname{rad}(n)=n\quad\Longleftrightarrow\quad n\text{ is square-free},\qquad
\mu(n)^2=\begin{cases}1&n\text{ is square-free},\\0&\text{otherwise},\end{cases}\qquad n>0.
$$
The <radical of an integer> keeps one copy of each <prime factor>, so it changes precisely the <integers> with a repeated <prime factor>. Its definition is given in Evertse's exercise sheet. https://pub.math.leidenuniv.nl/~evertsejh/dio12-ex4.pdf[Jan-Hendrik Evertse, Diophantine approximation, Homework IV, Exercise 20]{ref} The <Möbius function> assigns $(-1)^r$ to a <square-free integer> with $r$ distinct <prime factors> and zero otherwise; squaring forgets the sign. Consequently $\sum_{n=1}^{60}\mu(n)^2=37$ counts exactly the green cells. This connects a restriction on repeated <prime factors> with weighted counting and <inclusion-exclusion>. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781, Definition 2.1.2: the Möbius function]{ref}
Back to article page
