初等数论：素数（质数）与合数

陈一男学习网站[ ChenYinan.com ] - 中国数学学会 - 中国院士 - GeoGebra - 数学基础

一、素数（质数）

一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数。

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。

素数的因数性质：素数只有两个因数，即1和它本身。

例如，17是一个素数，它的因数只有1和17。这是素数最基本的性质，也是素数定义的核心内容。

从整除的角度来看，设\(p\)是素数，对于任意整数\(a\)，如果\(p\mid a\)（\(p\)整除\(a\)），那么\(a = kp\)，其中\(k\)是整数，并且除了\(k = 1\)和\(k=a/p\)这两种情况外，不存在其他整数\(k\)使得等式成立。

素数的分布性质：素数在自然数中的分布是不规则的。随着数字的增大，素数出现的频率会逐渐降低。

例如，在1 - 10之间有4个素数（2、3、5、7），而在101 - 110之间只有2个素数（101、103、107、109四个中的两个）。

素数有无穷多个。可以通过反证法来证明，假设素数是有限个，设为\(p_1,p_2,\cdots,p_n\)，考虑数\(N = p_1p_2\cdots p_n+ 1\)。如果\(N\)是素数，那么它不在\(p_1,p_2,\cdots,p_n\)之中，与假设素数有限矛盾；如果\(N\)是合数，那么它一定有一个素因数\(p\)，\(p\)不能是\(p_1,p_2,\cdots,p_n\)中的任何一个，因为如果\(p = p_i\)（\(i = 1,2,\cdots,n\)），那么\(p_i\mid(N - p_1p_2\cdots p_n)=1\)，这是不可能的，所以素数有无穷多个。

算术基本定理：任何一个大于1的自然数\(n\)，如果\(n\)为合数，则\(n\)可以分解成素数的乘积，而且这种分解是唯一的（不考虑因数的排列顺序）。

例如，\(12 = 2\times2\times3\)，这种分解方式是唯一的（除了写成\(3\times2\times2\)等顺序不同的形式）。

素数是构成自然数的“基本积木”。每一个合数都可以由素数相乘得到，就像每一个复杂的建筑都可以用基本的建筑材料搭建一样。

同余性质：设\(p\)是素数，对于任意整数\(a\)和\(b\)，如果\(a\times b\equiv0(\bmod p)\)，那么\(a\equiv0(\bmod p)\)或者\(b\equiv0(\bmod p)\)。

例如，设\(p = 5\)，如果\(a\times b\equiv0(\bmod 5)\)，那么要么\(a\)是5的倍数，要么\(b\)是5的倍数。这一性质在数论的同余方程等问题中有广泛应用。

两个连续的自然数中，必定有一个是素数或者合数。

例如，2和3，2是素数，3也是素数；4和5，4是合数，5是素数。

除了2以外，所有的素数都是奇数。因为偶数都能被2整除，所以大于2的偶数不符合素数的定义。例如，3、5、7、11等都是奇数且为素数。

二、合数

定义：自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。例如，4、6、8、9、10等都是合数。

合数的性质：

合数至少有三个因数。以4为例，4的因数有1、2、4，一共有三个因数。

合数可以分解成两个或两个以上素数的乘积。例如，6 = 2×3，其中2和3是素数；8 = 2×2×2，这里的2是素数。

素数与合数的区别

因数个数不同：素数只有两个因数，而合数至少有三个因数。这是区分素数与合数的最主要特征。例如，3是素数，因数为1和3；而6是合数，因数为1、2、3和6。

能否分解：素数不能分解成除了1和它本身之外的两个自然数的乘积，而合数可以。如5是素数，不能写成其他两个自然数（1和5除外）的乘积形式；9是合数，可以写成3×3。

1既不是素数也不是合数

因为素数要求有两个不同的因数（1和它本身），而1只有一个因数1；合数要求至少有三个因数，1也不满足合数的条件。

题1：在小于100的自然数中，与2、3都互质且是合数的数有多少个？

答案：首先，2和3互质，它们的最小公倍数是\(2\times3 = 6\)。与2、3都互质的数不能是2或3的倍数。

