前言
最近，笔者在一道 OI 题的 Hint 里看到了这样一个定理：
费马平方和定理：一个奇素数能被表成两个平方数之和，当且仅当它是 模4余1 型素数。
网上的几个证法看了之后写下这篇笔记。
法一：构造
核心：证明方程 \(4xy+z^2=p\) 在 \(p\) 是模4余1型素数时，必有 \(x=y\) 的解。
前置知识
基数：集合的元素个数。
对合：逆函数的函数，即满足 \(f(f(x))=x\) 的函数。
Step1
设集合 \(S=\left\{ (x,y,z) \vert 4xy + z^2 = p , x \in N , y \in N , z \in Z \right\}\) ，
其中 \(p\) 是一固定素数。
显然是个有限集。
再设 \(T=\left\{ (x,y,z) \in S | z >0 \right\}\) ，容易发现此时这个集合就是方程 \(4xy + z^2 =p\) 的解集了。
这里的 \(x\) 和 \(y\) 事实上是处于相同地位的（函数 \(f:T \to T , (x,y,z) \to (y,x,z)\) 是对合），那我们只要证明 \(T\) 的基数是奇数就行了。
Step2
这时候我们开始考虑基数。
先是 \(S\) ，构造一个函数 \(g:S \to S , (x,y,z) \to (y,x,-z)\) （跟 \(f\) 类似）。
由于 \(z \not= 0\) ，所以 \(g\) 一定没有不动点，也就是说 \(S\) 的基数是偶数。
同时，这个函数实现了 \(T\) 和 \(S/T\) 之间的一一映射。
因此 \(T\) 的基数是 \(S\) 的一半。
Step3
这个一半就很巧了呀。
尝试构造一个新的集合，其基数也是 \(S\) 一半的，并构造这个集合上的函数，以此证明 \(T\) 的基数是奇数。
这一步算得上是整个证明过程中的点睛之笔：
发现 \(g\) 也将 \(x-y\) 和 \(z\) 的正负性同时改变。当然 \(x-y + z\) 是一定不为 \(0\) 的，具体套入原式验证。
设 \(U = \left\{ (x,y,z) \in S | (x-y) + z > 0 \right\}\) ，那么 \(g\) 也实现了 \(U\) 和 \(S/U\) 之间的一一映射。
所以 \(U\) 的基数也是 \(S\) 的一半，与 \(T\) 相同。
在 \(U\) 上构造映射， \(h:U \to U , (x,y,z) \to (x-y+z,y,2y-z)\) 。
它是合法的因为 \(4y(x-y+z) + (2y-z)^2=4xy + z^2\) ，同时这是一个对合。
于是考虑它是否有不动点，就可以判断基数奇偶性了。
如果有，那么 \(y=z\) ，又因为 \(4xy + z^2=p\) ，
所以 \(y(4x+y)=p\) ，这就要求 \(y=z=1\) ， \(x=\frac{p-1}{4}\) ，
这时 \(p\) 为模4余1型素数，\(T\) 的基数为奇数，一定有满足 \(x=y\) 的解。