初等数论《 余数 》 习题集  (连载 1)

 

目     录

 

前言：我为什么要做初等数论《余数》习题 

余数问题解算方法概述   

习题 (63题)  

 

 

前言：我为什么要做初等数论《余数》习题

 

我做《余数》习题的目的，是想通过做习题，来清理一下我的极其肤浅的余数知识。看能解算什么难度的余数问题。

余数问题本质上是带余数的除法，例如9÷4=2 … 1等等，虽然是小学生的题目，但一旦深入，就难倒中学生、大学生。尤其是“同余方程”，在高斯的《算术探索》( 潘承彪 张明尧 译 ) 中有开创性的叙述，但读起来就如读天书一样了。

在看了一些“小学数论”的视频后，就觉得“余数问题”并不简单，有的还很难，甚至还不习惯它的解题方法。我就要考考自己，看能否做这样的习题。于是从笔记上、网页上、奥数书上收集了一些习题做一下。为了有点条理，大致分以下几类：

1、 求余数R。

在A÷B=X … R 的带余数除法中，引进“整除”规律，来求余数。有时，根据不同条件，还混合求A、R ，或B、R ，甚至求商的个数等等。解算花样就多了。

2、 求除数B

在余数方程组中，余数有相同的、有不同的、或余数间有一定关系的。根据情况，分别解B。

3、 求被除数A。

在余数方程组中，也根据余数R的同余与不同，分别情况，分别解之。

其中“A除以B₁余几、除以B₂余几、除以B₃余几  … ” 就是孙子问题，即中国剩余定理。我在解算时，摸索出一个“逐级公式解法”。这可能是我这次做《余数》习题的最大收获了。

 

翻看一下《多功能题典——小学数学竞赛》，其中“数论初步”的“带余数除法”部份43道题，我真正能做出的或大致理解的，只有10道而已，只得23分。

我避开难题，坚持做了63个习题。我的肤浅的余数知识，只能清理到此，便识相，到此为止。这本习题集，虽然也有少量奥数型题目，但大致上只是初等难度的习题。水平如此，只能如此。真的，我不想再折腾自己、难为自己了。

 

余数问题解算方法概述

 

※ 1     先看三个余数定理：

 

1、 余数的加法定理，简言之：加的余数等于余数的加。

2、 余数的乘法定理，简言之：乘积的余数等于余数的乘积。并扩充为乘幂的余数等于余数的乘幂。

3、 同余及同余定理。

同余：若两个整数A ₁、A ₂被自然数B除，有相同的余数R，那么称A ₁、A ₂对于模B同余，用式为：A ₁≡A ₂ ( mod B )，叫做同余式。读作：A ₁同余于A ₂  模B。

例如   16÷7＝2 … 2      

            37÷7＝5 … 2    

65÷7＝9 … 2      

由于   16－7×2 ＝ 2  、37－7×5 ＝2 、  65－7×9 ＝2  ，三式余数相同，所以16、37与65在一定条件下是互相等效的，但不能叫相等，而称37、16对于模7同余，65、37对于模7同余。而所谓模，其实就是除数而已。写作：

        37≡16  ( mod 7 )   

65≡37  ( mod 7 ) 

如此说来：

16≡9  ( mod 7 )

     37≡9  ( mod 7 )

65≡9  ( mod 7 ) 对于模7，它们也都是同余的（实际是同余2）。

而  16≡2  ( mod 7 )

37≡2  ( mod 7 ) … 直接把余数2表示出来，这才是最简明、最“小”、最基本的同余式了。

 

同余的两个推论：

一、  已知被除数A ，求除数B。由同余的性质，得到一个非常重要的推论：A ₁－A ₂＝BK 。即：

除数B是多个被除数A之间的差 ( A _I－A _J )的最大公约数。  B＝( A₁  A ₂  A₃  … )

如  16÷B＝X … 2     

            37÷B＝Y … 2   

65÷B＝Z … 2

(A ₂－A ₁)  → 37－16 =21    →   21的约数有1、3、7、21

(A ₃－A ₁)  → 65－37=28    →   28 的约数有1、2、4、7、14、28