合数是指除了能被1和本身整除外，还能被其他数（0除外）整除的自然数。

1到100以内6的倍数有\([\frac{100}{6}] = 16\)个（\([x]\)表示取整）。

1到100以内的合数有74个（可通过排除1和质数得到）。

1到100以内是合数但不是6的倍数的数有\(74-16 = 58\)个。

解题思路：先求出2和3的最小公倍数，确定与它们互质的数的特征。然后分别找出1到100以内6的倍数的个数和合数的个数，通过减法得到满足条件的数的个数。

题2：已知\(p\)、\(q\)是质数，且\(p + q = 2001\)，求\(p\times q\)的值。

答案：因为\(2001\)是奇数，两个数相加为奇数，必有一个是偶数，一个是奇数。而既是质数又是偶数的数只有2，所以不妨设\(p = 2\)，则\(q = 2001 - 2 = 1999\)。\(p\times q=2\times1999 = 3998\)。

解题思路：根据奇数和偶数的性质，由于和为奇数，确定其中一个质数为2，进而求出另一个质数，最后计算它们的乘积。

题3：有一个质数，它加上6是质数，减去6也是质数，这个质数是多少？

答案：设这个质数为\(x\)。

从最小的质数开始尝试，2不符合条件，因为\(2+6 = 8\)不是质数。

当\(x = 7\)时，\(7 + 6 = 13\)是质数，\(7-6 = 1\)不是质数。

当\(x = 11\)时，\(11+6 = 17\)是质数，\(11 - 6 = 5\)是质数。

所以这个质数是11。

解题思路：采用列举法，从最小的质数开始逐一尝试，根据题目条件判断是否符合要求，最终找到满足条件的质数。

题4：把33拆分成若干个不同质数之和，如果要使这些质数的乘积最大，问这几个质数分别是多少？

答案：首先列出小于33的质数：2、3、5、7、11、13、17、19、23、29、31。

因为\(2 + 3+5+7 + 11+13=41>33\)，所以最多用5个不同的质数。

33可以拆分为\(2 + 31\)，\(2\times31 = 62\)；

也可以拆分为\(3+7+23\)，\(3\times7\times23 = 483\)；

还可以拆分为\(5+7+21\)（21不是质数，舍去）；

或\(5 + 11+17\)，\(5\times11\times17 = 935\)；

或\(7+11+15\)（15不是质数，舍去）等组合。

通过比较可知，拆分为\(2\)、\(7\)、\(11\)、\(13\)时乘积最大（\(2\times7\times11\times13 = 2002\)）。

解题思路：先列出小于给定数的质数，然后根据和的限制条件，尝试不同的质数组合。计算每种组合的乘积，比较得出乘积最大的组合。

题5：两个质数的和是40，求这两个质数的乘积的最大值。

答案：因为\(40\)是偶数，两个质数相加为偶数，这两个质数必然同为奇数或同为偶数，而既是质数又是偶数的只有2。

设其中一个质数为\(x\)，另一个为\(40 - x\)。

当\(x = 2\)时，另一个数为\(38\)（不是质数，舍去）。

从奇数质数开始尝试，当\(x = 3\)时，另一个数为\(37\)，乘积为\(3\times37 = 111\)；

当\(x = 5\)时，另一个数为\(35\)（不是质数，舍去）；

当\(x = 7\)时，另一个数为\(33\)（不是质数，舍去）；

当\(x = 11\)时，另一个数为\(29\)，乘积为\(11\times29 = 319\)；

当\(x = 13\)时，另一个数为\(27\)（不是质数，舍去）；

当\(x = 17\)时，另一个数为\(23\)，乘积为\(17\times23 = 391\)；

当\(x = 19\)时，另一个数为\(21\)（不是质数，舍去）。

通过比较可知，乘积的最大值为\(391\)。

解题思路：根据和为偶数的性质，先排除不符合条件的情况。然后通过列举法，从可能的质数开始逐一尝试，计算乘积并比较大小，得出最大值。

题6：如果一个质数加上2，8，14，26以后，得到的和都是质数。那么，原来的质数是多少？

答案：设这个质数为\(x\)。

