下面我们先对同余式的基本概念以及一次同余式解法的相关知识做一些概述。
2 基本概念及一次同余式
定义1[ ] 若用 表示多项式 ,其中 是整数;又设 是一个正整数,则
叫做模 的同余式。 若 ,则 叫做(1)的次数,称(1)式为 次同余式。
定义2[ ] 设 是整数,当 时式(1)成立,则称 是同余式(1)的解。 凡对于模 同余的解,被视为同一个解,同余式(1)的解数是指它的关于模 互不同余的所有解的个数,也即在模 的一个完全剩余系中的解的个数。
由定义2可知,同余式(1)的解数不超过 。
定理1[1] 一次同余式 (2)
有解的充分与必要条件是 。 若有解,则恰有 个解。
定理2[1] 如果 是(2)的某一特解,则(2)的全部解是 , 。
因此,当一次同余式有解并且有不只一个解时,关键是求出它的一个特解。
设 , , , ,则必有 ,此时可以取一次同余
式 的唯一解叫做 的一个特解[ ]。
综合上述,我们知道一次同余式的求解关键在于求解有唯一解的一次同余式,然后再利用定理2得出其全部解。 因此,下面我们仅对 , 形式的一次同余式进行研究。
3 一次同余式的解法及其分析
3。1 代入求解法
由定义2可知,在求一次同余式 的解时,仅需要将模 的一个完全剩余系(如 )中的每一个数代入同余式中逐一验证,即可求出其全部解。
例1 解同余式
。
取模5的最小非负完全剩余系0,1,2,3,4,分别代入同余式 中,知 满足同余式,故同余式的解为 。
代入求解法需对模 的完全剩余系中的每个数逐一进行验证。 当模 的值较小时,可以直接利用代入求解法快速得到同余式的解;当模 较大时,若是把完全剩余系中的每一个数代入同余式中逐一验证,过程十分繁琐。 因此,当模 的值较小时适用此法。
3。2 欧拉定理法
欧拉定理是初等数论中非常重要的一个性质定理,利用欧拉定理并结合同余的相关性质可以得到一次同余式的一种公式解法。
定理3(Euler定理)[ ] 设 是大于1的整数, ,则 ,其中 是正整数 的欧拉函数值。
定理4[1] 设 是整数, ,则一次同余式的解为 。文献综述
例2 解同余式
。
因为 ,由定理4可知同余式的解为 。
欧拉定理法给出了一次同余式的一个公式解,用此法求解一次同余式时可以直接代入公式,这往往比较简单,在理论上易于分析。 但当模 的值较大时, 的求解则需要涉及到 的标准分解,较为复杂。 所以此方法更适合当模 的值较小时或当 较易求得时使用。
3。3 求 法
利用最大公因数的性质并结合同余的相关性质,可得到求解一次同余式的又一种方法。
因为 ,所以一定存在整数 ,使得 。 此时必有 ,于是得到 ,因为 ,所以以下三式
互相等价,因而同余式 的解为 [ ]。 例3 解同余式
。
因为 ,所以一定存在整数 使得 。 利用辗转相除法求得 , ,于是 。 又因为 , ,所以同余式的解为 。
求 法的关键在于如何利用最大公因数的性质求出 。 此法的步骤简明、思路清晰。 但是有时 并不是那么容易求得,特别是当 都较大时,所以此方法更适用于当 的数值较小时。
3。4 分式法
接下来,我们介绍一次同余式的分式解法。 一次同余式的解法及应用(2):http://www.youerw.com/shuxue/lunwen_86457.html