数论题 n^2==1(mod231)，求这个同余式所有的解。 要求详细写出过程。

这是一个二次同余式的问题，解起来与一次式完全不同，既费时又费脑，但还想试试玩一玩。不过只解出四个解：34、43、76和155适合同余式的解。
要 n^2—1被231整除，须n^2=232+1=232
所以：n^2=232+231k（k=0，1，2，……）（去除负整数k)
①当k=0时，n^2=232，显然232不是完全平方数，故排除
②当k=1时，n^2=463→排除
③当k=2时，n^2=232+462=694→排除
④当k=3时，n^2=232+231×3=925→排除
⑤当k=4时，n^2=232+231×4=1156→是完全平方数，可开出34，故为一解。
⑥当k=5时，n^2=232+231×5=1387→排除
⑦当k=6时，n^2=232+231×6=1618→排除
⑧当k=7时，n^2=232+231×7=1849→能开出43，故又为一解。
⑨……以后……直到
⑩当k=24时，n^2=232+231×24=5776→能开出76，又是一解。
…………
⑴当k=25至k=102时，无解
⑵当k=103时n^2=232+231×103=24205→开出155，此又为一解。
已经得到4个解：34、43、76、155
⑶⑷⑸⑹……下面当然还有解，但终究无度的往下一个个的算，哪岂不像“站在黄河两岸握手—— 差得远”，既像“瞎子走夜路——分不出东南西北”，又似“老太太坐飞机——劳命伤财”？
所以，到此告一段落，等那天灯火辉煌， 能得到此题的全部解时，再一一分解，也为时不晚！

