选修4-6 初等数论初步《第一讲 整数的整除 一 整除 3.素数及其判别法》优秀教案

选修4-6 初等数论初步《第一讲 整数的整除 一 整除 3.素数及其判别法》优秀教案

(二）1.定义2：如果一个正整数 有一个因数 ，而 又是素数，则 就叫做 的素因数.

2.如果 是一个大于1的正整数，则它大于1的最小正因数 是一个素数，于是，任何大于1的正整数总存在一个素因数.

证明：假设 不是素数，因为 ，那么 必然有一个除1， 以外的因数 ，使得 .因为 ，所以 ， 于是 是的除1， 以外且小于 的正因数，这与已知矛盾.

(三）整数的分解：1.任意的大于1正整数正整数 ，如果不是素数，则总可以分解成一些素数的乘积.

证明：如果 不是素数，则由上面的结论可知 可以分解成一个素因数和一个正整数 的乘积， ，如果 是素数，则过程停止.否则， 又可以分解成一个素因数和一个正整数 的乘积， ，如果 是素数，则过程停止.否则可以继续分解下去，而此过程必在有限步后停止，最后将 分解为一些素数的乘积.

2.素数的个数有无穷多个.

证明：假设素数有有限个，设为 ,共 个，令 ，那么每个素数都不能整除 ,而 是大于1的正整数，所以它一定能被某个素数整除，矛盾.因此素数的个数是无穷的.

（四）素数的判别法：1.如果 是一个合数，则 必有一个不超过 的素因数.

证明：因为 是一个合数,所以 存在两个大于1的两个因数 ，使得 ，设 是 的最小素因数，则 ，于是 ，所以 .故得所证.

2.如果 是一个大于1的整数，而所有不超过 的素因数都除不尽 ,则 是素数.

证明：否则，由上面的结论， 有一个不超过 的素数因数，与条件矛盾.

3.埃拉托斯特尼筛法

例3 找出1~100中的全部素数.

解：只需把1与1到100之间的合数划去即可.对于1到100之间的每个合数 ，它一定能被某个不超过 的素数整除，从而能被不超过 的素数整除.不超过10的素数为2,3,5,7.在1到100中首先划去1，然后留下2,3,5,7，并分别划去2,3,5,7除自身以外的所有倍数，留下的数就是不超过100的全部素数.最后得到不超过100的全部素数为：2,3,5,7，,11,

13，17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97，共25个.

练习：1判断343,2027,7679是素数还是合数.

二．最大公约数和最小公倍数

（一）定义：1.设 是两个不全为0的整数.若整数 满足： 则称 为 的公约数（公因数）， 的公约数中的最大者称为 的最大公约数，记为 .如果 ，则称 互质或互素. 类似的可以定义三个或更多个整数的最大公因数和互素的概念，将整数 的最大公因数记做 ,依次类推.

2．如果 同时是 的倍数，则称 是 的公倍数. 的公倍数中最小的正整数称为 的最小公倍数，记为 .类似的可以定义三个或更多个整数的最小公倍数概念，将整数 的最小公倍数记做 . 3.最大公约数的求法：（1）短除法；（2）辗转相除法.

（二）辗转相除法 1.设 是三个不全为0的整数，且有整数 使得 ，则

，即 .由此得到求最大公约数的一种方法——辗转相除法.

设 ，且 ，则由带余除法有：

； ；┉┉； ；

，则

例4 求3960和756的最大公约数.