整除与最大公约数

2019-06-29 本文已影响0人人类发展观察者

定义 1

a，b 为整数，如果 $b = ak$ , $k \in Z$ ，a 必定能整除 b，记为 $a \mid b$ (读作 a 整除 b)。

定理 1

假设 $a, b \in Z$ ，且 $a \mid b$ , 则任何 $c \in Z$ 都有 $a \mid bc$ 。

证明过程:

由 $a \mid b$ 可知, 存在 $k \in Z$ 使得 $b = ak$ ;

两边乘以 c 得到 $bc = (ak)c = a(kc)$ ， $kc \in Z$ ，

所以 $a \mid bc$ 。

定理 2

如果 $a \mid b$ 且 $b \mid c$ ，那么必有 $a \mid c$ 。

证明过程:

由 $a \mid b$ 可知，存在 $k \in Z$ 使得 $b = ak$ ;

由 $b \mid c$ 可知，存在 $h \in Z$ 使得 $c = bh$ ；

进而得到 $c = (ak)h = a(kh)$ , 又 $kh \in Z$ ,

所以 $a \mid c$ 。

定理 3

如果 $a \mid b$ 且 $a \mid c$ ，则任何 $r, c \in Z$ 都使得 $a \mid (br + cs)$ 。

证明过程:

由 $a \mid b$ 可知，存在 $k \in Z$ 使得 $b = ak$ ；

由 $a \mid c$ 可知，存在 $h \in Z$ 使得 $c = ah$ ；

进而 $(br + cs) = (akr + ahs) = a(kr+hs)$ ，又 $(kr + hs) \in Z$ ，

所以 $a \mid (br + cs)$ 。

定义 2

能同时整除非零整数 a，b，且为其中最大的数是这两个数的最大公约数(greatest common divisors)，记为 $(a, b)$ 。

公理 1

两数互质，其最大公约数必为 1。

定理 3

定理 5

能整除两数之差，必定与两数有相同的最大公约数。即

$m \mid (a - b) \Rightarrow (a, m) = (b, m)$ $(a,b,m \in Z)$

证明过程:

由 $m \mid (a - b)$ 可知必定存在 :

$k_{a}, k_{b},r \in Z_{\geq 0}$ ， $r < m$ 使得：

$\begin{align*}a &=(mk_{a} + r) \\b &=(mk_{b} + r) \\\end{align*}$

由此可知, 当 r 等于 0 时， $m \mid b, m \mid a \Rightarrow (m, a) = (m, b) = m$

当 r 大于0 时， $m \nmid b, m \nmid a$ ，

假设 $d = (a, m)$ , 则有

$\begin{align*} m &= dk_{m} \\ a &= dk_{a} \end{align*}$

定理 5

假设 a，b 均为非0整数。以a 为被除数，b 为除数相除，求余得 r；用除数作为下一轮的被除数, 用余数作为下一轮的除数求余，以此类推；直到求出最后一个不为0的余数，即为 a，b的最大公约数。

上一篇下一篇

猜你喜欢

热点阅读