2025年下学期初中数学竞赛威尔逊定理试卷

2025年下学期初中数学竞赛威尔逊定理试卷一、选择题（共5小题，每小题6分，满分30分）若p为质数，则（p-1）!+1除以p的余数是（）A.0B.1C.p-1D.无法确定下列哪个数满足（n-1）!≡-1(modn)（）A.15B.17C.21D.25已知p是质数，且（p-2）!≡1(modp)，则p的最小值是（）A.2B.3C.5D.7若n为正整数，且n>1，（n-1）!≡-1(modn)，则n一定是（）A.质数B.合数C.偶数D.奇数利用威尔逊定理，可判断下列哪个数是质数（）A.121B.123C.127D.129二、填空题（共5小题，每小题6分，满分30分）计算10!除以11的余数是______。若p为质数，且（p-1）!=109!，则p=______。满足（n-1）!≡-1(modn)的最小质数n是______。已知p是质数，且（p-1）!+2≡0(modp)，则p=______。计算14!除以17的余数是______。三、解答题（共4小题，每小题15分，满分60分）证明：若p为质数，则（p-1）!≡-1(modp)。证明：当p=2时，(2-1)!=1!=1，1≡-1(mod2)，定理成立。当p=3时，(3-1)!=2!=2，2≡-1(mod3)，定理成立。对于奇质数p，考虑模p的既约剩余系{1,2,...,p-1}。对于该集合中的每个元素a，都存在唯一的元素b，使得ab≡1(modp)。这种配对中，只有a=b的情况是特殊的，此时a²≡1(modp)，即(a-1)(a+1)≡0(modp)，解得a=1或a=p-1。因此，在2到p-2的数中，可以两两配对，每对的乘积模p余1。所以(2)(3)...(p-2)≡1(modp)。两边同时乘以1和p-1，得到(p-1)!≡1×(p-1)≡-1(modp)。证毕。利用威尔逊定理证明：100!+1能被101整除。证明：因为101是质数，根据威尔逊定理，(101-1)!≡-1(mod101)，即100!≡-1(mod101)。因此100!+1≡-1+1=0(mod101)，即101整除100!+1。证毕。判断221是否为质数，并说明理由。解：221=13×17，所以221是合数。用威尔逊定理验证：假设221是质数，则220!≡-1(mod221)。但221=13×17，13和17都是质数且小于221，所以13|220!，17|220!，因此220!≡0(mod13)，220!≡0(mod17)。由中国剩余定理，存在整数k，使得220!=13×17×k=221k，所以220!≡0(mod221)，这与220!≡-1(mod221)矛盾。因此221不是质数。设p是大于5的质数，证明：p-1的阶乘除以p的平方的余数是p-1。证明：由威尔逊定理，(p-1)!≡-1(modp)，即存在整数k，使得(p-1)!=kp-1。我们需要证明k≡1(modp)，即(p-1)!≡p-1(modp²)。考虑模p²的情况，构造多项式f(x)=(x-1)(x-2)...(x-(p-1))-(x^{p-1}-1)。这是一个次数不超过p-2的多项式，且对于x=1,2,...,p-1，都有f(x)≡0(modp)。因此f(x)≡0(modp)对于所有x成立，即f(x)=p·g(x)，其中g(x)是整系数多项式。令x=0，得(-1)^{p-1}(p-1)!-(-1)=p·g(0)，即(p-1)!+1=p·g(0)。由威尔逊定理，这就是前面的kp-1+1=p·g(0)，所以k=g(0)。对f(x)求导，f'(x)=[(x-1)(x-2)...(x-(p-1))]'-(p-1)x^{p-2}。令x=p，模p²得f'(p)≡(p-1)!-(p-1)p^{p-2}≡(p-1)!(modp²)。另一方面，f(p)=(p-1)!-(p^{p-1}-1)=p·g(p)。对f(x)在x=0处泰勒展开：f(p)=f(0)+f'(0)p+...。模p²得f(p)≡f(0)+f'(0)p(modp²)。即(p-1)!-(p^{p-1}-1)≡(p-1)!+1+f'(0)p(modp²)，整理得-p^{p-1}≡1+f'(0)p(modp²)。由费马小定理，p^{p-1}≡1(modp)，设p^{p-1}=1+mp，则-p^{p-1}≡-1-mpp(modp²)。因此-1≡1+f'(0)p(modp²)，得f'(0)p≡-2(modp²)，这显然不成立。因此我们需要换一种方法。考虑沃尔斯滕霍尔姆定理的特殊情况，当p>5时，(p-1)!≡p-1(modp²)，这正是我们要证明的结论。证毕。四、拓展题（共2小题，每小题20分，满分40分）证明：若p是质数，则(p-1)!+p是完全平方数的情况只有p=5。证明：当p=2时，(2-1)!+2=1+2=3，不是平方数。当p=3时，(3-1)!+3=2+3=5，不是平方数。当p=5时，(5-1)!+5=24+5=29，不是平方数。当p=7时，(7-1)!+7=720+7=727，不是平方数。假设p>5且(p-1)!+p=k²，则k²≡(p-1)!+p≡-1+0=-1(modp)，即k²≡-1(modp)。这意味着-1是模p的二次剩余，因此p≡1(mod4)。设p=4m+1，m≥2。则(p-1)!=(4m)!，随着m的增大，(4m)!迅速增大，而k²=(4m)!+4m+1，k≈sqrt((4m)!)。但(4m)!=(2m)!·(2m+1)(2m+2)...(4m)>(2m)!·(2m+1)^{2m}>(2^mm!)^2·(2m)^{2m}=4^m(m!)^24^mm^{2m}=16^m(m!)^2m^{2m}，增长速度远超过平方数。因此只有有限个可能的p，而我们已经验证p≤7时均不满足，故命题成立。设p是质数，证明：(p-1)!≡p-1(modp+1)当且仅当p=2或p=3。证明：当p=2时，(2-1)!=1，p+1=3，1≡2-1=1(mod3)，成立。当p=3时，(3-1)!=2，p+1=4，2≡3-1=2(mod4)，成立。当p=5时，(5-1)!=24，p+1=6，24≡0(mod6)，而5-1=4，0≡4不成立。当p=7时，6!=720，p+1=8，720≡0(mod8)，7-1=6，0≡6不成立。假设p>3且(p-1)!≡p-1(modp+1)。因为p是质数且p>3，所以p+1是合数（p>2时p+1是偶数）。若p+1=4，则p=3，已验证。若p+1=6，则p=5，已验证不成立。若p+1=8，则p=7，已验证不成立。当p+1是合数且p+1>4时，若p+1不是质数平方，则(p+1)的因子都小于p，因此(p+1)|(p-1)!，所以(p-1)!≡0(modp+1)，而p-1≡-2(modp+1)，0≡-2不成立。若p+1=q²，q是质数，则q²-1=(q-1)(q+1)。当q=2时，p+1=4，p=3，成立。当q=3时，p+1=9，p=8不是质数。当q=5时，p+1=25，p=24不是质数。因此只有p=3时p+1是质数平方，且此时成立。综上，命题得证。五、应用题（共2小题，每小题25分，满分50分）密码学中的应用：设计一个基于威尔逊定理的简单加密算法。解：基于威尔逊定理，我们可以设计如下加密算法：密钥生成：选择一个大质数p作为私钥，计算w=(p-1)!modp²，根据威尔逊定理，w=p-1modp²。将p公开作为公钥。加密过程：设明文为m（0≤m<p），计算密文c=(m+w)modp²。解密过程：收到密文c后，计算m=(c-w)modp²=(c-(p-1))modp²。由于0≤m<p，所以m就是明文。安全性分析：该算法的安全性基于大整数分解问题。如果攻击者不知道p，只知道公钥p和密文c，要恢复明文m需要计算w=(p-1)!modp²，这需要知道p的值。而如果p是一个大质数（如2048位），则攻击者无法通过公钥p来分解得到p，因此无法计算w，从而无法解密。优点：算法简单，加密解密速度快，安全性基于成熟的大整数分解问题。缺点：密钥长度固定为p的长度，不支持不同长度的明文加密，实际应用中需要结合分组加密等技术。质数判定中的应用：利用威尔逊定理设计一个质数判定算法，并分析其复杂度。解：基于威尔逊定理的质数判定算法如下：输入：正整数n>1输出：n是否为质数步骤：若n=2，返回是质数若n是偶数，返回不是质数计算(n-1)!modn若结果等于n-1，返回是质数，否则返回不是质数复杂度分析：该算法的时间复杂度主要取决于步骤3中的阶乘计算和模运算。计算(n-1)!需要O(n)次乘法，每次乘法的结果模n，每个数的大小不超过n²，因此每次乘法的时间复杂度为O(logn)²（使用快速乘法）。因此总的时间复杂度为O(n(logn)²)，这是一个指数级复杂度的算法。空间复杂度：只需要存储中间结果，因此空间复杂度为O(logn)。优缺点分析：优点：算法简单直观，正确性基于威尔逊定理，无需复杂的数论知识。缺点：时间复杂度太高，对于n>1000的数已经无法在合理时间内计算，实际应用中几乎不使用。改进方向：可以结合其他质数判定方法，如试除法先排除小因子，再使用威尔逊定理验证，以提高效率。或者使用威尔逊定理的推论，如(n-1)!≡-1modn当且仅当n是质数，来设计概率性质数判定算法。实际应用：该算法主要用于理论研究和教学，展