三、同余
1.定义：给定一个正整数m，把它叫做模。如果用m去除任意两个整数a与b所得的余数相同，则我们就说a，b对模m同余，记作a≡b（modm）。否则，我们说a，b对模m不同余，记作a≡/b（modm）。
2.定理：整数a，b对模m同余的充分且必要条件是m｜a-b，即a＝b＋mt，t是整数。
证明：设a＝mq1＋r1，b＝mq2＋r2，0≤r1＜m，0≤r2＜m。若a≡b（modm），则r1＝r2，因此a-b＝m（q1-q2）。反之，若m｜a-b，则m｜[m（q1-q2）＋（r1-r2）］因此m｜r1-r2。但｜r1-r2｜＜m，故r1＝r2。
有了同余的概念，我们就可把余数相同的数放在一起，从而产生了所谓剩余类概念。对模m，用它去除任何整数所得余数r，总满足0≤r≤m-1。若把余数为r的数放在一起，记作Kr，则可以把全体整数分为m个集合：K0，K1，…，Km-1，称它们为模m的剩余类。
3.剩余类具有下列性质：
（1）每一个整数必包含在而且仅在上述一个集合里。
（2）两个整数同在一个集合里的充分且必要条件是这两个整数对模m同余。
定义若a0，a1，…，am-1是m个整数，并且其中任何两数都不在同一个剩余类里，则称a0，a1，…，am-1为模m的一个完全剩余系。
例如，0，1，2，…，m-1便是模m的一个完全剩余系。
定义我们把完全剩余系中与模m互素的整数全体叫做模m的一个简化剩余系。
例如，m＝10时，1，3，7，9组成一个简化剩余系。
定义欧拉函数φ（x）是定义在正整数上的函数，它在正整数a上的值等于序列0，1，2，…，a-1中与a互素的数的个数。
例如，φ（10）＝4，φ（5）＝4。
4.同余式
若f（x）表示多项式anxn＋an-1xn-1＋…＋a1x＋a0，其中an，an-1，…，a0是整数，m是一个正整数，则f（x）≡0（modm）（12）
叫做模m的同余式。若an≡0（modm），则（12）叫做n次同余式。
若a是使f（a）≡0（modm）成立的一个整数，则x≡a（modm）叫做同余式（12）的一个解。第十三章 勾股方程如果x，y，z分别表示直角三角形的两个直角边和斜边的长，则有x2＋y2＝z2（1）
这就是著名的勾股定理。我们把方程（1）叫做勾股数方程。
如果正整数x，y，z适合方程（1），那么把它们叫做勾股数，或无零勾股数。如果勾股数x，y，z两两互素，那么称它们为基本勾股数。
求方程（1）的所有整数解，只须求出基本勾股数就足够了。所有另外的解，用改变符号，交换x，y和以某些非零的整数乘可以得到。
在寻找勾股数方面，我国有着悠久且光辉的历史。古算书《周髀算经》中，记述着公元前1100年周公和商高两个人的对话，商高说：“句广三，股修四，径隅五……”即给出了一组勾股数3，4，5。公元一、二世纪间的《九章算术》中，记载的勾股数竟有八组之多，它们是：（3，4，5），（5，12，13），（7，24，25），（8，15，17），（20，21，29），（20，99，101），（48，55，73），（60，91，109）。更有重大意义的是，近几年对《九章算术》进一步研究，数学史家指出，书中实际上给出了求勾股数的通式，即对于任意的正整数m，n，m＞n，有x=m2-n2y=2mnz=m2＋n2
并且刘徽给出了证明。这是第一个勾股方程解的通式。
公元前五、六世纪，古希腊数学家毕达哥拉斯在研究勾股定理方面做出了很大贡献，因而，国外把勾股定理叫做毕达哥拉斯定理，把勾股数叫做毕达哥拉斯数。
现在介绍（1）的解的通式。
我们讨论（1）的解的性质。
由于方程（1）是二次齐次式，故求（1）的非零整数解，只须求正整数解即可。因而，可假设x＞0，y＞0，z＞0。
如果（1）有正整数解x，y，z且（x，y）＝d＞1，那么d2｜（x2＋y2），即d2｜z2，而d｜z。此时，可从（1）的两端约去d。因而，可假定（x，y）＝1。
如果（1）有正整数解x，y，z，且（x，y）＝1，那么x，y奇偶性相反。因为（x，y）＝1，显然x，y不能同为偶数。x，y也不能同为奇数。否则，x2＋y2≡2（mod4），z2≡0或1（mod4），显然（1）不成立。故可设y为偶数。
综上所述，欲求（1）的全部非零整数解，只须求满足上述三个假定的整数解就可以了。
【定理1】方程x2＋y2＝z2（1）满足条件x＞0，y＞0，z＞0，（x，y）＝1，2｜y的全部整数解可以由下列公式给出：x=u2-v2（2）y=2uv（3）z=u2＋v2（4）
这里u＞v＞0，（u，v）＝1，u，v奇偶性相反。
首先，我们证明两个引理。
【引理1】如果x，y，z是方程（1）的解，并且满足条件（2），那么所有的12（z-x）都是整数，并且12（z＋x），12（z-x）
证明由于2｜y，（x，y）＝1，则x为奇数。因而x2为奇数，y2为偶数。由于x2＋y2＝z2，则z2为奇数，从而z为奇数。因此，z＋x，z-x都是偶数，故12（z＋x），12（z-x）都是整数。假设12（z＋x），12（z-x）=d，则12（z＋x）=k1d12（z-x）=k2d其中（k1，k2）＝1。由此得x＝（k1-k2）d，d｜x。又由（1）得y2＝z2-x2＝（z＋x）（z-x）＝4k1k2d2。因而d2｜y2，d｜y，故d｜（x，y）。但（x，y）-1，所以d＝1。
因此12（z＋x），12（z-x）=1.
【引理2】方程
uv＝w2（5）
满足条件
u＞0，v＞0，w＞0，（u，v）＝w（6）
全部整数解可以写成
u＝a2，v＝b2，w＝ab（7）
其中
a＞0，b＞0，（a，b）＝1（8）
证明设u，v，w是（5）的一组整数解，且满足条件（6）。令u＝a2u1，v＝b2v1，a，b，u1，v1都是正整数，且u1和v1不再有平方因子，则a2｜w2，b2｜w2，进而a｜w，b｜w。由于（u，v）＝1，则（a2，b2）＝1，进而（a，b）＝1。因此ab｜w。设w＝abw1，代入（5），得u1v1=w21（9）
如果w12≠1，那么存在素数p，使p2|w21.由于u1和v1的定义及（u1，v1）=1，可知p2u1v1，与（9）矛盾。因此w21=1，得u1v1＝1。但w1，u1，v1都是正整数，故w1＝u1＝v1＝1。因此，u＝a2，v＝b2，w＝aba＞0，b＞0，（a，b）＝1
反之，满足（8）的（7）中的u，v，w显然适合（5），并且满足（6）。
定理的证明把（1）改写成
y2＝（z＋x）（z-x）或
y22=z＋x2·z-x2
由引理1，12（z＋x）和12（z-x）都是整数，并且12（z＋x），12（z-x）=1.又由2|y和引理2，则12（z＋x）=u212（z-x）=v212y=uv解得x=u2y=2uvz=u2＋v2
这里u＞v＞0，（u，v）＝1。因为z是奇数，z＝u2＋v2，所以u，v奇偶性相反。
直接代入可验证，（3）式适合（1）：
x2＋y2＝（u2-v2）2＋4u2v2＝（u2＋v2）2＝z2由于u＞v＞0，所以x＝u2-v2＞0，y＝2uv＞0，z＝u2＋v2＞0，并且2｜y。设（x，y）＝d，则d｜z，d｜（u2＋v2），d｜（u2-v2），故d｜2（u2，v2）。但（u，v）＝1，则（u2，v2）＝1，故d＝1或2。因为x是奇数，d｜x，所以d＝1。因此，满足条件（4）的（3）中的x，y，z是（1）的解，并且满足条件（2）。
这里还要指出，古代各国学者都没有考虑（1）的通解问题，研究这方面的问题是近代的事，上个世纪八十年代才求得（1）的整数解的通式。
由公式（3），从不同的数对（u，v）得到不同的基本勾股数。例如，最小的几组基本勾股数，依z值从小到大的顺序如下：（3，4，5），（5，12，13），（15，8，17），（7，24，25），（21，20，29），（35，12，37），……
基本勾股数的列举相当于奇正整数分为两个整数平方和的表示法。关于这一点，费马证明熟知的定理：【定理2】如果n是正整数，n＝r2n′，并且n′不含平方因数，那么n能够表为两个平方数和的充分且必要条件是n′没有形如4m-1的素因数，其中r，m是正整数。
然后，余下的问题是求一个整数表为两个平方数和的个数。
令r（n）表示n＝a2＋b2的整数对（a，b）的个数，其中a，b不必为正数。例如r（1）＝4，r（5）＝8，即1＝（±1）2＋02＝02＋（±1）2
5＝（±1）2＋（±2）2＝（±2）2＋（±1）2
雅可比和高斯各自独立地求出r（n）：
【定理3】r（n）＝4（d1（n）-d3（n））
其中
d1（n）＝＃｛d｜d≥1，d｜n，d≡1（mod4）｝d3（n）＝＃｛d｜d≥1，d｜n，d≡3（mod4）｝定理3是说，n＝a2＋b2解的个数等于四倍于n的因数≡1（mod4）的个数减去n的因数≡3（mod4）的个数。
由于这个公式，确定所有的基本勾股数是可能的（对于确定的z）。定理3的证明可在华罗庚的《数论导引》中找到。
