2025年下學(xué)期初中數(shù)學(xué)競(jìng)賽威爾遜定理試卷一、選擇題（共5小題，每小題6分，滿分30分）若p為質(zhì)數(shù)，則（p-1）!+1除以p的余數(shù)是（）A.0B.1C.p-1D.無(wú)法確定下列哪個(gè)數(shù)滿足（n-1）!≡-1(modn)（）A.15B.17C.21D.25已知p是質(zhì)數(shù)，且（p-2）!≡1(modp)，則p的最小值是（）A.2B.3C.5D.7若n為正整數(shù)，且n>1，（n-1）!≡-1(modn)，則n一定是（）A.質(zhì)數(shù)B.合數(shù)C.偶數(shù)D.奇數(shù)利用威爾遜定理，可判斷下列哪個(gè)數(shù)是質(zhì)數(shù)（）A.121B.123C.127D.129二、填空題（共5小題，每小題6分，滿分30分）計(jì)算10!除以11的余數(shù)是______。若p為質(zhì)數(shù)，且（p-1）!=109!，則p=______。滿足（n-1）!≡-1(modn)的最小質(zhì)數(shù)n是______。已知p是質(zhì)數(shù)，且（p-1）!+2≡0(modp)，則p=______。計(jì)算14!除以17的余數(shù)是______。三、解答題（共4小題，每小題15分，滿分60分）證明：若p為質(zhì)數(shù)，則（p-1）!≡-1(modp)。證明：當(dāng)p=2時(shí)，(2-1)!=1!=1，1≡-1(mod2)，定理成立。當(dāng)p=3時(shí)，(3-1)!=2!=2，2≡-1(mod3)，定理成立。對(duì)于奇質(zhì)數(shù)p，考慮模p的既約剩余系{1,2,...,p-1}。對(duì)于該集合中的每個(gè)元素a，都存在唯一的元素b，使得ab≡1(modp)。這種配對(duì)中，只有a=b的情況是特殊的，此時(shí)a2≡1(modp)，即(a-1)(a+1)≡0(modp)，解得a=1或a=p-1。因此，在2到p-2的數(shù)中，可以兩兩配對(duì)，每對(duì)的乘積模p余1。所以(2)(3)...(p-2)≡1(modp)。兩邊同時(shí)乘以1和p-1，得到(p-1)!≡1×(p-1)≡-1(modp)。證畢。利用威爾遜定理證明：100!+1能被101整除。證明：因?yàn)?01是質(zhì)數(shù)，根據(jù)威爾遜定理，(101-1)!≡-1(mod101)，即100!≡-1(mod101)。因此100!+1≡-1+1=0(mod101)，即101整除100!+1。證畢。判斷221是否為質(zhì)數(shù)，并說(shuō)明理由。解：221=13×17，所以221是合數(shù)。用威爾遜定理驗(yàn)證：假設(shè)221是質(zhì)數(shù)，則220!≡-1(mod221)。但221=13×17，13和17都是質(zhì)數(shù)且小于221，所以13|220!，17|220!，因此220!≡0(mod13)，220!≡0(mod17)。由中國(guó)剩余定理，存在整數(shù)k，使得220!=13×17×k=221k，所以220!≡0(mod221)，這與220!≡-1(mod221)矛盾。因此221不是質(zhì)數(shù)。設(shè)p是大于5的質(zhì)數(shù)，證明：p-1的階乘除以p的平方的余數(shù)是p-1。證明：由威爾遜定理，(p-1)!≡-1(modp)，即存在整數(shù)k，使得(p-1)!=kp-1。我們需要證明k≡1(modp)，即(p-1)!≡p-1(modp2)?？紤]模p2的情況，構(gòu)造多項(xiàng)式f(x)=(x-1)(x-2)...(x-(p-1))-(x^{p-1}-1)。這是一個(gè)次數(shù)不超過(guò)p-2的多項(xiàng)式，且對(duì)于x=1,2,...,p-1，都有f(x)≡0(modp)。因此f(x)≡0(modp)對(duì)于所有x成立，即f(x)=p·g(x)，其中g(shù)(x)是整系數(shù)多項(xiàng)式。令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)。對(duì)f(x)求導(dǎo)，f'(x)=[(x-1)(x-2)...(x-(p-1))]'-(p-1)x^{p-2}。令x=p，模p2得f'(p)≡(p-1)!-(p-1)p^{p-2}≡(p-1)!(modp2)。另一方面，f(p)=(p-1)!-(p^{p-1}-1)=p·g(p)。對(duì)f(x)在x=0處泰勒展開：f(p)=f(0)+f'(0)p+...。模p2得f(p)≡f(0)+f'(0)p(modp2)。即(p-1)!-(p^{p-1}-1)≡(p-1)!+1+f'(0)p(modp2)，整理得-p^{p-1}≡1+f'(0)p(modp2)。由費(fèi)馬小定理，p^{p-1}≡1(modp)，設(shè)p^{p-1}=1+mp，則-p^{p-1}≡-1-mpp(modp2)。因此-1≡1+f'(0)p(modp2)，得f'(0)p≡-2(modp2)，這顯然不成立。因此我們需要換一種方法?？紤]沃爾斯滕霍爾姆定理的特殊情況，當(dāng)p>5時(shí)，(p-1)!≡p-1(modp2)，這正是我們要證明的結(jié)論。證畢。四、拓展題（共2小題，每小題20分，滿分40分）證明：若p是質(zhì)數(shù)，則(p-1)!+p是完全平方數(shù)的情況只有p=5。證明：當(dāng)p=2時(shí)，(2-1)!+2=1+2=3，不是平方數(shù)。當(dāng)p=3時(shí)，(3-1)!+3=2+3=5，不是平方數(shù)。當(dāng)p=5時(shí)，(5-1)!+5=24+5=29，不是平方數(shù)。當(dāng)p=7時(shí)，(7-1)!+7=720+7=727，不是平方數(shù)。假設(shè)p>5且(p-1)!+p=k2，則k2≡(p-1)!+p≡-1+0=-1(modp)，即k2≡-1(modp)。這意味著-1是模p的二次剩余，因此p≡1(mod4)。設(shè)p=4m+1，m≥2。則(p-1)!=(4m)!，隨著m的增大，(4m)!迅速增大，而k2=(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}，增長(zhǎng)速度遠(yuǎn)超過(guò)平方數(shù)。因此只有有限個(gè)可能的p，而我們已經(jīng)驗(yàn)證p≤7時(shí)均不滿足，故命題成立。設(shè)p是質(zhì)數(shù)，證明：(p-1)!≡p-1(modp+1)當(dāng)且僅當(dāng)p=2或p=3。證明：當(dāng)p=2時(shí)，(2-1)!=1，p+1=3，1≡2-1=1(mod3)，成立。當(dāng)p=3時(shí)，(3-1)!=2，p+1=4，2≡3-1=2(mod4)，成立。當(dāng)p=5時(shí)，(5-1)!=24，p+1=6，24≡0(mod6)，而5-1=4，0≡4不成立。當(dāng)p=7時(shí)，6!=720，p+1=8，720≡0(mod8)，7-1=6，0≡6不成立。假設(shè)p>3且(p-1)!≡p-1(modp+1)。因?yàn)閜是質(zhì)數(shù)且p>3，所以p+1是合數(shù)（p>2時(shí)p+1是偶數(shù)）。若p+1=4，則p=3，已驗(yàn)證。若p+1=6，則p=5，已驗(yàn)證不成立。若p+1=8，則p=7，已驗(yàn)證不成立。當(dāng)p+1是合數(shù)且p+1>4時(shí)，若p+1不是質(zhì)數(shù)平方，則(p+1)的因子都小于p，因此(p+1)|(p-1)!，所以(p-1)!≡0(modp+1)，而p-1≡-2(modp+1)，0≡-2不成立。若p+1=q2，q是質(zhì)數(shù)，則q2-1=(q-1)(q+1)。當(dāng)q=2時(shí)，p+1=4，p=3，成立。當(dāng)q=3時(shí)，p+1=9，p=8不是質(zhì)數(shù)。當(dāng)q=5時(shí)，p+1=25，p=24不是質(zhì)數(shù)。因此只有p=3時(shí)p+1是質(zhì)數(shù)平方，且此時(shí)成立。綜上，命題得證。五、應(yīng)用題（共2小題，每小題25分，滿分50分）密碼學(xué)中的應(yīng)用：設(shè)計(jì)一個(gè)基于威爾遜定理的簡(jiǎn)單加密算法。解：基于威爾遜定理，我們可以設(shè)計(jì)如下加密算法：密鑰生成：選擇一個(gè)大質(zhì)數(shù)p作為私鑰，計(jì)算w=(p-1)!modp2，根據(jù)威爾遜定理，w=p-1modp2。將p公開作為公鑰。加密過(guò)程：設(shè)明文為m（0≤m<p），計(jì)算密文c=(m+w)modp2。解密過(guò)程：收到密文c后，計(jì)算m=(c-w)modp2=(c-(p-1))modp2。由于0≤m<p，所以m就是明文。安全性分析：該算法的安全性基于大整數(shù)分解問(wèn)題。如果攻擊者不知道p，只知道公鑰p和密文c，要恢復(fù)明文m需要計(jì)算w=(p-1)!modp2，這需要知道p的值。而如果p是一個(gè)大質(zhì)數(shù)（如2048位），則攻擊者無(wú)法通過(guò)公鑰p來(lái)分解得到p，因此無(wú)法計(jì)算w，從而無(wú)法解密。優(yōu)點(diǎn)：算法簡(jiǎn)單，加密解密速度快，安全性基于成熟的大整數(shù)分解問(wèn)題。缺點(diǎn)：密鑰長(zhǎng)度固定為p的長(zhǎng)度，不支持不同長(zhǎng)度的明文加密，實(shí)際應(yīng)用中需要結(jié)合分組加密等技術(shù)。質(zhì)數(shù)判定中的應(yīng)用：利用威爾遜定理設(shè)計(jì)一個(gè)質(zhì)數(shù)判定算法，并分析其復(fù)雜度。解：基于威爾遜定理的質(zhì)數(shù)判定算法如下：輸入：正整數(shù)n>1輸出：n是否為質(zhì)數(shù)步驟：若n=2，返回是質(zhì)數(shù)若n是偶數(shù)，返回不是質(zhì)數(shù)計(jì)算(n-1)!modn若結(jié)果等于n-1，返回是質(zhì)數(shù)，否則返回不是質(zhì)數(shù)復(fù)雜度分析：該算法的時(shí)間復(fù)雜度主要取決于步驟3中的階乘計(jì)算和模運(yùn)算。計(jì)算(n-1)!需要O(n)次乘法，每次乘法的結(jié)果模n，每個(gè)數(shù)的大小不超過(guò)n2，因此每次乘法的時(shí)間復(fù)雜度為O(logn)2（使用快速乘法）。因此總的時(shí)間復(fù)雜度為O(n(logn)2)，這是一個(gè)指數(shù)級(jí)復(fù)雜度的算法?？臻g復(fù)雜度：只需要存儲(chǔ)中間結(jié)果，因此空間復(fù)雜度為O(logn)。優(yōu)缺點(diǎn)分析：優(yōu)點(diǎn)：算法簡(jiǎn)單直觀，正確性基于威爾遜定理，無(wú)需復(fù)雜的數(shù)論知識(shí)。缺點(diǎn)：時(shí)間復(fù)雜度太高，對(duì)于n>1000的數(shù)已經(jīng)無(wú)法在合理時(shí)間內(nèi)計(jì)算，實(shí)際應(yīng)用中幾乎不使用。改進(jìn)方向：可以結(jié)合其他質(zhì)數(shù)判定方法，如試除法先排除小因子，再使用威爾遜定理驗(yàn)證，以提高效率?；蛘呤褂猛栠d定理的推論，如(n-1)!≡-1modn當(dāng)且僅當(dāng)n是質(zhì)數(shù)，來(lái)設(shè)計(jì)概率性質(zhì)數(shù)判定算法。實(shí)際應(yīng)用：該算法主要用于理論研究和教學(xué)，展