Counting the units in a quotient ring of a polynomial ring over a field?

Question

Is there a formula to count the number of units in a polynomial ring over a field?

For instance, counting the number of units in $\mathbb{F}_3[x]/(x^3+1)$ without going one by one.

As a frame of reference for my current background, in my Classical Algebra class so far we have algebraically computed whether each possible remainder of the above ring is a unit or zero divisor. Mostly we used long division, but also by finding a simple zero divisor such as $(x+1)$ and then finding its multiples, as well as using the Division Theorem to solve for the remainder when possible.

We have defined a polynomial $g(x)$ to be a unit in $\mathbb{F}_q[x]/f(x)$ precisely when $\gcd(f,g)=1$ (or some nonzero constant), and $g(x)$ is a zero divisor when $\gcd(f,g)\neq1$ (or some nonzero constant).

Subsequently we examined the function $\varphi(m)$ (i.e. Euler's totient function) which counts the units in $\mathbb{Z}/_m\mathbb{Z}$ and defined formulas for when $m$ is prime or a prime to some power (e.g. $p^n$ for some $p$ prime and $n\geq2$).

My question is, is there a generalized definition for Euler's totient function for a polynomial ring over a field such as the example above? In other words, using my notation above, could the notion of "$\varphi(x^3+1)$" be defined in some sense analogous to integers?

Answer 1

You can proceed exactly as in the case of $\mathbb{Z}/n\mathbb{Z}$.

Fix a prime power $q$, and let $\varphi(f)$ be the cardinality of the group of units of $\mathbb{F}_q[X]/(f)$, where $f$ is a nonzero polynomial of $\mathbb{F}_q[X]$. Because of the Chinese Remainder Theorem, $$\varphi(f_1f_2)=\varphi(f_1)\varphi(f_2) \mbox { whenever }gcd(f_1,f_2)=1.$$ Hence, it is enough to compute $\varphi(\pi^r)$, where $\pi$ is irreducible and $r\geq 1$. But a polynomial is NOT coprime to $\pi^r$ if and only if it is NOT coprime to $\pi$, since $\pi$ is irreducible. Now an element of $\mathbb{F}_q[X]/(\pi^r)$ maybe represented by a unique polynomial of degree $\leq \deg(\pi^r)-1=\deg(\pi)r-1$. So we have to count the number of multiples of $\pi$ of degree $\leq \deg(\pi)r-1$. There are exactly the polynomials of the form $\pi g,$ where $\deg(g)\leq \deg(\pi)(r-1)-1$, so there are exactly $q^{\deg(\pi)(r-1)}$ such polynomials.

All in all, $$\displaystyle \varphi(\pi^r)=q^{\deg(\pi)r}-q^{\deg(\pi)(r-1)},$$

and $$\varphi(f)=\prod_{\pi\mid f}(q^{\deg(\pi)r_\pi}-q^{\deg(\pi)(r_\pi-1)})=\prod_{\pi\mid f}(q^{\deg(\pi)(r_\pi-1)}(q^{\deg(\pi)}-1)),$$ where $\pi$ runs through the irreducible monic divisors of $f$ and $r_\pi$ is the power of $\pi$ in the decomposition of $f$ into irreducible factors.

In your example, $f=X^3+1=(X+1)^3\in\mathbb{F}_3[X]$, so $\varphi(f)=3^3-3^2=18$.

Answer 2

The particular problem can be solved without lifting the machinery of Euler. By doing long division, each element in the quotient ring $\mathbb F_3[x]/(x^3+1)$ is congruent to a unique polynomial of degree $\le 2$. We want to know among them, which is invertible in the quotient.

We claim that $a+bx+cx^2+(x^3+1)$ is invertible iff $p(x)=a+bx+cx^2$ has $-1$ as a root. If it has $-1$ as a root, note that $-1$ is also a root of $x^3+1=(x+1)^3$, then the ideal $(x+1)$ contains both $p(x)$ and $(x+1)^3$, therefore they don't generate the unital ideal, so $p(x)$ is not invertible mod $(x+1)^3$. On the other hand, if $p(x)$ is a unit, then $p(x)q(x)\equiv 1 \mod (x+1)^3$, $(x+1)^3 \mid p(x)q(x)-1$, hence $p(x)q(x)-1$ has $x=-1$ as a root, and if $p(-1)=0$, $-1$ cannot be a root of $p(x)q(x)-1$.

Therefore to count units in the quotient ring is equivalen to count the number of triples $(a,b,c)\in\mathbb F_3$, such that $a-b+c\not=1$. As $a-b+c=1$ has $9$ solutions, there are $18$ such triples.

In general, let $R$ be a PID, for any ideal $I$ of $R$, $I = (p_1^{n_1} \cdots p_m^{n_m})$ for some distinct irreducible elements $p_1, \cdots, p_m$. By Chinese Remainder, $R/I\cong \prod_{i=1}^m R/(p_i^{n_i})$, hence $|(R/I)^{\times}|\cong \prod_{i=1}^m |(R/(p_i^{n_i}))^{\times}|$, and it's enough to analyze $R/(p^n)$ with the method similar to the one used earlier.

$R/(p^n)$ is a local ring with a unique maximal ideal generated by (the coset of) $p$. Therefore the number of units is equal to (assuming the residue field $R/(p)$ is finite) $$|(R/(p))^{\times}|\cdot|(p)/(p^n)|=(|R/(p)|-1)(|R/(p)|^{n-1})$$ $$=|R/(p)|^n(1-\frac{1}{|R/(p)|})$$

When $R=\mathbb Z$ and $p$ is a (positive) prime factor of $R$, then this is exactly $\phi(p^n) = p^n (1-1/p)$ as $|\mathbb Z/(p)|=p$.

To apply to our case, $I = x^3+1 = (x+1)^3$ is a primary ideal, and the residue field is $\mathbb F_3[x]/(x+1)\cong \mathbb F_3$ has three element, so the quotient $R/I$ has $3^2(1-1/3)=18$ units.

In particular, over a finite field $\mathbb F_q$, if we have $f(x) = \prod_{i=1}^m p_i(x)^{n_i}$ where $p_i(x)$'s are distinct irreducible polynomials. Then $\mathbb F_q[x]/(p_i(x))\cong \mathbb F_{q^{\deg(p_i(x))}}$, therefore $|(\mathbb F_q[x]/(f(x)))^\times|=\prod_{i=1}^m q^{\deg(p_i)n_i}(1-q^{-\deg(p_i)})$