Het bewijs gebruikt voor een deel volledige inductie en is voor een deel een bewijs uit het ongerijmde.

Beschouw een polynoom ${\displaystyle f}$ en stel dat er niet-constante polynomen ${\displaystyle g}$ en ${\displaystyle h}$ met gehele coëfficienten zijn, zo dat ${\displaystyle f(x)=g(x)\cdot h(x)}$.

${\displaystyle g(x)=b_{m}x^{m}+b_{m-1}x^{m-1}+\ldots +b_{1}x+b_{0}}$

${\displaystyle h(x)=c_{k}x^{k}+c_{k-1}x^{k-1}+\ldots +c_{1}x+c_{0}}$

${\displaystyle n=m+k}$

${\displaystyle b_{m}}$ en ${\displaystyle c_{k}}$ kunnen geen van beide door ${\displaystyle p}$ worden gedeeld, omdat ${\displaystyle a_{n}}$ niet door ${\displaystyle p}$ kan worden gedeeld. Er volgt uit ${\displaystyle a_{0}=b_{0}c_{0},\ a_{0}\ {\text{mod}}\ p\ =\ 0}$ en ${\displaystyle a_{0}\ {\text{mod}}\ p^{2}\ \not =\ 0}$, dat een van de twee ${\displaystyle b_{0}}$ en ${\displaystyle c_{0}}$ een keer door ${\displaystyle p}$ is te delen, de andere niet. Kies de coëfficiënten, zodat ${\displaystyle b_{0}\ {\text{mod}}\ p=0}$ en ${\displaystyle c_{0}\ {\text{mod}}\ p\ \not =\ 0}$.

${\displaystyle a_{r}=\sum _{i+j=r}b_{i}\ c_{j}=b_{0}\ c_{r}+\cdots +b_{r}\ c_{0}}$,

waarin de coëfficiënten ${\displaystyle b_{i}}$ en ${\displaystyle c_{j}}$ gelijk aan 0 kunnen zijn, omdat ${\displaystyle i>m}$ of ${\displaystyle j>k}$ daarin mogelijk is.

Voor alle ${\displaystyle i}$ tot en met ${\displaystyle n-1}$ is het zo, dat ${\displaystyle b_{i}}$ door ${\displaystyle p}$ kan worden gedeeld of gelijk aan nul is. Dit deel wordt met volledige inductie bewezen.

Inductiebegin

${\displaystyle b_{0}}$ kan door ${\displaystyle p}$ worden gedeeld. Dat is afgeleid.

Inductieveronderstelling

Veronderstel voor bepaalde ${\displaystyle r}$ dat voor alle ${\displaystyle i<r}$ het zo is dat ${\displaystyle b_{i}}$ door ${\displaystyle p}$ kan worden gedeeld of gelijk aan nul is.

Inductiestap

${\displaystyle a_{r}=\sum _{i+j=r}b_{i}\ c_{j}=b_{0}\ c_{r}+\cdots +b_{r}\ c_{0}}$

Gegeven dat ${\displaystyle r<n}$ kan ${\displaystyle a_{r}}$ door ${\displaystyle p}$ worden gedeeld. Dat betekent dat ${\displaystyle b_{r}}$ ook door ${\displaystyle p}$ kan worden gedeeld of gelijk aan nul is. ${\displaystyle c_{0}}$ kon niet door ${\displaystyle p}$ worden gedeeld, maar alle ${\displaystyle b_{0}\ ,\ \cdots \ ,\ b_{r-1}}$ wel. De inductiestap is daarmee gezet.

Er doet zich nu bij ${\displaystyle a_{n}}$ een tegenspraak voor.

${\displaystyle a_{n}=\sum _{i+j=n}b_{i}\ c_{j}=b_{0}\ c_{n}+\cdots +b_{n}\ c_{0}}$

${\displaystyle b_{n}=0}$, omdat ${\displaystyle m}$ de coëfficiënt van de hoogste macht van ${\displaystyle g}$ is en ${\displaystyle m<n}$, en alle andere ${\displaystyle b_{i}}$ kunnen in ieder geval door ${\displaystyle p}$ worden gedeeld. Het is gegeven dat ${\displaystyle a_{n}}$ niet door ${\displaystyle p}$ kan worden gedeeld, maar alle termen in de som ${\displaystyle b_{0}\ c_{n}+\cdots +b_{n}\ c_{0}}$ kunnen wel door ${\displaystyle p}$ worden gedeeld, hun som dus ook en dat geeft een tegenspraak.

${\displaystyle x^{p}-1=(x-1)(x^{p-1}+x^{p-2}+\ldots +x+1)}$

Na substitutie van ${\displaystyle x=y+1}$ is deze vergelijking met binomiaalcoëfficiënten te schrijven als:

${\displaystyle x^{p-1}+x^{p-2}+\ldots +x+1={\frac {x^{p}-1}{x-1}}={\frac {(y+1)^{p}-1}{y}}=y^{p-1}+\sum _{j=1}^{p-1}{\binom {p}{j}}y^{j-1}}$

De coëfficiënt 1 van de hoogste macht van ${\displaystyle y}$ kan niet door ${\displaystyle p}$ worden gedeeld, maar alle andere coëfficiënten wel en de constante term, die ook ${\displaystyle p}$ is, kan niet door ${\displaystyle p^{2}}$ worden gedeeld. Uit het criterium van Eisenstein volgt nu dat het polynoom in ${\displaystyle y}$ irreducibel is, dus is ook het oorspronkelijke polynoom in ${\displaystyle x}$ irreducibel.