能否指定素数的余数?
证明素数有无穷多个时,我们可假设有一份有限清单,再构造一个不被清单上任何素数整除的数。更细致的问题是:除以四有指定余数的素数,是否也有无穷多个?这里证明余数为三的情形。
论证只用整除、素因数分解和模四余数;它是这些方法的应用,并非证明每个等差数列都含有无穷多个素数。
定义
(模四同余)
对整数 ,若 整除 ,记作 。每个整数都恰与 之一模四同余,这个数就是它的余数。同余式可以相乘:若 且 ,则 ,因为 。
奇数除以四的余数是一或三。下面的引理提供构造所需的素因数。
引理
(大于一的整数必有素因数)
若整数 ,则必有某个素数整除 。
证明
(大于一的最小因数是素数)
的大于一的因数组成的集合非空,因为 属于其中,所以有最小元 。若 不是素数,可写 ,其中 。于是 整除 ,从而整除 ,且 ,与 的最小性矛盾。所以 是 的素因数。
把引理反复用于余下的因子,可知每个 都是素数的乘积,重复的因数也计算在内。
为什么余三能保证所需的素因数?
定理
(余三的奇数有余三的素因数)
若 且 ,则 至少有一个素因数 满足 。
证明
(余一因数的乘积仍余一)
由 知 是奇数,所以其素因数都不是 2。每个素因数都是奇数,模四余一或余三。把 分解为素数的乘积,重复因数也计算在内。若所有素因数都模四余一,逐个因数把同余式相乘,可知它们的乘积也模四余一。这个乘积就是 ,与 矛盾,因为 不整除 。因此至少一个素因数余三。
证明透视
余数定理的每个假设用在哪里
这个论证其实是逆否命题:素因数全都模四余一的数,本身也模四余一,所以模四余三的数不可能只有这样的因数。有三个假设承担了分量。第一, 已迫使 为奇数,排除了素数 2;2 是唯一余数既非一也非三的素数,若不排除,二分的情形就会多出第三个余数类。第二,同余式可相乘是推动论证的机制:它把因数的性质传给乘积,并要求分解是有限的,这就是要计算重复因数的原因。第三, 保证存在至少含一个素数的分解;整数 模四余三,却没有素因数。
结论只是存在性的:证明说明了并非所有因数都余一,对其余因数则没有任何说明。
常见错误
(余三的数,其素因数未必全都余三)
定理没有说 的每个素因数都余三。例如 ,但素因数 13 模四余一;它也没有说余三的数本身必为素数:39 就是合数。能保留下来的只是较弱的结论:至少有一个素因数余三。
排除每一份有限清单
定理
(模四余三的素数有无穷多个)
满足 的素数 有无穷多个。
证明
(同时保留所需余数并排除清单上的因数)
反设这种素数只有有限多个,全部列为 。清单非空,因为 3 已是其中一个。令
此时 且 。根据上一个定理, 有素因数 。对每个清单上的 ,由于 ,
因此 不整除 ,特别地 不等于任何已列素数。但 是模四余三的素数,与清单已列尽所有此类素数矛盾。所以任何有限清单都不可能列尽它们。
的两个作用不同,缺一不可: 保证有一个所需种类的素因数; 排除每个已列素数。证明没有预先算出 ,也没有假设 是素数。
证明透视
为什么构造中的因数四和符号都不能少
这个证明的形状和证明素数有无穷多个的常见论证相似,却不能照搬。那个论证中的数 模四的余数不受控制,而上面的余数定理只在 时才有用。因数 4 解决了这一点:无论 是什么, 都是四的倍数,所以 。在样本 中,,所以光用 本身得不到余数三。
减一的负号还有第二个作用:它使 模每个已列素数都余 ,这是非零余数,因此没有已列素数整除 。使矛盾成立的一步是两者的结合:素数 由余数定理保证存在,又因为每个已列素数都使 余 ,所以 不在清单上。单靠其中一个都不够。
例题
(构造出的数可以是合数)
以样本素数 构造
其中 、;71 是不在样本清单上的素数。因为 ,只需检查可能的素因数 ,便知 71 是素数。虽然 923 是合数,它仍有新的所需素因数 71。
有限样本不等于假设这些就是所有此类素数。一般反证法假设有一份完整的有限清单,再对那份假设清单使用构造。
例题
(找出余三的素因数)
取 。由 知 。分解得 ,三个素因数模四的余数依次为 。余数之积 ,与定理相符,而 就是定理所说的那个素因数。这里三个素因数中只有一个余三。
最小的情形是 :它本身是素数,所以 ,无需再找别的素因数。
例题
(构造出的数本身是素数)
取样本清单 ,则 ,。因为 ,只需试 :83 是奇数,数字和 不是 3 的倍数,个位不是 0 或 5,而 。所以 83 是素数。又 ,且 83 不在清单 上。
这时新的素数就是 本身,定理中的素因数 就是 。这一情形与合数的情形 由同一个证明处理;证明从不判断究竟属于哪一种。
反例模式
改变符号会失去余数保证
命题:把 改为 ,同一论证仍能得到不在清单上、模四余三的素数。用样本清单 检验,此时 ,。两个素因数都模四余一(,),而且 。两者都不余三,所以命题不成立:这个数得不到所需种类的素数,无论在不在清单上。
这不与定理矛盾。85 模四余一,不在余数定理的假设之内。补救办法是回到原来的构造:同一清单下, 是素数,且余三。
常见错误
(假设构造出的数是素数)
很容易写出“ 是不在清单上、模四余三的素数”。 的例子说明这一般不成立。证明只需要 有一个余数合适的素因数,这由余数定理提供,无需把它算出来。
练习与解答
快速检查
(样本清单只有 3 时,计算 ,找一个新的模四余三素数。)
取 。
解答 · 答案
,故 。11 是素数,模四余三,且不等于 3。
快速检查
(为什么任何清单上的 都不能整除 ?)
把 与 比较。
解答 · 答案
整除 ;若也整除 ,便整除两者之差 ,不可能。等价地,构造出的数模 余 。
快速检查
( 是否表示每个素因数都余三?)
试一个较小的合数。
解答 · 答案
否。 模四余三,但 13 模四余一;至少一个所需素因数已足够。
快速检查
(为什么此证明不能直接改用 ?)
计算它模四的余数。
解答 · 答案
它模四余一,所有素因数可以都余一。取 得 ,两个因数均非模四余三。
有效的反证构造要同时具备两点:产生所需种类的对象,并排除假设清单上的每个对象。