We call a monic polynomial $P(x) \in \mathbb{Z}[x]$ square-free mod n if there dose not exist polynomials $Q(x),R(x) \in \mathbb{Z}[x]$ with $Q$ being non-constant and $P(x) \equiv Q(x)^2 R(x) \mod n$. Given a prime $p$ and integer $m \geq 2$. Find the number of monic square-free mod p $P(x)$ with degree $m$ and coeeficients in $\{0,1,2,3,...,p-1\}$. Proposed by Masud Shafaie
Problem
Source: Iran TST2 Day1 P1
Tags: polynomial, number theory, Iranian TST
17.03.2020 17:11
The answer is$1$ for $m=0$, $p$ for $m=1$ and $p^m-p^{m-1}$ for $m>1$. Note that $\mathbb{Z}_p[x]$ is a unique factorization domain with units ${1,2,3,...,p-1}$. So : any monic $P(x)\in \mathbb{Z}_p[x] $ can be uniquely expressed as $P(x)=A(x)^2Q(x)$ where $A(x), Q(x) $ are monic and $Q(x)$ is square-free. Let $S_n$ be the set of all square free monic elements of $\mathbb{Z}_p[x]$ of degree $n$. Any not square free monic $P$ , $(deg P) =n $, can be expressed $P(x)=A(x)^2Q(x)$ as above where $degA=d $ , $d\ge 1$ , $Q \in S_{n-2d}$ . For specific $d$ there are $p^d\cdot |S_{n-2d}|$ such non-square free polynomials and for all possible $d$ we count all non square free monic polynomials of degree $n$ and conclude that: $$|S_n|=p^n- \sum_{d\ge 1, 2d\le n} p^d\cdot |S_{n-2d}|$$that complies with $|S_0|=1, |S_1|=p, |S_n|=p^n-p^{n-1}$.
05.04.2020 02:46
I am wondering something: it is well known that the product of all monic irreducible polynomials over $\mathbb{Z}_p$ having degree dividing $n$ for some natural number $n$ is $x^{p^n}-x$, and $\phi(p^n)=p^n-p^{n-1}$, so might there be a connection to $x^{p^n}-x$ in this problem?