這個問題是一個比較有趣也有價值的問題。前面Mr.He給出的證明思路是正確的。《Proof of The Book》中給出過一個更嚴格的引理及其巧妙的證明過程，可以幫助證明這個結論。

【引理】 對於素數p， 關於 的正整數解滿足如下結論：如果p=2，那麼s只有1個解；如果p為形如4m+1的素數，那麼s有2個解；如果p為形如4m+3的素數，那麼s無解。這個引理的簡略證明如下：首先，任何素數都可以分為三類{2}、{4m+1型素數}、{4m+3型素數}，因此上面的引理涵蓋了所有素數的可能。其次，p=2時引理顯然成立。第三，對於任一奇素數p，我們把集合{1、2、3、......、p-2、p-1}中的p-1個數進行分組。分組方法如下，先任選集合中的一個數x，然後把x、p-x、x"、p-x"分到一組，其中的x"滿足 。如果對於數論及“素數同餘類乘群”不熟悉的朋友，我可以舉個例子。比如對於素數11，在{1、2、3、...、9、10}這個集合中，分組如下{1、10}，{2、9、6、5}，{3、8、4、7}。從這個例子中也可以看出來，有些時候會發生 或者 的情況（注意由於p是奇數，因此不可能發生x=p-x的情況）。如果x=x"，意味著 ，從而x只能為1或p-1，也就是說，這種情況對應著分組{1、p-1}，而且也只有這一種情況；如果 ，則由 得到 。這個同餘式就是引理中關於s的同餘式，它在0<x"<p的範圍內，要麼沒有解，要麼有2個解。這是因為如果x"是同餘式的解，那麼 也必然是它的解，而且不會再有一個與x"及 不同的解了（這一點不難證明，因為如果再有一個 也滿足同餘式，那就意味著 ，從而 ，從而x""只能等於p-x"）。於是，根據上述結果，分組完成後，一般情況下每組有四個數，另外還必然有一組{1、p-1}有兩個數，還有可能有一組{x"、p-x"}有兩個數，但也可能不存在這樣的x"。由於集合中一共有p-1個數，如果p為4m+3型素數，意味著p-1=4m+2，這樣分組後就必然不會有{x"、p-x"}這組了，否則總數會被4整除，與4m+2矛盾。沒有{x"、p-x"}這組意味著 無解。如果p為4m+1型素數，p-1=4m，從而必然會有{x"、p-x"}這一組。這意味著 有兩個解，就是x"與p-x"。從而引理得證。

於是，我們可以很容易的證明4n+1型的素數有無窮多個了。假設不是這樣，那麼設 到 為全部的4n+1型素數，則構造 型的整數 ，這是一個奇數，顯然不會被2整除，而且根據前面的引理，它也不會被4n+3型的素數整除（因為同餘式無解），從而它的素因子必然全部都是4n+1型的素數。問題是我們假設的全部4n+1型的素數 到 都不能整除它，於是必然要存在 到 以外的4n+1型素數。從而假設不成立，4n+1型素數必然有無窮多。

另外，4n+3型的素數也是無窮多個的。證明這個結論更容易。假設4n+3型素數有限多個，設為 到 ，那麼構造 ，這個數因為是奇數所以沒有素因子2，也不會全部都是4n+1型的素因子，否則這個數將會模4同餘1，與它實際模4同餘3矛盾。從而必然還有新的4n+3型素數。

以上內容供參考。