-1-1-1+2002=1002
或者
将2002中拿出1000分别分给2，4，6，8。。。2000则变成3-3+5-5+7-7。。。。1002=1002
还能装58-5=35
大的高是小的高2倍大的圆是小的 圆4倍
故大的 体积是小的8倍
则58-5=35
43
原数与新数相加的和是77
故各位数加十位数是7又这个两位数的个位数字比十位数小1
故43
37-4-4=29
29-7=22
22\2=11
29-14=15(shequ)
29-21=8
8\2=4
29-28=1(shequ)
故小明和父亲的生日分别是4月11日和4月18日
或者小明和父亲的生日分别是4月4日和4月25日
11x/20+16=3x/4
得x=80
52个
孙子定理 孙子定理
中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国剩余定理。公元前后的《孙子算经》中有“物不知数”问题：“今有物不知其数，三三数之余二 ，五五数之余三 ，七七数之余二，问物几何？”答为“23”。也就是求同余式组x≡2 （mod3），x≡3 （mod5 ），x≡2 （mod7）（式中a≡b （modm）表示m整除a－b ）的正整数解。明朝程大位用歌谣给出了该题的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。”即解为x≡2×70＋3×21＋2×15≡233≡23(mod105）。此定理的一般形式是设m = m1 ，… ，mk 为两两互素的正整数，m＝m1，…mk ，m＝miMi，i＝1，2，… ，k 。则同余式组x≡b1(modm1)，…，x≡bk(modmk)的解为x≡M'1M1b1＋…＋M'kMkbk （modm）。式中M'iMi≡1 （modmi），i＝1，2，…，k 。直至18世纪 CF高斯才给出这一定理。孙子定理对近代数学如环论，赋值论都有重要影响。
孙子问题的解法，以现代的说法，是找出三个关键数70，21，15。解法的意思就是用70乘3除所得的馀数，21乘5除所得的馀数，15乘7除所得的馀数，然后总加起来，除以105的余数就是答案。
即题目的答案为 70×2+21×3+15×2
=140+63+30
=233
233-2×105=23
公式：70a+21b+15c-105n
解法中的三个关键数70，21，15，有何妙用，有何性质呢首先70是3除馀1而5与7都除得尽的数，所以70a是3除馀a,而5与7都除得尽的数，21是5除馀1，而3与7都除得尽的数，所以21b是5除馀b，而3与7除得尽的数。同理，15c是7除馀c，3与5除得尽的数，总加起来 70a+21b+15c 是3除馀a，5除馀b ，7除馀c的数，也就是可能答案之一，但可能不是最小的，这数加减105(105=357)仍有这样性质，可以多次减去105而得到最小的正数解。

《孙子算经》里面的"物不知数"说的是这样的一个题目：一堆东西不知道具体数目，3个一数剩2个，5个一数剩3个，7个一数剩2个，问一共有多少个。
书里面给了计算过程及答案：702 + 213 + 152 -1052 = 23。
它的计算思路如下：
70是能被5或7整除的数字，但是除以3正好余1。
21是能被3或7整除的数字，但是除以5正好余1。
15是能被3或5整除的数字，但是除以7正好余1。
所以若有数N = 70 N1 + 21 N2 + 15 N3(其中N,N1,N2,N3为正整数)，则整数N是符合题目要求的结果(mod3为N1，mod5为N2， mod7为N3)。
我们把N1赋值2，N2赋值3，N3赋值2。
则: N = 702 + 213 + 152 = 233。
但是3，5，7的最小公倍数为105。
所以N + 105M均为正解。
因此为了求得最小正整数解，我们需要用(N mod 105)也就是23了。
中国剩余定理(西方数学史中的叫法)，就是上一题目的一般情况。
设m1,m2mk是两两互素的正整数，即: gcd(mi, mj) = 1 (其中 i != j, i, j >= 1且 <=k)
则同余方程组:
x ≡ a1(mod m1)
x ≡ a2(mod m2)

x ≡ ak(mod mk)
存在唯一[m1,m2mk]使方程成立
解法同物不知数是一致的我们可以稍微模仿一下
唯一的难题就是如何把上面70, 15, 21的求法,对应到一般情况来
假设: N1, N2, ,Nk就是对应的权值, 满足如下条件:
N1 能够被 m2, m3, mk整除,但是除以m1正好余1
N2 能够被 m1, m3, mk整除,但是除以m2正好余1

Nk能够被m1, m2,,mk-1整除,但是除以mk正好余1
N1->Nk如果求出来了,那么假设:
x1 = N1a1 + N2a2 + + Nkak就是我们要求的x一个解, 同物不知数一样,我们把x1 mod (m1m2mk)的结果
就是x的最小整数解,若为负数,则再加上一个m1m2mk因为加减整数倍个m1m2mk所得结果都是x的解
所以问题只剩下一个,就是求N1, N2,,Nk
怎么求呢我需要先化简一番:
设m = m1m2mk, L, J为任意整数
因为Ni能被m1, m2,,mi-1, mi+1,,mk整除(其中i+1<k)
因此: Ni = m/mi L
又因为Ni除以mi余1
因此: Ni = miJ + 1
即: miJ + 1 = m/mi L ==> (-mi)J + m/miL = 1
而m1-->mk这些数都是互质数,所以(-mi) 同 m/mi也是互质数即:
gcd(mi, m/mi) = 1也就是说:
(m/mi)L + (-mi)J = gcd(m/mi, -mi)==>其中-mi和m/mi都是已知的,J和L未知
这就是经典扩展欧几里德定理的原型(由定理知J和L是唯一的, 因此,N1-->Nk有唯一解)
按照扩展欧几里德定理求解即可
扩展欧几里德定理：
a和b都是不全为0的正整数，则：
ax + by = gcd(a, b)
存在唯一的x, y使得上面等式成立。
(当然，容易得知，如果，a和b中有负数，那么也是成立的。)
本题中，m/mi相当于a, -mi相当于b, L相当于x, J相当于y。求出L, J就能求出Ni。
此时Ni求解完毕
我们要求的x的最小整数解也就呼之欲出了
————————————————
版权声明：本文为CSDN博主「hard_man」的原创文章，遵循 CC 40 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：>中国剩余定理
"剩余倍分法"互除余一 互除少一
证明"孙子定理"不完善 不稳定的表现
作者：张景刚 zhangyi003@yahoocn
>为了方便用X≡a(mod m)表示X用m除余数为a，aX≡b(mod m) 表示aX用m除余数为b,这称为同余式，那么两题如下去解：
1．求X满足同余式组
X≡1(mod3), X≡2(mod4), X≡4(mod5),
先求X1，X2，X3，它们分别满足同余式
20X1≡1(mod3), 15X2≡2(mod4), 12X3≡4(mod5),
（20=4×5，15=3×5，12=3×4）
解得X1≡2(mod3), X2≡2(mod4), X3≡2(mod5),（如何解下面讲）
求得上面三个同余式均是2，3个2是巧合，
故得X≡20×2+15×2+12×2≡94(mod60),X=34。
2．求X满足同余式组
X≡5(mod9), X≡1(mod7), X≡2(mod5),
先求X1，X2，X3，它们分别满足同余式
35X1≡5(mod9), 45X2≡1(mod7), 63X3≡2(mod5),
解得X1≡4(mod9), X2≡5(mod7), X3≡4(mod5),
故得X≡35×4+45×5+63×4≡617(mod315),X=302。
如何求同余式20X1≡1(mod3), 15X2≡2(mod4)，12X3≡4(mod5),等等，对你们中学生来说用尝试法即可，只要3，4，5互质（9，7，5互质），同余式必有解，如12X≡4(mod5),将X=1，2，,5代入尝试，X=1时，12X用5除余2，X=2，12X用5除余4，故X=2是解，尝试法计算量不大，m=5，最多尝试5次，m=9, 最多尝试9次,如35X≡5(mod9)，最多尝试9次，将X=1,2,3,…,9代入即可，如果你不想用尝试法，方法很多，但不如尝试法来的简单，如计算12X≡4(mod5)，（1）一种是求不定方程，12X≡4(mod5)等价于求二元不定方程的整数解12X-5Y=4，可用欧几里得辗转相除法来求。
（2）先求12X≡1(mod5)的解，利用欧拉定理（这是数论重要定理a^(p-1)≡1(modp)）直接求得X≡12^(5-2) (mod5)，X≡12^3 ≡2^3=8≡3，12X≡4(mod5)的解为X≡4×3≡2(mod5)，这种方法求同余式aX≡b(modm)要求a,m互素。
可参看看我写的一篇文章：
>中国剩余定理
民间传说着一则故事——“韩信点兵”。
秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。
在一千多年前的《孙子算经》中，有这样一道算术题：
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数
这样的问题，也有人称为“韩信点兵”它形成了一类问题，也就是初等数论中解同余式这类问题的有解条件和解的方法被称为“中国剩余定理”，这是由中国人首先提出的
① 有一个数，除以3余2，除以4余1，问这个数除以12余几？
解：除以3余2的数有：
2， 5， 8， 11，14， 17， 20， 23…
它们除以12的余数是：
2，5，8，11，2，5，8，11，…
除以4余1的数有：
1， 5， 9， 13， 17， 21， 25， 29，…
它们除以12的余数是：
1， 5， 9， 1， 5， 9，…
一个数除以12的余数是唯一的上面两行余数中，只有5是共同的，因此这个数除以12的余数是5
如果我们把①的问题改变一下，不求被12除的余数，而是求这个数很明显，满足条件的数是很多的，它是 5＋12×整数，
整数可以取0，1，2，…，无穷无尽事实上，我们首先找出5后，注意到12是3与4的最小公倍数，再加上12的整数倍，就都是满足条件的数这样就是把“除以3余2，除以4余1”两个条件合并成“除以12余5”一个条件《孙子算经》提出的问题有三个条件，我们可以先把两个条件合并成一个然后再与第三个条件合并，就可找到答案
②一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数
解：先列出除以3余2的数：
2， 5， 8， 11， 14， 17， 20， 23， 26，…，
再列出除以5余3的数：
3， 8， 13， 18， 23， 28，…
这两列数中，首先出现的公共数是83与5的最小公倍数是15两个条件合并成一个就是8＋15×整数，列出这一串数是8， 23， 38，…，再列出除以7余2的数 2， 9， 16， 23， 30，…，
就得出符合题目条件的最小数是23
事实上，我们已把题目中三个条件合并成一个：被105除余23
那么韩信点的兵在1000-1500之间，应该是105×10+23=1073人

剩余定理：
一个数除以5余1，除以7余2，除以9余4，问这个数最小是多少？
1 找一个最小的数a，使a能被7和9整除，而被5除余1可以找到a=126（79=63,126,189,252……，其中满足要求的最小数为126）；
2 同理，可以找到能被5和9整除，被7除余2的最小数b=135；
3 被5和7整除，被9除余4的最小数c=175；
126+135+175=436满足一个数除以5余1，除以7余2，除以9余4。
436/(579)=1……121
121即是所求最小的数

中国剩余定理的原理
物不知其数问题出自一千六百年前我国古代数学名著《孙子算经》。原题为："今有物不知其数，三三数之二，五五数之三，七七数之二，问物几何？"
这道题的意思是：有一批物品，不知道有几件。
如果三件三件地数，就会剩下两件；如果五件五件地数，就会剩下三件；如果七件七件地数，也会剩下两件。 问：这批物品共有多少件？
变成一个纯粹的数学问题就是：有一个数，用3除余2，用5除余3，用7除余2。
求这个数。
这个问题很简单：用3除余2，用7除也余2，所以用3与7的最小公倍数21除也余2，而用21除余2的数我们首先就会想到23；23恰好被5除余3，所以23就
是本题的一个答案。
这个问题之所以简单，是由于有被3除和被7除余数相同这个特殊性。
如果没有这个特殊性，问题就不那么简单了，也更有趣得多。
我们换一个例子；韩信点一队士兵的人数，三人一组余两人，五人一组余三人，七人一组余四人。问：这队士兵至少有多少人？
这个题目是要求出一个正数，使之用3除余2，用5除余3，用7除余4，而且希望所求出的数尽可能地小。
如果一位同学从来没有接触过这类问题，也能利用试验加分析的办法一步一步地增加条件推出答案。
例如我们从用3除余2这个条件开始。满足这个条件的数是3n+2，其中n是非负整数。
要使3n+2还能满足用5除余3的条件，可以把n分别用1，2，3，…代入来试。 当n=1时，3n+2=5，5除以5不用余3，不合题意；当n=2时，3n+2=8，8除以5正好余3，可见8这个数同时满足用3除余2和用5除余3这两个条件。
最后一个条件是用7除余4。8不满足这个条件。我们要在8的基础上得到一个数，使之同时满足三个条件。
为此，我们想到，可以使新数等于8与3和5的一个倍数的和。 因为8加上3与5的任何整数倍所得之和除以3仍然余2，除以5仍然余3。
于是我们让新数为8+15m，分别把m=1，2，…代进去试验。当试到m=3时，得到8+15m=53，53除以7恰好余4，因而53合乎题目要求。
我国古代学者早就研究过这个问题。例如我国明朝数学家程大位在他著的《算法统宗》（1593年）中就用四句很通俗的口诀暗示了此题的解法：
三人同行七十稀，
五树梅花甘一枝，
七子团圆正半月，
除百零五便得知。
"正半月"暗指15。"除百零五"的原意是，当所得的数比105大时，就105、105地往下减，使之小于105；这相当于用105去除，求出余数。
这四句口诀暗示的意思是：当除数分别是3、5、7时，用70乘以用3除的余数，用21乘以用5除的余数，用15乘以用7除的余数，然后把这三个乘积相加。
加得的结果如果比105大，就除以105，所得的余数就是满足题目要求的最小正整数解。
按这四句口诀暗示的方法计算韩信点的这队士兵的人数可得：
70×2+21×3+15×4=263，
263=2×105+53，
所以，这队士兵至少有53人。
在这种方法里，我们看到：70、21、15这三个数很重要，稍加研究，可以发现它们的特点是：
70是5与7的倍数，而用3除余1；
21是3与7的倍数，而用5除余1；
15是3与5的倍数，而用7除余1。
因而
70×2是5与7的倍数，用3除余2；
21×3是3与7的倍数，用5除余3；
15×4是3与5的倍数，用7除余4。
如果一个数除以a余数为b，那么给这个数加上a的一个倍数以后再除以a，余数仍然是b。
所以，把70×2、21×3与15×4都加起来所得的结果能同时满足"用3除余2、用5除余3、用7除余4"的要求。一般地，
70m+21n+15k (1≤m＜3, 1≤n＜5,1≤k＜7)
能同时满足"用3除余m 、用5除余n 、用7除余k"的要求。
除以105取余数，是为了求合乎题意的最小正整数解。
我们已经知道了70、21、15这三个数的性质和用处，那么，是怎么把它们找到的呢？要是换了一个题目，三个除数不再是3、5、7，应该怎样去求出类似的有用的数呢？
为了求出是5与7的倍数而用3除余1的数，我们看看5与7的最小公倍数是否合乎要求。
5与7的最小公倍数是5×7=35，35除以3余2，35的2倍除以3余2，35的2倍除以3就能余1了，于是我们得到了"三人同行七十稀"。
为了求出是3与7的倍数而用5除余1的数，我们看看3与7的最小公倍数是否合乎要求。
3与7的最小公倍数是3×7=21，21除以5恰好余1，于是我们得到了"五树梅花甘一枝"。
为了求出是3与5的倍数而用7除余1的数，我们看看3与5的最小公倍数是否合乎要求。
3与5的最小公倍数是3×5=15，15除以7恰好余1，因而我们得到了"七子团圆正半月"。
3、5、7的最小公倍数是105，所以"除百零五便得知"。
例如：试求一数，使之用4除余3，用5除余2，用7除余5。

解：我们先求是5与7的倍数而用4除余1的数；5与7的最小公倍数是5×7=35，35除以4余3，3×3除以4余1，因而35×3=105除以4余1，105是5与7的倍数而用4除余1的数。

我们再求4与7的倍数而用5除余1的数；4与7的最小公倍数是4×7=28，28除以5余3，3×7除以5余1，因而28×7=196除余5余1，所以196是4与7的倍数而用5除余1的数。
最后求的是4与5的倍数而用7除余1的数：4与5的最小公倍数是4×5=20，20除以7余6，6×6除以7余1，因而20×6=120除以7余1，所以120是4与5的倍数而用7除余1的数。

利用105、196、120这三个数可以求出符合题目要求的解：
105×3+196×2+120×5=1307。
由于4、5、7的最小公倍数是4×5×7=140，1307大于140，所以1307不是合乎题目要求的最小的解。
用1037除以140得到的余数是47，47是合乎题目的最小的正整数解。
一般地，
105m+196n+120k (1≤m＜4,1≤n＜5,1≤k＜7)
是用4除余m,用5除余n,用7除余k的数(105m+196n+120k)除以140所得的余数是满足上面三个条件的最小的正数。

上面我们是为了写出105m+196n+120k这个一般表达式才求出了105这个特征数。如果只是为了解答我们这个具体的例题，由于5×7=35既是5与7的倍数除以4又余3，就不必求出105再乘以3了。

35+196×2+120×5=1027
就是符合题意的数。
1027=7×140+47，
由此也可以得出符合题意的最小正整数解47。
《算法统宗》中把在以3、5、7为除数"物不知其数"问题中起重要作用的70、21、15这几个特征数用几句口诀表达出来了，我们也可以把在以4、5、7为除数的问题中起重要作用的105、196、120这几个特征数编为口诀。

---