【离散数学中的数据结构与算法】一最大公约数与最小公倍数之间的关系

╰半橙微兮° 2022-03-10 08:50 198阅读 0赞

> ### 文章目录 ###
> 
>  *   *  1 算数基本定理
>      *  2 最大公约数
>      *  3 最小公倍数
>      *  4 性质
>      *  5 推论

## 1 算数基本定理 ##

设正整数 n>1， 则 n 可唯一地表示为：

![在这里插入图片描述][20190310142441913.png_pic_center]  
其中 p1<p2<,…, <ps 是 s 个相异的素数， 指数ki都是正整数。 此定理又称作唯一析因定理（unique factorization theorem） 。 该表达式称作整数 n 的素因子分解。

> 例如：  
> ![在这里插入图片描述][20190310142609270.png_pic_center]

## 2 最大公约数 ##

设 a 和 b 是两个不全为 0 的整数，若整数 d 满足 d|a 且 d|b， 则称 d 是a, b 的公因子（common divisor），也称最大公约数。

所有公因子中最大的称作 a 与 b 的最 大 公 因 子 （ greatest common divisor） ， **记作 GCD(a, b)**

## 3 最小公倍数 ##

设 a 和 b 是两个不全为 0 的整数，若整数 m 满足 a|m 且 b|m ， 则称 m是 a, b 的公倍数（common multiple）

所有公倍数中最小的正整数称作a与b 的 最 小 公 倍 数 （ least common multiple） ， **记作 LCM(a, b)**

## 4 性质 ##

对任意的正整数a有：

*  GCD(0, a)=a
 *  GCD(1, a)=1
 *  LCM(1, a)=a

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 1]

## 5 推论 ##

设a, b是正整数， 则：

![在这里插入图片描述][20190310142758803.png_pic_center]

[20190310142441913.png_pic_center]: /images/20220310/1b7d3dcfe4c94efea3df60f61c24d99d.png
[20190310142609270.png_pic_center]: /images/20220310/ac996a16b7a74db98452fc97c9b25687.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center]: /images/20220310/54350a01b9254c9dae61bb4c4e5c3397.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9seXktMDIxNy5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220310/6ad06c56a20b4319b51b2793fc50746d.png
[20190310142758803.png_pic_center]: /images/20220310/ff749a7ca4c140f78256eea66a864eba.png