初等数论初步中大衍求一术的介绍中的k1,k2…kn代表什么,又是怎样得出的
发布网友
发布时间：2023-09-07 16:23
共1个回答
热心网友
时间：2023-09-18 00:26
乘率，同余逆，同余倒数，模逆，都是说的同一概念。
例如，
ax==1 mod m
其中的 a与x互称为基于(关于、对于)模m的乘率，简称乘率。
若已知a求x, 就说求a关于模m的乘率，或简单地说求a的乘率.
这个同余式也相当于ax+my=1，于是my==1 mod a, 此时m与y也互为关于模a的乘率。
其中为打字方便，用双等号==取代三线等号≡表示同余。
BBB 注意事项：
一、求乘率，就是求解同余式，该同余式有一侧为定值1；或者是求解含有常数1作为和项的二元一次三项不定方程。否则一般不称为求乘率。
二、利用中国剩余定理同余式组，利用到乘率。但是，不利用乘率也可以直接解同余式组的，就像解多元方程组的矩阵方法，并不是一定要求逆矩阵一样。中国剩余定理解同余式，与解多元一次方程组或矩阵方程中用到的线性叠加方法原理是一样的，我们应当利用线性叠加原理而灵活变化。
CCC 求乘率的例子
CCC 例1(求乘率)： 13x==1 mod 23
方法1-1：
13x==1 mod 23
两边乘2得
26x==2 mod 23
3x==-21 mod 23
x==-7==16 mod 23
用洪伯阳同余记法，可用分数形式表示同余，再转换为整数形式，如下：
x==1/13==2/26==-21/3==-7==16 mod 23
方法1-2：
13x==1 mod 23
-10x==1 mod 23
-10x==70
x==-7==16
用洪伯阳同余记法，即x==1/13==1/-10==70/-10==-7==16 mod 23
方法2-1：
使用不定方程。对于较复杂的情况，很适用。
下面是经我改写了的一种解不定方程的方法，较常规教科书思路略有不同，计算较为方便。后文有略微复杂的几个例子，作了详细说明。
13x==1 mod 23
13x=1+23y
将13的倍数合并到13x这一项上并使用新的变量，得
13z=1-3y
易见可取特值y=-4，代入即得 x=-7。于是x==-7==16 mod 23.
DDD 注意对mod的一个重要认识：
由13z==1-3y 也可直接解出 y=-4 mod 13，或写成 y=-4+13t
代入13x=1+23y 立即得 x= -7+ 23t == -7 mod 23
事实上，我们应当认为 mod 13 与 +13t 地位相当本质相同。
（mod 13） 本质上即是 +13 的任意倍数，我常常写成 +13**或13**+（放在左边时用13**+）， 表明不使用具体的符号来表示出这个任意的倍数。
将mod13看作成+13**，于是立即知道它可以在同余式的代数和项或乘积的因数项上任意加减、滑移（包括等式左右两边移项）而不影响式子的性质。任意加减与滑移，只是这个任意倍数**发生了变值（包括改变正负号），而我们不关心因子**的值，故不需要去管它的形式，照样用**代替即是。
使用 （mod 13）这种形式，就已经不再注意这个任意倍数了，其加减与滑移特性赋予了它极大的自由；使得它成为一个平台，相当于物理学中的“以太”一样了；而同时让我们将着眼点更好的放在其他变量的分析上。
而使用 （+13 t ）这样的形式，则便于对变量进行称名引用。这种形式下，同余式即是不定方程，，方便于对模13的倍数进行定量跟踪分析，还可以在转换到（即重定位到）其它模与变量时不致混淆关注点（视点）。而转换模与变量，在解复杂的、难于计算的不定方程（包括同余式转化来的不定方程）是很好的方便的手段之一。
方法2-2
13x==1 mod 23
13x=1+23y
13z=1+10y
易见可取z=7, y=9，代入得x=16 mod 23
这个代入计算的过程略微不便计算，可以这样简化：
将两式比较，得x-z=y, 故 x=z+y=16 mod 23
CCC例2(求乘率)：
103x==1(mod211)
解：206x==2
-5x==2*1
-5x==2*-210
x==84
洪伯阳表示法：x==1/103==2/206==2*1/-5==2*-210/-5==84
CCC例3(求乘率)
开譆历上元积年377873x≡1(mod499067)的乘率解：
用洪伯阳记号解，由于不便于重定位模对象，故此在不做为首选方法，见后文。
先用我改写了的不定方程解法来解。
这种不定方程解法的要点：
要点1，其中使用双等号==取代等号=，以保证在使用同余关系时的扩展，从而使用了连等式，连等式各项使用同余关系相关联。
一个连等式系列之中，取最前与最后二者，可改用等号连接形成等式，以此为依据进行变量的定量化分析。
要点2，辗转相除法求最大公约数或求乘率、大衍求一术求乘率均可以用我这种思路改写成为不定方程。
要点3，使用连等式，可保留中间计算过程，利于辅助记忆。如果笔算或口算或心算，记忆起来轻松一些，下面的过程主体是我一边打字一边心算完成的。
要点4，其中变量便于称名引用，过程中的对象位置能够方便的对应，思路很为连续方便。
要点5，在不定方程中使用了具体的变量名，因而转换到（即重定位到）其它模与变量时不致混淆关注点（视点）。而转换模与变量，在解复杂的、难于计算的不定方程（包括同余式转化来的不定方程）是很好的方便的手段之一。这一点前文也讲到过了。
要点6，开始步骤与中间步骤都是对上一个不定方程式按较小的模进行并项得到下一个不定方程，并使用新的变量而不使用累次的代换关系，也不涉及复杂的分式，简洁明快。
要点7，最后反推步骤，利用到了最后一个显然易解的不定方程，及所得到的所有相邻不定方程之间相比较得到的关系式，使计算涉及到的数值总体减小。
在求值时，可以使用具体值参予计算，也可以继续使用变量，很自由方便。
377873x==1+499067y
377873z==1+121194y 注：即将377873的倍数集中到原来的377873x这一项上并改用新变量。
014291z==1+121194a
014291b==1-021716a==1+6866a 注意，与前一式相比，14291的因子变量被改写。
注意，此处使用了连等式，连等式对模14291构成同余等价关系。在连等式中以最前与最后二者以等号连接构成等式而进行定量分析。
559b==1+6866c
559d==1+1276c==1+158c 注意，此处连等式对模559构成同余等价关系。
-73d==1+158e
-73f==1+12e
取e=6, 逆求之可得解。过程可以如下：
{
将保留下来的各个算式，相邻两式两两比较，顺次得到：
x-z=y
3z=y-a
z-b=8a
2b=a-c
b-d=12c
4d=c-e
-d+f=2e
将e=6,f=-1代入，逆求。原先发文曾略去计算过程。此次补充，逆求如下：
d=-13,
c=-46,
b=d+12c,
a=2b+c=2d+25c
z=b+8a=17d+212c
y=3z+a=53d+661c,
x=z+y=70d+873c=(-910+873*(-46))
将上面的项复制到windows计算器(在windows操作系统开始菜单-运行：calc.exe-科学型)，算得
x==-41068 mod 499067
x==457999
}
用计算器检验，457999*377873 mod 499067 ==1
检验正确.
一般取正数为乘率，取负数也是不影响计算的，故二者均均可做为乘率。
CCC例3续：以下用洪伯阳记号来解377873x==1(mod499067)
用洪伯阳记号来解，可以有一个相当于下面的过程：
-121194x==1
-484776x==4
14291x==4（#1#）
142910x==40
21716x==41（#2#）
（#1#）*-3+（#2#）*2得 （这在洪伯阳表示式，即分数形式的同余表示中，相当于对分数连等式使合比定理，以下类似。）
559x==70（#3#）
由（#2,3#）得
注：21716=559*39-85
-85x==41-70*39==-2689 （#4#）
由 （#4,3#）得
注：559=85*6+49
49x==70+-2689*6=-16064 （#4#）
由 （#4,5#）得
-36x==-18753
故12x==6251==-492816
x==-41068
x==457999
用洪伯阳表示，写作：
x==1/377873 ==1/-121194==4/-484776==4/14291==41/21716==70/559==-2689/-85==-16064/49==-18753/-36=6251/12==-492816/12==-41068==457999
注：用洪伯阳记号解，由于不便于重定位模与变量对象，中途利用合比定理略嫌复杂，故此在不做为首选方法，以不定方程法为最佳。
CCC例4(求乘率)
907X≡2107（mod731）的两个乘率
注：后文将另行求解同余式907X≡2107（mod731），使用不定方程 907x+731y=2107来解。
由前面讲过的乘率的概念，我们认为此题求乘率即是求解两个同余式：
907x==1 mod 731 及 731y==1 mod 907，这两个同余式是等价的，可互相转换的，仅是着眼点不同。
同时也相当于不定方程 907x+731y=1.
解：
907x+731y=1
176x+731z=1
176a+27z=1
14a+27b=1
取a=2，反推即可求出x,y。下面采用另一种方式以简捷计算。
比较上述各式之两邻相式，分别得
x+y-z=0
x-a+4z=0
6a+z-b=0
下面已知a=2,b=-1,故z=-13,x=54,y=-67
也可以这样：
907x+731y=1
176x+731z=1
176a+27z=1
-13a+27b=1，由a=2反推。
比较上述各式之两邻两式分别得
x+y-z=0, x-a+4z=0,7a+z-b=0, 由a=2,b=1得z=-13,x=54,y=67
CCC例5（求乘率）
3800k≡1（mod27）
注：转化为解不定方程
3800x+27y=1
20x+27z=1
易见或取z=3,x=-4; 两式比较得140x+y-z=0，故y=-140x+z=563
EEE 非求乘率型的同余式的求解
EEE 例6
方法1
103x==57(mod211)
x==57/103==114/-5==325/-5==-65 mod 211
方法2:不定方程法：
103x=57+211y
将103x的倍数集中到103x上并使用新的变量:
103z=57+5y
易见可取z=-1, y=-32，这时可以代入计算出x,也可以用下面的思路简化计算。
上述两式比较，易见 x-z=2y, 故x=z+2y=-65. 即原同余式解为 x==-65 mod 211.
EEE 例7 解同余式 907X≡2107（mod731）
相当于求解不定方程
907x+731y=2107
解：
176x+731z=-86
176a+27z=-86
-13a+27b=-5
(-13c+b=-5)
取b=-5,c=0逆求即可。
当然也可以由-13a+27b=-5这一步直接看出可取b=-5，a=-10进行逆求。但引入-13c+b=-5会减轻心算之记忆负担。
比较上述各式之两两相邻式子，得
x+y-z=3
x-a+4z=0
7a+z-b=-3
(-a+c+2b=0)
于是由c=0,b=-5,a=-10得 z=-7a+b-3=62,x=a-4z=-258,y=-x+z+3=258+62+3=323
