4.4 一次同余方程
18
本章目录 · 1 节
本章导读
设 ,使 成立的整数 称为该一次同余方程的解。解通常以模 的剩余类表示,而不是只列出一个普通整数。若 为解,所有与 模 同余的整数也都是解,但一般还可能存在其他解类。例如 无解,因为左侧恒同余于0。
定理4.4.1:方程有解当且仅当 整除 。必要性:由 可知共同因子 整除右侧。充分性:若 ,则 ;选贝祖系数 使 ,乘 即得到一个整数解 。
求解可分两步:先检查 ;成立时,方程约为 ,其中系数与模数互素,求出唯一的模 解。若需按原模数 列出全部解类,可写为
这些解类互不相同,故恰有 个;作为整数解集合则为 。模数缩小后的一个类,与原模数下的 个类,是同一个整数集合的不同描述。
【例4.4.1】解 。
解:,且 ,所以有解。约去共同因子时模数也除以2,得 ,即 。按模6写为 ,与教材的 相同。全部整数解为 ,最小正整数解为2。直接检验 。
定义4.4.1:若 ,称 为 的模 逆,记 。这是模乘法的逆,不是普通实数倒数。通常实际计算取 ,并选0至 中的代表;本章正模数定义若允许 ,则所有整数模1同余,逆的“唯一性”仍仅指唯一剩余类。
定理4.4.2:模逆存在当且仅当 ;存在时模 唯一。存在性由一次同余方程的判据得到。若 ,则 ,利用互素条件消去 ,得 。这不表示整数代表只能选一个,代表之间可相差任意整数倍 。
【例4.4.2】求5模7的逆。
解:直接观察 ,可取逆为3。也可枚举模7的七个类;较大数则用扩展欧几里得算法:,回代 ,同样得到 。先检验互素,再求系数,可避免对无逆元素强行求逆。
