与素数有关的一些性质及证明（一）

文章目录

• ​​写在前面​​
• ​​素数、合数​​

• ​​定理：带余除法​​

• ​​整除、因数​​

• ​命题：除数整除被除数的倍数和​​

• ​​公因数、最大公因数​​

• ​​除数与被除数的最大公因数等于除数与余数的最大公因数​​
• ​​辗转相除法:求两整数最大公因数的统一方法​​

• ​​互素​​

• ​定理：两整数互素的充要条件​​

• ​​证明​​

• ​​互素整数的重要性质及推广​​

• ​​素数的重要性质​​

• ​​证明​​

• ​​算术基本定理​​

写在前面

最近学习了丘维声教授的课程《数学的思维方式与创新》，总结一下课程中关于素数的一些主要性质及证明。

素数、合数

设是大于的整数，如果的正因数只有和自身，那么称是一个素数（或质数），否则称是合数。

定理：带余除法

任给，且，则存在唯一的一对整数，使得

其中，和分别称为被除所得的商和余数。

整除、因数

对于整数，如果存在整数，使得

那么称整除，记作，否则，称不能整除，记作。当时，称为的一个因数，称为的一个倍数。

• 任给，由于，因此，特别地，。
• 整除具有反身性，传递性，但是没有对称性。

命题：除数整除被除数的倍数和

在中，若，则对任意整数，有

公因数、最大公因数

• 如果且，那么称是与的一个公因数（公约数）。
• 整数与的一个公因数如果满足：与的任一公因数都能整除，那么称是与的一个最大公因数（最大公约数）。
• 约定： 用表示两整数间正的最大公因数。
• 任给，由于且，所以是与的一个公因数，任取与的一个公因数，显然，所以是与的一个最大公因数。
• 特别地，是与的最大公因数。

除数与被除数的最大公因数等于除数与余数的最大公因数

在中如果有等式

成立，那么是与的最大公因数当且仅当是与的最大公因数。

辗转相除法:求两整数最大公因数的统一方法

任给两个整数，都存在它们的一个最大公因数，并且可以表示成与的倍数和，即存在整数，使得

互素

• 设，如果，那么称与互素。
• 两个整数互素当且仅当它们的公因数只有。

定理：两整数互素的充要条件

两整数互素的充要条件是：存在整数，使得

证明

• 必要性：由辗转相除法定理即可得到，下证充分性。
• 充分性：设成立，只需证明整数互素，即证明。任取的一个公因数，则有，由定理：除数整除被除数的倍数和，可以得到：，所以，证毕。

互素整数的重要性质及推广

1. 在中，如果，且，那么。

   证明：

   若，显然成立；若，利用整数互素的充要条件得到：存在整数，使得，两边同乘以得到：，而显然有，根据命题：除数整除被除数倍数和，得到.

性质1的简单应用

对于素数, 有

证明:

对组合数显然有, 而显然,, 所以由性质1, 可得.

1. 在中，如果，且，那么。

   证明：

   根据，有整数使得。由于，因此。又由于，因此由性质1得到，从而有整数使得，所以有，即得到。

   推广：

   在中，如果，且两两互素，那么.

2. 在中，如果，且，那么。

   证明：

   根据，得到：有整数，使得

   将上述两式左右两边分别相乘，得到

   于是由整数互素的充要条件得到：.

   推广：

   在中，如果，那么。

素数的重要性质

设是大于的整数，则下列命题等价：

1. 是素数；
2. 对任意整数，都有或者；
3. 对整数，从可以推出：或者；
4. 不能分解成两个比小的正整数的乘积。

证明

• 1->2：由于是素数，所以有或者，而后者可得出.
• 2->3：由于，假设，则由性质2，有，再由整数互素的性质1，得到。
• 3->4：假设，则由整除的反身性得到，由性质3得到：或者，矛盾。
• 4->1：任取的一个正因数，则存在正整数，使得，根据性质4，或者，当时，，因此的正因数只有，从而为素数。

算术基本定理