2段にわけて証明する.
(第1段) 合同方程式に整数解が存在するならばは2つの平方数の和として表せることを示す.とする.にそれぞれの整数倍を加えてもであるから, であるとしてよい.さらに,のときは,をそれぞれで割ってもなので,であるとしてよい.(はどちらもより小さいのではの倍数ではない.) このときであるので,の正の約数は全て以下である.もしが2つの互いに素な平方数の和として表せないならば,補題によりの以外の素因数で,2つの互いに素な平方数の和として表せないものが存在する.それをとすれば明らかにである.そして,同様にしてを作っていくことができ,素数の真減少列ができる.しかし,素数全ての集合は下に有界なのでこれは矛盾である.ゆえに,合同方程式が整数解をもつならば,は2つの平方数の和として表すことができる.
(第2段) 合同方程式が整数解をもつことを示す.だから,とおけば,Fermatの小定理により
が任意のの倍数でない整数に対して成り立つ.よって,ならばとなって証明が完了するが,平方剰余の第一補充則によってであるときそのような整数が存在する.