View source for Cohn's criterion

Let <math>p</math> be a prime number, and <math>b\geq 2</math> an integer. If <math>\overline{p_np_{n-1}\cdots p_1p_0}</math> is the base-<math>b</math> representation of <math>p</math>, and <math>0\leq p_i<b</math>, then
<cmath>f(x)=p_nx^n+p_{n-1}x^{n-1}+\cdots+p_1x+p_0</cmath>
is irreducible.

==Proof==
The following proof is due to M. Ram Murty.

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

Proof: If <math>|z|>1</math> and Re <math>z>0</math>, note that:
<cmath>|\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|}</cmath>
This means <math>g(z)>0</math> if <math>|z|\geq \frac{1+\sqrt{1+4H}}{2}</math>, so <math>|\phi|<\frac{1+\sqrt{1+4H}}{2}</math>.

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

If <math>b=2</math>, we will need to prove another lemma:

All of the zeroes of <math>f(x)</math> satisfy Re <math>z<\frac{3}{2}</math>.

Proof: If <math>n=1</math>, then the two polynomials are <math>x</math> and <math>x\pm 1</math>, both of which satisfy our constraint. For <math>n=2</math>, we get the polynomials <math>x^2</math>, <math>x^2\pm x</math>, <math>x^2\pm 1</math>, and <math>x^2\pm x\pm 1</math>, all of which satisfy the constraint. If <math>n\geq 3</math>, 
<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 <math>z\geq 0</math>, we have Re <math>\frac{1}{z^2}\geq 0</math>, and then
<cmath>|\frac{f(z)}{z^n}|>1-\frac{1}{|z|^2(|z|-1)}</cmath>
For <math>|z|\geq \frac{3}{2}</math>, then <math>|z|^2(|z|-1)\geq(\frac{3}{2})^2(\frac{1}{2})=\frac{9}{8}>1</math>. Therefore, <math>z</math> is not a root of <math>f(x)</math>.


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


[[Category:Algebra]]