一个数除以3的余数有0、1、2三种情况。

当\(x\div3\)余0时，\(x\)只能是3，此时\(3+2 = 5\)，\(3+8 = 11\)，\(3 + 14 = 17\)，\(3+26 = 29\)，都为质数，符合条件。

当\(x\div3\)余1时，\(x + 2\div3\)余0，\(x + 2\)能被3整除，不是质数（不符合）。

当\(x\div3\)余2时，\(x+8\div3\)余0，\(x + 8\)能被3整除，不是质数（不符合）。

所以原来的质数是3。

解题思路：考虑数除以3的余数情况，通过分类讨论，判断在不同余数情况下是否满足得到的和都是质数的条件，从而确定原来的质数。

题7：有三个质数\(x\)、\(y\)、\(z\)，满足\(x + y = z\)，且\(x\lt y\)，\(x = 2\)，求\(y\)和\(z\)的值。

答案：因为\(x = 2\)，且\(x + y = z\)，所以\(2+y = z\)。

质数中除了2是偶数，其余都是奇数。

两个奇数相加为偶数，一个偶数和一个奇数相加为奇数。

因为\(z\)是质数，所以\(y\)必须是奇数，\(z\)是奇数。

从最小的奇数质数3开始尝试，当\(y = 3\)时，\(z = 2 + 3 = 5\)。

经检验，\(2\)、\(3\)、\(5\)满足条件。

解题思路：根据已知条件\(x = 2\)和\(x + y = z\)，结合质数中偶数只有2的特点，通过列举奇数质数来尝试找到满足条件的\(y\)和\(z\)的值。

题8：一个两位质数，将它的十位数字与个位数字对调后仍是一个质数，我们称它为“无暇质数”，求所有“无暇质数”的和。

答案：两位数的质数有11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。

经过对调后仍是质数的有11、13和31、17和71、37和73、79和97。

它们的和为\((11)+(13 + 31)+(17+71)+(37 + 73)+(79+97)\)

\(=11 + 44+88 + 110+176\)

\(=429\)

解题思路：先列出所有的两位质数，然后逐一检查对调后的数是否仍是质数，最后将符合条件的“无暇质数”相加求和。

题9：\(p\)是质数，\(p^{2}+2\)也是质数，求\(p^{3}+2\)的值。

答案：如果\(p = 2\)，则\(p^{2}+2 = 2^{2}+2 = 6\)（不是质数，不符合）。

因为除了2以外的质数都是奇数，设\(p\)是奇数（\(p\neq2\)），那么\(p^{2}\)也是奇数，\(p^{2}+2\)是奇数。

对于奇数\(p\)，\(p^{2}\equiv1(\bmod3)\)（因为奇数的平方除以3余数为1），所以\(p^{2}+2\equiv0(\bmod3)\)，即\(p^{2}+2\)能被3整除，不是质数（不符合）。

所以只有\(p = 3\)时满足条件，此时\(p^{3}+2 = 3^{3}+2 = 29\)。

解题思路：先考虑特殊值\(p = 2\)是否符合条件，然后对于奇数\(p\)，利用数的同余性质分析\(p^{2}+2\)的情况，排除不符合的情况，最后确定\(p\)的值，进而求出\(p^{3}+2\)的值。

题10：已知\(a\)、\(b\)、\(c\)是三个不同的质数，且满足\(a\times b^{c}\times a = 2002\)，求\(a + b + c\)的值。

答案：将\(2002\)分解质因数，\(2002 = 2\times7\times11\times13\)。

因为\(a\times b^{c}\times a = a^{2}\times b^{c}=2002\)，通过尝试不同的组合，发现\(a = 2\)，\(b = 7\)，\(c = 11\)满足条件。

所以\(a + b + c = 2+7 + 11 = 20\)。

解题思路：先分解\(2002\)的质因数，然后根据等式\(a^{2}\times b^{c}=2002\)的形式，通过尝试不同质因数的组合，找到满足条件的\(a\)、\(b\)、\(c\)的值，最后计算它们的和。

数学基础 : 小学数学、初中数学、高中数学、高等数学