Olympiad Maths Prep

Library / /23 of 29

Algebra Difficulty 6.7 National olympiad Prove it Iran

We call a monic polynomial P(x)Z[x]P(x) \in \mathbb{Z}[x] square-free mod nn if there are no polynomials Q(x),R(x)Z[x]Q(x), R(x) \in \mathbb{Z}[x] such that QQ being non-constant and
P(x)Q(x)2R(x)(modn). P(x) \equiv Q(x)^2 R(x) \pmod{n}.
Given a prime pp and integer m2m \ge 2. Find the number of monic square-free mod pp polynomials P(x)P(x) with degree mm and coefficients in {0,1,2,3,,p1}\{0, 1, 2, 3, \dots, p-1\}.

Solution

The answer is 11 for m=0m = 0, pp for m=1m = 1 and φ(pm)\varphi(p^m) for m>1m > 1.

Note that Zp[x]\mathbb{Z}_p[x] is a unique factorization domain. So any monic P(x)Zp[x]P(x) \in \mathbb{Z}_p[x] can be uniquely expressed as P(x)A(x)2Q(x)(modp)P(x) \equiv A(x)^2 Q(x) \pmod{p}, where A(x),Q(x)A(x), Q(x) are monic polynomials and Q(x)Q(x) is square-free. Let fnf_n be the number of all square-free monic polynomials of Zp[x]\mathbb{Z}_p[x] with degree nn. Any non-square-free monic polynomial can be expressed as P(x)=A(x)2S(x)P(x) = A(x)^2 S(x) where S(x)S(x) is a square-free monic polynomial.

If degA(x)=m\deg A(x) = m, then S(x)fn2mS(x) \in f_{n-2m}. We have fn2mf_{n-2m} options for S(x)S(x) and pmp^m options for A(x)A(x). So
fn=pnm=1n2fn2mpm. f_n = p^n - \sum_{m=1}^{\lfloor \frac{n}{2} \rfloor} f_{n-2m} p^m.
And by simple induction on nn we get fn=φ(pn)f_n = \varphi(p^n).

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.