21、28的最大公约数(21 ，28 ) = 7  。所以B只有1个：B = 7

同余定理的作用就是消去同余，使之成为整除，并在约数中找到除数B的解。

 

二、  已知除数B ，求被除数A 。由同余的性质，又得：

被除数A＝各除数B的最小公倍数＋同余量R 。A ＝〔B₁  B₂  B₃ 〕＝ B₁ B₂ B₃ ＋R

如  A ≡ 2  ( mod  3)

A ≡ 2  ( mod  4)

A ≡ 2  ( mod  5)   则：

A ＝〔B₁  B₂  B₃ 〕＋R＝3×4×5＋2 ＝62

同余的这两个推论，是解算余数问题的一把钥匙。

 

※ 2   用单式求余数R (1—21题)

 

一、  在A÷B=X … R 的带余数除法中，被除数A是很大的数，甚至是指数很大的幂。除数B则是特殊的3、7、9、11、13、99等，把“整除”规律引进来求余数。算除数时，只作判别，及少量除法。

二、  被除数A是很大的数，但除数B不是特殊的3、7、9、… 可引用余数的加法定理：加的余数等于余数的加，可使解算简单一些。如：

1849÷14的余数等于多少？由于1849＝1000＋800＋40＋9，而1000、800、40、9的余数分别为

6 、2 、12 、9，所以1849÷14的余数等于6 、2 、12 、9，之和6＋2＋12＋9＝29，而29÷14的余数为1，所以1849÷14的余数也等于 1。不过具体分拆大数时，要讲究机巧。如1849可分拆为1400+420+29，则三个余数为0、0、1，最后1849÷14的余数等于 1。

三、   被除数A是很大的数相乘，可引用余数的乘法定理：乘积的余数等于余数的乘积。

如：16×47×109÷14的余数等于？由于16、47、109的余数分别为2、5、11，（这三个余数要具体算）所以16×47×109÷14的余数等于2×5×11＝110。而110÷14的余数为12，最终余数为12。

四    被除数A是指数很大的幂。如2²⁴⁰÷7＝？

将2²⁴⁰ 化为2^3×80 ＝8⁸⁰  由于8÷7的余数是1，而1⁸⁰ 的余数也是1。所以2²⁴⁰÷7的余数是1。不过，幂的分解也不是那么省力的，需要灵巧、经验。我辈自感无能，只理解它的思路和方法而已。

五   A÷B，通过试算，先找余数的循环节，再判具体余数。见15、16、18题。

 

※ 3   用单式或两式求A 、B  (22—31题)

 

一   根据不同条件，同时求A、R，或B、R，甚至求商的个数等等。解算花样就多了。

 

 

※ 4   用方程组求除数B  (32—42题)

 

一    同余时，除数B就是两被除数A之差 (A₁－A₂)中的一个最大公约数。B＝( A₁  A ₂  A₃  … )

二    余数R之间有某种关系。利用这种关系，通过加、减、乘，使它们变为同余。再用同余定理解算B。

三    或通过加、减、乘，使它们变为整除形式的不定方程，解方程得B。

 

※ 5   用方程组求被除数A (43—64题)

 

一   同余时，被除数A＝各除数的最小公倍数＋同余数。A ＝〔B₁  B₂  B₃ 〕＝ B₁ B₂ B₃ ＋R

二   余数间有某种关系。设法通过加、减、乘，使它们变为同余。

三   先通过乘，使它们的除数相同，成为一组等价的不定方程组。再通过加、减，变成一个不定方程式，解得A。这个方法也很有效。反正只解一次不定方程而已。见61题

四   我发现，这些不定方程组的前后方程之间，是有一定关系的，即它们都应满足一个不定方程：

 ( 第一方程的通解A ₁－第二方程的余数R ₂)÷第二方程的除数B ₂ ＝☆(整数)，即可求得两个方程的最小解及通解A₂ 。再用同样方法，求第三个通解…，逐级计算一个个不定方程，便可得到最终结果A。见58、63题

五    “孙子问题”的古老传统的“大衍求一术”，解法见63题。我又十分轻松的编了一个Basic程序，让它再作现代化的演算，作为这本《习题集》的终结。

 (待续)