We call a monic polynomial square-free mod if there are no polynomials such that being non-constant and
Given a prime and integer . Find the number of monic square-free mod polynomials with degree and coefficients in .
Solution
The answer is for , for and for .
Note that is a unique factorization domain. So any monic can be uniquely expressed as , where are monic polynomials and is square-free. Let be the number of all square-free monic polynomials of with degree . Any non-square-free monic polynomial can be expressed as where is a square-free monic polynomial.
If , then . We have options for and options for . So
And by simple induction on we get .
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.