x^2+y^2=N的整数解？
  我们先研究这个问题的⼀部分：哪些素数是两平⽅数之和？为什么我们先研究素数，有个很重要的原因是：若两个正整数都是两平⽅数之和，那么它们的乘积也是两平⽅数之和。道理很简单，设两个正整数分别为 a^2+b^2 和 c^2+d^2 ，那么有
当然我们暂时不⽤管这么多，我们专⼼研究素数。在尝试了⼀些较⼩的素数后（这⾥不再像《数论概论》⼀样把表打出来了...），我们发现，除了偶素数 2 （它是两平⽅数 1,1 之和）之外，⼀个素数是两平⽅数之和当且仅当这个素数除以 4 的余数为 1 （也可以叫做 4k+1 型素数）。
也就是说，我们有如下两个猜想：
1. 4k+1 型素数⼀定是两平⽅数之和。
2. 4k+3 型素数⼀定不是两平⽅数之和。
我们先挑⼀个简单的。第⼀个猜想要证明存在性，⼀般要构造，但是似乎不容易构造出来。我们再看第⼆个猜想，这个...好像也太简单了吧...注意到平⽅数模 4 余数⼀定是 0 或 1 ，两个平⽅数加起来怎么也凑不出余数 3 。第⼆个猜想就这么证出来了。
回头再看第⼀个猜想，好像还是很难的样⼦...事实上，这个猜想是成⽴的。不过，证明⽅法并没有⼀下⼦构造出两个平⽅数，⽽是先把这个素数的某个倍数表⽰为两平⽅数之和，再逐步缩⼩这个倍数。这种⽅法被称为费马降阶法。
设这个素数为 p ，我们先随便⼀个正整数 k 使得 kp 可写为两平⽅数之和：
这是很容易办到的，例如取 b=1 ，由于 p 是 4k+1 型素数，所以 -1 必然是 p 的⼆次剩余，因此可以到⼀个在 1,2,3,...,p-1 范围内的 a 使得 a^2+1是 p 的倍数。顺便我们可以得到 k ⼩于 p 。
若 k=1 ，则我们已经把 p 写成两平⽅数之和，因此我们假设 k>1 。
接下来我们想办法到另⼀组 a,b 使得 k 变得更⼩（也就是降阶操作）。为此我们先⼀个尽量⼩的正整数 t 使得 kt 可写为两平⽅数之和：
这也很容易做，只需把 a,b 都模 k ，得到的两个余数分别作 u,v 即可。为了尽量缩⼩ t ，我们不管 u,v 是正的还是负的，这样的好处是 u,v 的绝对值都可以取到不超过 k/2 。后⾯可以看到，只有这样才能保证达到降阶的⽬的。
然后把两式相乘，利⽤上⾯的恒等式：
在使⽤恒等式时，左边的加减号稍微变了⼀下，这样能保证左边的两个平⽅数都是 k^2 的倍数（别忘了 a,u 和 b,v 都是模 k 同余的）。然后两边同时除以 k^2 ，在最后⼀⾏⾥，⽤ a,b 替换两个⼩括号，⽤ k 换掉右边的 t ，我们就到了⼀组新的 a,b,k 使得 a^2+b^2=kp 。
当然，我们需要验证我们得到的 t 确实⼩于 k 。在式⼦ u^2+v^2=kt 中进⾏估计，左边不会超过 k^2/2 （因为 u,v 的绝对值都不超过 k/2 ），这样 t ⼀定不会超过 k/2 ，当然有 t ⼀定⽐ k ⼩。
最后还要排除 t=0 的情况。如果 t=0 ，那么 u^2+v^2=0 ，这样必有 u=v=0 ，也就是 a,b ⼀定是 k 的倍数。这样 a^2+b^2 ⼀定是 k^2 的倍数，则 kp 也是 k^2 的倍数， p 就是 k 的倍数。⽽ k 是⼩于 p 的，所以 k ⼀定为 1 ，与我们假设 k>1 ⽭盾。
这样，只要 k>1 ，我们就可以重复进⾏降阶操作直到 k=1 ，此时我们就把 p 表⽰成了两平⽅数之和。
⾄此，我们证明了 4k+1 型素数⼀定是两平⽅数之和。
结论：素数 p 是两平⽅之和当且仅当 p=2 或 p 为 4k+1 型素数。
素数的情况就研究完了，其实本来希望是所有素数都可以的...这样的话每个合数都可以表⽰为若⼲个素数的乘积，就直接得出所有正整数都是两平⽅数之和了。
对任意正整数的情况，受上⾯的启发，我们知道 4k+3 型正整数肯定不是两平⽅数之和（仍然是模 4 分析余数）。 4k+1 型正整数是否⼀定是两平⽅数之和？试验发现有反例（例如 21 ）。分解素因数发现， 21=3*7 ，两个素因数都是 4k+3 型的。我们需要研究含有 4k+3 型素因数的正整数的性质。
我们要证明这样⼀个性质：若 p 是 4k+3 型素数，则有
右边推左边是显然的。如果已知左边推右边，先⽤反证法，假设右边不成⽴，则 a,b 有⼀个不是 p 的倍数，容易得到另⼀个也不是 p 的倍数。然后就可以⽤费马⼩定理了。
到这⾥显然⽭盾了。注意第 4 ⾏⽤到了 p 为 4k+3 型素数的条件（否则右边没有负号）。我们⽴即推出，p^2 也是 a^2+b^2 的约数，⽽且
(a^2+b^2)/p^2=(a/p)^2+(b/p)^2 也是两平⽅数之和。
接下来我们讨论两平⽅数之和的问题，若某个正整数含某个 4k+3 型素因⼦ p ，并且 p^2 不整除该正整数，则该正整数不是两平⽅数之和；否则若p^2 整除该正整数，则该正整数是两平⽅数之和，等价于该正整数除以 p^2 后仍然是两平⽅数之和。
结论：某个正整数是两平⽅数之和，当且仅当该正整数的所有 4k+3 型素因⼦的幂次均为偶数。
博客为什么没人用了
考虑⼀个加强版的问题：哪些正整数可以表⽰成两个互素的平⽅数之和？容易想到的是，这类正整数决不能含有 4k+3 型素因⼦（否则的话，这两个平⽅数也必须是该素因⼦的倍数，它们不可能互素）。不过，不含 4k+3 型素因⼦的正整数也并不是都可以（例如 4,8 ）。事实上，所有 4 的倍数都不⾏，否则的话模 4 分析可得两个平⽅数均为 4 的倍数，它们不可能互素。
现在我们只剩下两类数要考虑：
1.只含 4k+1 型素因⼦的奇数。
2.只含 4k+1 型素因⼦的奇数的⼆倍。
下⾯证明第⼀类数都是两互素平⽅数之和。为此，先⽤归纳法证明 4k+1 型素数的正整数次幂是两互素平⽅数之和。设 p 为 4k+1 型素数，我们已经证出来 p 是两平⽅数之和，容易证明这两个平⽅数是互素的。
假设 p^k 被表⽰成了两互素平⽅数之和：
则我们可以将 p^(k+1) 表⽰为：
假如该表⽰不符合两平⽅数互素的要求，设 au+bv,av-bu 的最⼤公约数为 d(d>1) ，则有 d|p^(k+1) ，容
易得到 d 是 p 的倍数，也就是说 au+bv,av-bu 都是 p 的倍数。反过来，如果 au+bv,av-bu 不是 p 的倍数，那么该表⽰必然符合要求。
同时我们也可以看到，由归纳假设， p^k 和 p 的平⽅和表⽰都是合格的，也就是说 a,b,u,v 均不是 p 的倍数。
事实上，如果 au+bv,av-bu 确实是 p 的倍数，那么我们把这两个数换成 au-bv,av+bu ，这两个数都不是 p 的倍数（否则的话，它们都是 p 的倍数，那么 2bv=(au+bv)-(au-bv) 也是 p 的倍数，这与 b,v 均不是 p 的倍数⽭盾）。所以我们总是可以到两个互素的平⽅数。
接下来证明所有只含 4k+1 型素因⼦的奇数都是两互素平⽅数之和。为此我们先把它分解为若⼲个单素数幂，它们两两互素，由刚才的结论，可以把它们分别表⽰为两个互素平⽅数之和。然后再把它们乘起来。
我们证明这个结论：若 n=a^2+b^2,m=c^2+d^2 ，且 (n,m)=(a,b)=(c,d)=1 ，则
证明⽐较简单，设待证的最⼤公约数为 g ，则
所以说，只要互素的数 n,m 都是两互素平⽅数之和，则 nm 也是两互素平⽅数之和。这样我们就证完了。
对于第⼆类数（只含 4k+1 型素因⼦的奇数的⼆倍），设其中⼀个数为 2n ，则 n 是只含 4k+1 型素因数的奇数，于是存在 n=a^2+b^2 ，其中 a,b 互素。显然 a,b ⼀奇⼀偶。把 2n 写成 (a+b)^2+(a-b)^2 ，则有
于是这种表⽰是满⾜要求的。
结论：某个正整数是两互素平⽅数之和，当且仅当该正整数不含 4k+3 型素因⼦且不被 4 整除。