整除与最大公约数

作者: 人类发展观察者 | 来源:发表于2019-06-29 12:59 被阅读0次

程序题
整除与最大公约数
数论——欧几里得算法
最大公因数，最小公倍数
伪·从零开始学算法 - 2.2 求最大公约数
算法笔记(7)| 数学问题(1)
【python】使用二进制求解最大公约数？
【初等数论】整除、公约数、同余与剩余系
js递归实现最大公约数与最小公倍数
最大公约数

定义 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的最大公约数。

程序题
求两个正整数的最大公约数数组反转闰年: 能被4整除且不能被100整除或者能被400整除
整除与最大公约数
定义 1 a，b为整数，如果,，a必定能整除b，记为(读作a整除b)。定理 1 假设，且,则任何都有。证明过程...
数论——欧几里得算法
欧几里得算法介绍【欧几里得算法】又名辗转相除法，是求最大公约数的算法。两个整数的最大公约数是能够同时整除它们的...
最大公因数，最小公倍数
1、最大公约数：几个数都能被同一个数一次性整除，这个数就叫做这几个数的最大公约数。(或几个数公有的约数，叫做这几个...
伪·从零开始学算法 - 2.2 求最大公约数
简介两个或多个正整数数的公约数是，对于这些数，存在一个正整数，可以整除它们。公约数可能有若干个，而其中最大的就是...
算法笔记(7)| 数学问题(1)
1.最大公约数与最小公倍数 1.最大公约数最大公约数是指正整数a和b中都能够除尽的最大的数。解决最大公约数是方法...
【python】使用二进制求解最大公约数？
题目：两个整数x，y，它们的最大公约数d必须满足d|x，而且d|y。其中符号“|”表示整除，d|x表示x是d的倍数...
【初等数论】整除、公约数、同余与剩余系
整除、公约数、同余与剩余系从本文开始，我们将正式开始介绍有关初等数论的相关知识与概念，我们争取用通俗的语言去把握...
js递归实现最大公约数与最小公倍数
先说一说关于最大公约数与最小公倍数怎么算的; 两个数A B相除取余C，第二个数B除C取余，直到整除，那么被除数被最...
最大公约数
最大公约数自然数d同时是a,b的约数，称d是a和b的公约数，d是a和b的公约数中最大的一个，d就是最大公约数，记...