科数网
学习首页
高中数学
高中物理
微积分
线性代数
概率论
赞助
在线教程
初等数论
初等数论(高中版)
一次同余方程
最后更新:
2023-11-09 18:46
查看:
158
次
下载
编辑本文
科数网
一次同余方程
**1. 一次同余方程** 前面已经提到, 剩余类可以看作特殊的 “数”, 剩余类环可以看作是定义了剩余类加法和剩余类乘法运算的 “数集”. 类似于实数集情形, 我们也可以在剩余类环中解方程或方程组. 例如, 在模 6 的剩余类环中解方程 $[5][x]=[3]$, 这里, $[x]$ 是模 6 的剩余类环中的未知剩余类. 注意到在模 6 的剩余类环中, 有 $$ [5][x]=[3] \Leftrightarrow[5 x]=[3] \Leftrightarrow 6 \mid 5 x-3 \Leftrightarrow 5 x \equiv 3(\bmod 6), $$ 因此, 原方程可表示成下面含未知数的同余式: $$ 5 x \equiv 3(\bmod 6) . $$ 通常, 我们把含有未知数的同余式叫做同余方程. 方程 $5 x \equiv 3(\bmod 6)$ 是一类形式最简单的同余方程, 叫做一次同余方程. 一次同余方程的一般形式为 $$ a x \equiv b(\bmod n), $$ 其中 $n$ 为正整数, $a, b$ 为整数, 且 $a$ 不等于零. 若存在整数 $c$, 使得同余式 $a c \equiv b(\bmod n)$ 成立, 则把 $x \equiv c(\bmod n)$ 叫做一次同余方程 $a x \equiv b(\bmod n)$ 的解. 例如, $x \equiv 3(\bmod 6)$ 是 $5 x \equiv 3(\bmod 6)$ 的解. 如果 $x \equiv d(\bmod n)$ 也是同余方程 (1) 的解, 且 $c \equiv d(\bmod n)$, 那么我们将这两个解视作一样的. 实际上, 在这种意义下, 一次同余方程的解可理解为模 $n$ 的一个剩余类, 是一个集合, 而不是一个整数. 因此, 要判断一个模 $n$ 的剩余类是不是同余方程的解, 只需选取剩余类中的一个代表元, 看它是否使同余式成立即可. 由上面的分析可知, 解剩余类环中的方程总可以转化为解某个同余方程. 与我们熟悉的解一元一次方程、一元二次方程等过程类似, 对于一次同余方程, 我们关心下面几个问题: (1) 一次同余方程 $a x \equiv b(\bmod n)$ 什么情况下有解? (2) 有多少解? (3)有解时如何描述所有的解? $1^{\circ}$ 先讨论特殊情形, 即当 $(a, n)=1$ 的情形. 我们知道, 当 $(a, n)=1$ 时, 存在整数 $k, l$, 使得 $a k+n l=1$, 于是 $n \mid n l=1-a k$, 即 $$ a k \equiv 1(\bmod n) . $$ 因此, $a x \equiv b(\bmod n) \Leftrightarrow a x \equiv(a k) b=a(k b)(\bmod n) \Leftrightarrow x \equiv k b(\bmod n)$. 因此, 同余方程 (1) 仅有一个解 $x \equiv k b(\bmod n)$. $2^{\circ}$ 再讨论 $(a, n)=d>1$ 的情形. 若同余方程 (1) 有解, 不妨设 $x \equiv c(\bmod n)$ 为它的一个解, 则 $a c \equiv b(\bmod n)$, 从而 $n \mid a c-b$. 由于 $d|a, d| n$, 故 $d|a c, d| a c-b$, 从而 $d \mid a c-(a c-b)=b$. 这表明,同余方程(1)有解时, 必有 $d \mid b$. 那么, 当 $d \mid b$ 时, 同余方程(1) 是否一定有解呢? 记 $a=a^{\prime} d, n=n^{\prime} d, b=b^{\prime} d$, 则 $\left(a^{\prime}, n^{\prime}\right)=1$. 注意到, $$ a x \equiv b(\bmod n) \Leftrightarrow n\left|a x-b \Leftrightarrow n^{\prime} d\right|\left(a^{\prime} x-b^{\prime}\right) d \Leftrightarrow n^{\prime} \mid a^{\prime} x-b^{\prime}, $$ 于是同余方程(1)可化简为 $$ a^{\prime} x \equiv b^{\prime}\left(\bmod n^{\prime}\right) . $$ 由于 $\left(a^{\prime}, n^{\prime}\right)=1$, 由情形 $1^{\circ}$ 的讨论知, 同余方程 (2) 有惟一解 $x \equiv k^{\prime} b^{\prime}\left(\bmod n^{\prime}\right)$, 此时 $x=k^{\prime} b^{\prime}+n^{\prime} l$, 其中 $l$ 为任意整数. 对 $l, d$ 用带余除法: $l=d q+r, 0 \leqslant r \leqslant d-1$, 则 $$ x=k^{\prime} b^{\prime}+n^{\prime}(d q+r)=k^{\prime} b^{\prime}+n q+n^{\prime} r, $$ 其中 $0 \leqslant r \leqslant d-1, q$ 为整数. 于是 $$ x \equiv k^{\prime} b^{\prime}+n^{\prime} r(\bmod n), r=0,1, \cdots, d-1 . $$ 容易检验, 它们都是同余方程 (1) 的解. 综上所述, 我们得到下面的结论. 一次同余方程 $a x \equiv b(\bmod n)$ 有解, 则 $(a, n) \mid b$, 反过来, 当 $(a, n) \mid b$ 时, 一次同余方程 $a x \equiv b(\bmod n)$ 恰有 $(a, n)$ 个解. 下面看一个解一次同余方程例子. **2. 大衍求一术** 对于一次同余方程的解法, 我们古代一些数学家曾做出过巨大的贡献, 其中比较有名的是一衍求一术. 大衍求一术是解一次同余方程 $a x \equiv 1(\bmod n)$, 其中 $a$ 为正整数, $a<n$, 且 $(a, n)=1$的一种算法程序. 我国宋代大数学家秦九韶(约 1202 - 约 1261)继承前人造历算法经验,在其所著的《数书九章》中给出了解法: 秦九韶称 $a$ 为衍母, $n$ 为定母, 并称满足同余式的最小正整数为乘率. 大衍求一术的 法则是: 置衍右上, 定居下. 立天元一于左上. 先以右上除右下, 所得商数与左上一相生并人左下. 然后乃以右行上下, 以少除多, 递互除之. 所得商数, 随即递互累乘. 归左行上下……须使右上末后奇一而止. 乃验左上所得, 以为乘率. 用现代数学的语言, 大衍求一术的算法步骤可表述为: 先规定 $k_1=1, r_1=a$, 对 $n, a$ 用带余除法: $n=a q_2+r_2$, 记 $k_2=-q_2 k_1$; 对 $a, r_2$ 用带余除法: $a=r_2 q_3+r_3$, 记 $k_3=k_1-q_3 k_2$; 对 $r_2, r_3$ 用带余除法: $r_2=r_3 q_4+r_4$, 记 $k_4=k_2-q_4 k_3$; 对 $r_3, r_4$ 用带余除法: $r_3=r_4 q_5+r_5$, 记 $k_5=k_3-q_5 k_4$; 重复这种运算, 直到余数 $r_n=1$, 那么最后所得 $k_n=k_{n-2}-q_n k_{n-1}$ 满足 $a k_n \equiv 1(\bmod n)$. 于是 $x \equiv k_n(\bmod n)$ 就是一次同余方程 $a x \equiv 1(\bmod n)$ 的解. 下面考察一下大衍求一术的算法原理. 我们发现, $$ \begin{aligned} & r_1=a=a k_1(\bmod n), \\ & r_2=n-r_1 q_2 \equiv a\left(-q_2 k_1\right)=a k_2(\bmod n), \\ & r_3=r_1-r_2 q_3 \equiv a\left(k_1-q_3 k_2\right)=a k_3(\bmod n), \\ & r_4=r_2-r_3 q_4 \equiv a\left(k_2-q_4 k_3\right)=a k_4(\bmod n), \\ & \cdots \cdots \end{aligned} $$ 而 $r_n=1$, 故 $a k_n \equiv 1(\bmod n)$. 这就是大衍求一术的算法原理. 下面看一个用大衍求一术解同余方程的例子. 例 6 解同余方程 $33 x \equiv 1(\bmod 74)$. 解: 显然 $(33,74)=1$. 由于 $74=33 \times 2+8,33=8 \times 4+1$, 故 $q_2=2, q_3=4, r_3=1$. 依次可计算出 $$ k_2=-2 \times 1=-2, k_3=1-4 \times(-2)=9 . $$ 因此原方程的解为 $$ x \equiv 9(\bmod 74) . $$
上一篇:
费马小定理与欧拉定理
下一篇:
拉格朗日插值法和孙子定理
本文对您是否有用?
有用
(
0
)
无用
(
0
)
科数网知识库旨在打造一个可以顺序阅读的在线电子学习教程,点击顶部的
编辑本文
来完善本文,如果本文对您有用,也欢迎
赞助我们
0
篇笔记
写笔记
更多笔记
提交笔记