Cohn's criterion

Let $p$ be a prime number, and $b\geq 2$ an integer. If $\overline{p_np_{n-1}\cdotsp_1}$ (Error compiling LaTeX. Unknown error_msg) is the base- $b$ representation of $p$ , and $0\leq p_i<b$ , then $f(x)=p_nx^n+p_{n-1}x^{n-1}+\cdots+P_1x+p_0$ is irreducible.

Proof

The following proof is due to M. Ram Murty.

We start off with a lemma. Let $g(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\in \mathbb{Z}[x]$ . Suppose $a_n\geq 1$ , $a-{n-1}\geq 0$ , and $|a_i|\leq H$ . Then, any complex root of $f(x)$ , $\phi$ , has a non positive real part or satisfies $|\phi|<\frac{1+\sqrt{1+4H}}{2}$ .

Proof: If $|z|>1$ and Re $z>0$ , note that: $|\frac{g(z)}{z^n}|\geq |a_n+\frac{a_{n-1}}{z}|-H(\frac{1}{|z|^2}+\cdots+\frac{1}{|z|^n})>Re(a_n+\frac{a_{n-1}}{z})-\frac{H}{|z|^2-|z|}\geq 1-\frac{H}{|z|^2-|z|}=\frac{|z|^2-|z|-H}{|z|^2-|z|}$ This means $g(z)>0$ if $|z|\geq \frac{1+\sqrt{1+4H}}{2}$ , so $|\phi|<\frac{1+\sqrt{1+4H}}{2}$ .

If $b\geq 3$ , this implies $|b-\phi|>1$ if $b\geq 3$ and $f(\phi)=0$ . Let $f(x)=g(x)h(x)$ . Since $f(b)=p$ , one of $|g(b)|$ and $h(b)$ is 1. WLOG, assume $g(b)=1$ . Let $\phi_1, phi_2,\cdots,\phi_r$ be the roots of $g(x)$ . This means that $|g(b)|=|b-\phi_1||b-\phi_2|\cdots|b-\phi_r|>1$ . Therefore, $f(x) is irreducible.

If$ (Error compiling LaTeX. Unknown error_msg)b=2$, we will need to prove another lemma:

All of the zeroes of$ (Error compiling LaTeX. Unknown error_msg)f(x) $satisfy Re$ z>\frac{3}{2}$.

Proof: If$ (Error compiling LaTeX. Unknown error_msg)n=1 $, then the two polynomials are$ x $and$ x\pm 1 $, both of which satisfy our constraint. For$ n=2 $, we get the polynomials$ x^2 $,$ x^2\pm x $,$ x^2\pm 1 $, and$ x^2\pm x\pm 1 $, all of which satisfy the constraint. If$ n\geq 3$, <cmath>|\frac{f(z)}{z^n}|\geq |1+\frac{a_{n-1}}{z}+\frac{a_{n-2}}{z^2}|-(\frac{1}{|z|^3}+\cdots+\frac{1}{|z|^n})>|1+\frac{a_{n-1}}{z}+\frac{a_{n-2}}{z^2}|-\frac{1}{|z|^2(|z|-1)}</cmath>

If Re$ (Error compiling LaTeX. Unknown error_msg)z\geq 0 $, we have Re$ \frac{1}{z^2}\geq 0 $, and then <cmath>|\frac{f(z)}{z^n}|>1-\frac{1}{|z|^2(|z|-1)}</cmath> For$ |z|\geq \frac{3}{2} $, then$ |z|^2(|z|-1)\geq(\frac{3}{2})^2(\frac{1}{2})=\frac{9}{8}>1 $. Therefore,$ z $is not a root of$ f(x).

However, if Re $z<0$ , we have from our first lemma, that $|z|<\frac{1+\sqrt{5}}{2}$ , so Re $z<\frac{1+\sqrt{5}}{2\sqrt{2}}<\frac{3}{2}$ . Thus we have proved the lemma.

To finish the proof, let $f(x)=g(x)h(x)$ . Since $f(2)=p$ , one of $g(2)$ and $h(2)$ is 1. WLOG, assume $g(2)=1$ . By our lemma, $|z-2|>|z-1|$ . Thus, if $\phi_1, \phi_2,\cdots,\phi_r$ are the roots of $g(x)$ , then $|g(2)|=|2-\phi_1||2-\phi_2|\cdots|2-\phi_n|>|1-\phi_1||1-\phi_2|\cdots|1-\phi_n|=|g(1)|\leq 1$ . This is a contradiction, so $f(x)$ is irreducible.

Page

Toolbox

Search

Cohn's criterion

Proof