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

关于在离散数学中的除法

数学中很基本的运算加减乘除，本次主要讨论的是在离散数学中的除法，而除法通常会涉及到余数，通常用 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)。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容