Misalkan \(d(x)\) polinomial monik berderajat terkecil dalam himpunan
\begin{equation*}
S = \{ f(x) p(x) + g(x) q(x) : f(x), g(x) \in F[x] \}\text{.}
\end{equation*}
Kita dapat menulis \(d(x) = r(x) p(x) + s(x) q(x)\) untuk dua polinomial \(r(x)\) dan \(s(x)\) di \(F[x]\text{.}\) Kita perlu menunjukkan bahwa \(d(x)\) membagi \(p(x)\) dan \(q(x)\text{.}\) Pertama-tama kita akan menunjukkan bahwa \(d(x)\) membagi \(p(x)\text{.}\) Berdasarkan algoritma pembagian, terdapat polinomial \(a(x)\) dan \(b(x)\) sedemikian sehingga \(p(x) = a(x) d(x) + b(x)\text{,}\) dengan \(b(x)\) merupakan polinomial nol atau \(\deg b(x) \lt \deg d(x)\text{.}\) Oleh karena itu,
\begin{align*}
b(x) & = p(x) - a(x) d(x)\\
& = p(x) - a(x)( r(x) p(x) + s(x) q(x))\\
& = p(x) - a(x) r(x) p(x) - a(x) s(x) q(x)\\
& = p(x)( 1 - a(x) r(x) ) + q(x) ( - a(x) s(x) )
\end{align*}
merupakan kombinasi linear dari \(p(x)\) dan \(q(x)\text{,}\) sehingga harus berada di \(S\text{.}\) Akan tetapi, \(b(x)\) harus merupakan polinomial nol karena \(d(x)\) dipilih berderajat terkecil; akibatnya, \(d(x)\) membagi \(p(x)\text{.}\) Argumen simetris menunjukkan bahwa \(d(x)\) juga harus membagi \(q(x)\text{;}\) jadi, \(d(x)\) merupakan faktor persekutuan dari \(p(x)\) dan \(q(x)\text{.}\)
Untuk menunjukkan bahwa \(d(x)\) merupakan faktor persekutuan terbesar dari \(p(x)\) dan \(q(x)\text{,}\) misalkan \(d'(x)\) faktor persekutuan lain dari \(p(x)\) dan \(q(x)\text{.}\) Kita akan menunjukkan bahwa \(d'(x) \mid d(x)\text{.}\) Karena \(d'(x)\) merupakan faktor persekutuan dari \(p(x)\) dan \(q(x)\text{,}\) terdapat polinomial \(u(x)\) dan \(v(x)\) sedemikian sehingga \(p(x) = u(x) d'(x)\) dan \(q(x) = v(x) d'(x)\text{.}\) Oleh karena itu,
\begin{align*}
d(x) & = r(x) p(x) + s(x) q(x)\\
& = r(x) u(x) d'(x) + s(x) v(x) d'(x)\\
& = d'(x) [r(x) u(x) + s(x) v(x)]\text{.}
\end{align*}
Karena \(d'(x) \mid d(x)\text{,}\) \(d(x)\) merupakan faktor persekutuan terbesar dari \(p(x)\) dan \(q(x)\text{.}\)
Terakhir, kita harus menunjukkan bahwa faktor persekutuan terbesar dari \(p(x)\) dan \(q(x)\) bersifat tunggal. Misalkan \(d'(x)\) faktor persekutuan terbesar lain dari \(p(x)\) dan \(q(x)\text{.}\) Kita baru saja menunjukkan bahwa terdapat polinomial \(u(x)\) dan \(v(x)\) di \(F[x]\) sedemikian sehingga \(d(x) = d'(x)[r(x) u(x) + s(x) v(x)]\text{.}\) Karena
\begin{equation*}
\deg d(x) = \deg d'(x) + \deg[r(x) u(x) + s(x) v(x)]
\end{equation*}
dan \(d(x)\) serta \(d'(x)\) keduanya merupakan faktor persekutuan terbesar, \(\deg d(x) = \deg d'(x)\text{.}\) Karena \(d(x)\) dan \(d'(x)\) keduanya polinomial monik berderajat sama, haruslah \(d(x) = d'(x)\text{.}\)