关于威尔逊定理的详细证明
威尔逊（Wilson）定理：设p为质数，则(p?1)!??1(modp)。 1. 数论倒数：若ab?1(modm),则a与b是关于模m的数论倒数
2. 若(a,m)?1,则a关于模m必有数论倒数。这由欧拉定理或裴蜀定理可保证
3. 质数p的一个缩系为：1,2,3,?,p?2,p?1. 则：1?1(modm),p?1??1(modm) 4. 主要证明：?x?A??2,3,?,p?2?,存在唯一的y?A,且y?x,使得xy?1(modp) 5. 因为(x,p)?1,?由：2.知存在z,xz?1(modp),可以证明: (z,p)?1所以在模p的缩
系中，必存在y??1,2,3,?,p?1?，使得z?y(modp)，所以xy?1(modp) 6. 若y?1,则x?1(modp),矛盾，同理y?p?1。所以，y?A 7. 若x?y,则x?1(modp),x?1,p?1(modp)，矛盾，所以x?y
8. 现在证明y的唯一性：设又有y1,使得xy1?1(modp)，则xy?xy1(modp)，易知：
2y?y1(modp)，由?(p?2)?y?y1?p?2知y?y1，唯一性得到证明。于是有
9. ?x?A??2,3,?,p?2?,存在唯一的y?A,且y?x,使得xy?1(modp)，即集合A中的数两两配对，成为数论倒数，乘积为1
(p?1)!?1?[2?3??(p?2)]?(p?1)??1(modp) 证毕
1
第一章 初等数论
第一节 数的整除性
1.1 整除
典例分析
例1．证明：10?01被1001整除。 ???2000个0证明：10?01=10???2000个02001?1?(103)667?1,1001?103?1，103??1(mod1001)，故
(103)667??1(mod1001)，故结论成立
例2．对正整数n，记S(n)为n的十进制表示中数码之和。证明： 9|n的充要条件是9|S(n)。
m?1???a1?101?a0，而10k?1(mo9d)，对证明：n?am?1am?2?a1a0?am?1?10n模9即可证明
例3．设k?1是一个奇数，证明：对于任意正整数n，数1k?2k???nk不能被n?2整除。 提示：倒叙相加求和
例4．设m,n是正整数，m?2，证明：（2?1）（2?1）。
证明：设n?mq?r,0?r?m，2?1(mod(2?1)),?2?1?2?1(mod(2?1)) 又2?1>2?1,(以下略)
例5．设正整数a,b,c,d满足ab?cd，证明：a?b?c?d不是质（素）数。
例6．求出有序整数对（m,n）的个数，其中1?m?99，1?n?99，(m?n)?3m?n是完全平方数。
提示：两个相邻的完全平方数之间没有完全平方数
例7．证明：若正整数a,b满足2a?a?3b?b，则a?b和2a?2b?1都是完全平方数。
证明: a?b?2(a?b)?b?b?(a?b)[1?2a?2b],
同理：a?(a?b)(1?3a?3b)，ab?(a?b)(1?2a?2b)(1?3a?3b) ，
222222222mmnrmmnmr221?2a?2b与1?3a?3b均为完全平方数 又(1?2a?2b,1?3a?3b)?1，所以例8．证明不存在正整数n，使2n2+1，3n2+1，6n2+1都是完全平方数。
提示：此题是否定语气的命题，可用反证法，假设存在n，使他们都是完全平方数，则乘积也是完全平方数，若介于两个相邻的完全平方数之间，则矛盾
2
练习题
1．证明：如果p和p?2都是大于3的素数，则6是p?1的因子。 提示：对p选个模分类讨论 2．设m?n?0，证明：(2证明：2立证
3．已知n为正奇数，求证：60|6?3?2?1。
提示：因为涉及幂次，建议利用数论的有力工具：同余
5. 已知x、y、z是三个大于1的正整数，且xyz整除(xy-1)(yz-1)(zx-1)，求x、y、z的所有 可能的值。（13华约） 提示：限定范围，合理筛选。设x?y?z，则 xyz?xy?yz?zx?1?3xy,z?3（略） 1.2 质数与合数
nnn2nn2n?1)|(2m2m?1)；
nm?n??1(mod(22?1)), 又22?(22)2，(2)2n2m?n?(?1)2m?n(mod(22?1)),
n典例分析
1的正整数，证明：数n?n?1不是质数 例1 设n为大于提示：因式分解
例2 考察下面的数列：101，10101,1010101，?。问：该数列中有多少个质数？ 证明：利用因式分解公式 x?y?(x?y)(x2222nnnn?154?xn?2y???xyn?2?yn?1)
(10n?1?1)(10n?1?1)可得：1?10?(10)???(10)=，9与每个括号内的数都不
9能约为1，是合数（除非n=1），只有一个质数101
例3 求所有的正整数n，使得
n(n?1)?1是一个质数 2提示：分类则明了
例4 对任意正整数n，证明：存在n个连续正整数，他们都是合数 （提示：n!?n?(n?1)??3?2?1）研究：(n?1)!?k
例5 设n为大于2的正整数，证明：存在一个质数，满足：n?p?n! 提示：设小于n的质数只有有限个
3
练习题
1的正整数，证明：n?4是一个合数 1 设n为大于证明: n为偶数显然，n?2k?1时，n?4?n?(22 求使得4x?12x?27为质数的所有整数x 提示：因式分解法x??1,?2,4,5
3 能否将1,2,3，?，50两两配对，使得所配的25对数之和两两不同，且都是质数？
证明：假若成立，则在1到99有25个不同的质数，事实上，从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共25个质数，但前面无2，故不成立
4 是否存在3个不同的质数p,q,r,使得下面的整除关系都成立？
22 qrp?d, rpq?d, pqr?d 其中(1)d?10; (2)d?11
224n4n42k?12) 配方法
证明：由对称性，不妨设：1?p?q?r,则：p?1?q,q?1?r，三数中q,r较大，
可构造同向不等式：p?d?qr?(p?1)(p?2),3p?2?d。d?10时，无有，
2d?11时，三数 2,3,5
点评：限定范围，合理筛选
5 设p为正整数，且2?1是质数，求证：p为质数 提示：反证法
6 正整数m,n,k满足：mn,nk.证明：mk
证明：由已知：(m)(n),(n)(k)，由整除的传递性既得 7 设a,b,c,d都是整数，且a?c,a?cab?cd,证明：a?cad?bc 提示：被除式作差即可
8 设a,b,c,d都是质数，且a?3b?6c?12d, a?b?c?d?1749 求a?b?c?d的所有可能值
证明：因为有四个质数，可先考虑质数的分类：奇质数，偶质数1749是奇数，故d?2
22222222nkmkkmnmnmknkmpa2?b2?c2?1753，c?2d,c?5，基于“限定范围”的想法，将a2?b2?c2缩小 1753?(3b?1)2?b2?c2?8b2?6b?1?c2?8(2c?1)2?6(2c?1)?1?c2
得：33c?44c?1738，c?7，故c?5，a?b?1728?2?3（1），又a,b有相同
22263 4
相关推荐：
loading