Cohn's criterion
Let be a prime number, and an integer. If is the base- representation of , and , then is irreducible.
Proof
The following proof is due to M. Ram Murty.
We start off with a lemma. Let . Suppose , . Then, any complex root of , , has a non positive real part or satisfies .
Proof: If and Re , note that: This means if , so .
If , this implies if and . Let . Since , one of and is 1. WLOG, assume . Let be the roots of . This means that . Therefore, is irreducible.
If , we will need to prove another lemma:
All of the zeroes of satisfy Re .
Proof: If , then the two polynomials are and , both of which satisfy our constraint. For , we get the polynomials , , , and , all of which satisfy the constraint. If ,
If Re , we have Re , and then For , then . Therefore, is not a root of .
To finish the proof, let . Since , one of and is 1. WLOG, assume . By our lemma, . Thus, if are the roots of , then . This is a contradiction, so is irreducible.