离散数学学习——简单的数论基础

2018-12-30 本文已影响0人牧尘_916c

关于在离散数学中的除法

数学中很基本的运算加减乘除，本次主要讨论的是在离散数学中的除法，而除法通常会涉及到余数，通常用 mod 来表示求余数运算，而用a|b来表示a是b的因子，那么，很容易证明下面的定理：

$若a|b，b|c，则a|c（传递性）；若a|b，a|c，则a为b，c的公因子；若a|b，c|b，则b为a，c的公倍数；$

那么就有最大公约数和最小公倍数，分别记作GCD(Great Common Divisor)和LCM(Least Common Multiple)。

提到最小公倍数和最大公约数就必须提到的一个数学概念就是素数，所谓素数，就是仅仅只有1和本身这两个因子，那么，需要介绍一个定理——算术基本定理（Arithmetic Fundamental Theorem）：

$若n>1且n\in N,则，n可以唯一地表示为p1^{k1} p2^{k2}p3^{k3} ...ps^{ks}$

其中p1，p2，...ps为互不相同的素数。

那么最大公约数即可以表示为：

$p1^{min{a1,a2}} p2^{min{b1,b2}} p3^{min{c1,c2}} ...ps^{min{k1,k2}}$

最小公倍数可以表示为：

$p1^{max{a1,a2}} p2^{max{b1,b2}} p3^{max{c1,c2}} ...ps^{max{k1,k2}}$

所以，a*b=GCD(a,b)*LCM(a,b)。