公因数与互质数（非对称加密基础）

由于本人对数学的一些基本知识已经忘记了，所以在此下此笔记，以便日后查看

一、公因数

亦称“公约数”。它是一个能被若干个整数同时均整除的整数。如果一个整数同时是几个整数的因数，称这个整数为它们的“公因数”；公因数中最大的称为最大公因数。

二、互质数

公因数只有1的两个非零自然数，叫做互质数。

三、举个例子

3.1 公因数

4 8 16
# 它们同时能够被1 2 4整除，所以1 2 4就是4 8 16的公因数（公约数）
5 10 20
# 它们同时能被1 5整除，所以1 5就是这三个数的公因数（公约数）
9 15 18 24
# 它们同时能被1 3整除

3.2 互质数

从定义看，我们知道，互质是公约数只有1

4 8
# 显然不是，因为4 8的公约数不只1，还有2和4
1 2
# 公约数只有1，所以这个就是
# 5 9、8 11、2 3等等，这些都是互质数