同余及其应用毕业论文

数论中除了整除以外，还有一个很重要也很难的知识点，就是余数，理解余数性质时，要与整除性联系起来，从被除数中减掉余数，那么所得到的差就能够被除数整除了．在一些题目中因为余数的存在，不便于我们计算，去掉余数，回到我们比较熟悉的整除性问题，那么问题就会变得简单了，这样就需要用到余数中一个非常重要的定理—同余定理。

同余定义 如果a，b除以c的余数相同，就称a，b对于除数c来说是同余的，且有a与b的差能被c整除．（a，b，c均为自然数） 例如：17与13除以3的余数都是2，所以(17－11)能被3整除．

同余定理 ①如果 a%b = c, 则有(a+kb)%b = c; (k为非0整数) ②如果 a%b = c, 则有(k*a)%b = k*c%b; (k为正整数) ③(a+b)%c = ((a%c) + (b%c)) % c; ④(a*b)%c = ((a%c)*(b%c)) % c;

（一） 可加性 a与b的和除以c的余数，等于a，b分别除以c的余数之和（或这个和除以c的余数）． 例如：23，16除以5的余数分别是3和1，所以(23+16)除以5的余数等于3+1=4． 注意：当余数之和大于除数时，所求余数等于余数之和再除以c的余数． 例如：23，19除以5的余数分别是3和4，所以(23+19)除以5的余数等于(3+4)除以5的余数。

（二） 可减性 a与b的差除以c的余数，等于a，b分别除以c的余数之差． 例如：23，16除以5的余数分别是3和1，所以(23－16)除以5的余数等于3－1=2． 注意：当较大数的余数小于较小数的余数时，所求余数等于c减去余数之差． 例如：23，19除以5的余数分别是3和4，所以 除以(23－19)的余数等于5－(4－3)=4.

（三） 可乘性 a与b的乘积除以c的余数，等于a，b分别除以c的余数之积（或这个积除以c的余数）． 例如：23，16除以5的余数分别是3和1，所以除以5的余数等于3*1 = 3． 注意：当余数之积大于除数时，所求余数等于余数之积再除以c的余数． 例如：23，19除以5的余数分别是3和4，所以 除以5的余数等于3*4除以5的余数．

（四） 乘方性 如果a与b除以m的余数相同，那么a^n与b^n除以m的余数也相同，但不一定等于原余数． 例如：3，7除以4的余数都是3，可以算得3^2和7^2除以4的余数都等于1，它们的余数相等但不一定等于3. 余数判别法 当一个数N不能被另一个数整除时，虽然可以用长除法去求得余数，但当被除位数较多时，计算是很麻烦的．建立余数判别法的基本思想是：为了求出“N被m除的余数”，我们希望找到一个较简单的数R，使得：N与R对于除数m同余．由于R是一个较简单的数，所以可以通过计算R被m除的余数来求得N被m除的余数．

下面列出几个常用到的规律：

再加一个整理的结论： 能被7、13、11整除的特征（实际是一个方法）是这样的： 将一个多于4位的整数在百位与千位之间分为两截，形成两个数，左边的数原来的千位、万位成为个位、十位（依次类推）。 将这两个新数相减（较大的数减较小的数），所得的差不改变原来数能被7、11、13整除的特性，如果所得的差依然大于999，再次进行上一步，直到所得的差小于1000为止。 例如：判断71858332能否被7、11、13整除，这个数比较大， 将它分成71858、332两个数（右边是三位数） 71858-332=71526; 再将71526分成71、526两个数（右边是三位数） 526-71=455; 由于455数比原数小得多， 相对来说容易判断455能被7和13整除，不能被11整除， 所以原来的71858332能被7和13整除，不能被11整除。

同余问题

"差同减差，和同加和，余同取余，最小公倍加"

所谓同余问题，就是给出“一个数除以几个不同的数”的余数，反求这个数，称作同余问题。 首先要对这几个不同的数的最小公倍数心中有数，下面以4、5、6为例，请记住它们的最小公倍数是60。

1、差同减差：用一个数除以几个不同的数，得到的余数，与除数的差相同， 此时反求的这个数，可以选除数的最小公倍数，减去这个相同的差数，称为：“差同减差”。 例：“一个数除以4余1，除以5余2，除以6余3”，因为4-1=5-2=6-3=3，所以取-3，表示为60n-3。

2、和同加和：用一个数除以几个不同的数，得到的余数，与除数的和相同， 此时反求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为：“和同加和”。 例：“一个数除以4余3，除以5余2，除以6余1”，因为4+3=5+2=6+1=7，所以取+7，表示为60n+7。

3、余同取余：用一个数除以几个不同的数，得到的余数相同， 此时反求的这个数，可以选除数的最小公倍数，加上这个相同的余数，称为：“余同取余”。 例：“一个数除以4余1，除以5余1，除以6余1”，因为余数都是1，所以取+1，表示为60n+1。

4、最小公倍加：所选取的数加上除数的最小公倍数的任意整数倍（即上面1、2、3中的60n）都满足条件， 称为：“最小公倍加”，也称为：“公倍数作周期”。

一般关于余数的题目根据"差同减差，和同加和，余同取余，最小公倍加"就可以解出正确答案，但是好多关于余数的题目，不是仅仅知道上面17个字就能解题的，是对余数三大定理的灵活应用。

下面列几个例题，涉及中国剩余定理和大数求余通过同余性质化大为小