數(shù)論期末考試題及答案一、選擇題（每題3分，共15分）1.以下哪個(gè)數(shù)是質(zhì)數(shù)（）A.1B.9C.11D.15答案：C。質(zhì)數(shù)是指在大于1的自然數(shù)中，除了1和它自身外，不能被其他自然數(shù)整除的數(shù)。1既不是質(zhì)數(shù)也不是合數(shù)，9能被3整除，15能被3和5整除，只有11符合質(zhì)數(shù)定義。2.若\(a\)，\(b\)是整數(shù)，且\(a=bq+r\)（\(0\leqr\lt|b|\)），則\(\gcd(a,b)\)等于（）A.\(\gcd(b,r)\)B.\(\gcd(a,q)\)C.\(\gcd(q,r)\)D.\(\gcd(a,r)\)答案：A。根據(jù)輾轉(zhuǎn)相除法，設(shè)\(d=\gcd(a,b)\)，則\(d\)能整除\(a\)和\(b\)，因?yàn)閈(a=bq+r\)，所以\(r=abq\)，那么\(d\)也能整除\(r\)；設(shè)\(d_1=\gcd(b,r)\)，則\(d_1\)能整除\(b\)和\(r\)，又因?yàn)閈(a=bq+r\)，所以\(d_1\)能整除\(a\)，所以\(\gcd(a,b)=\gcd(b,r)\)。3.同余式\(3x\equiv6\pmod{9}\)的解的個(gè)數(shù)是（）A.1B.2C.3D.4答案：C。先將同余式\(3x\equiv6\pmod{9}\)化簡(jiǎn)，因?yàn)閈(\gcd(3,9)=3\)且\(3\mid6\)，原同余式等價(jià)于\(x\equiv2\pmod{3}\)，在模9的剩余類中，滿足\(x\equiv2\pmod{3}\)的有\(zhòng)(x=2,5,8\)，共3個(gè)解。4.歐拉函數(shù)\(\varphi(12)\)的值為（）A.2B.4C.6D.8答案：B。因?yàn)閈(12=2^2\times3\)，根據(jù)歐拉函數(shù)公式\(\varphi(n)=n\prod_{p|n}(1\frac{1}{p})\)（\(p\)為\(n\)的不同質(zhì)因數(shù)），則\(\varphi(12)=12\times(1-\frac{1}{2})\times(1\frac{1}{3})=12\times\frac{1}{2}\times\frac{2}{3}=4\)。5.以下哪個(gè)數(shù)是模5的原根（）A.1B.2C.3D.4答案：B。對(duì)于模\(p\)的原根\(g\)，\(g\)的各次冪\(g^k(k=1,2,\cdots,p1)\)遍歷模\(p\)的簡(jiǎn)化剩余系。對(duì)于\(p=5\)，\(\varphi(5)=4\)。計(jì)算\(2^1\equiv2\pmod{5}\)，\(2^2\equiv4\pmod{5}\)，\(2^3\equiv3\pmod{5}\)，\(2^4\equiv1\pmod{5}\)，2的各次冪遍歷了模5的簡(jiǎn)化剩余系\(\{1,2,3,4\}\)；\(1\)的各次冪都為\(1\)，\(3^2\equiv4\pmod{5}\)，\(3^3\equiv2\pmod{5}\)，\(3^4\equiv1\pmod{5}\)，\(4^2\equiv1\pmod{5}\)，所以2是模5的原根。二、填空題（每題3分，共15分）1.用輾轉(zhuǎn)相除法求\(\gcd(24,36)\)的值為______。答案：12。\(36=24\times1+12\)，\(24=12\times2+0\)，所以\(\gcd(24,36)=12\)。2.若\(a\equiv3\pmod{7}\)，\(b\equiv5\pmod{7}\)，則\(a+b\equiv\)______\(\pmod{7}\)。答案：1。因?yàn)閈(a\equiv3\pmod{7}\)，\(b\equiv5\pmod{7}\)，則\(a+b\equiv3+5\equiv8\equiv1\pmod{7}\)。3.方程\(x^2\equiv1\pmod{8}\)的解為______。答案：\(x=1,3,5,7\pmod{8}\)。分別將\(x=0,1,2,\cdots,7\)代入\(x^2\pmod{8}\)進(jìn)行計(jì)算：\(1^2\equiv1\pmod{8}\)，\(3^2=9\equiv1\pmod{8}\)，\(5^2=25\equiv1\pmod{8}\)，\(7^2=49\equiv1\pmod{8}\)。4.梅森數(shù)\(M_p=2^p1\)（\(p\)為質(zhì)數(shù)），當(dāng)\(p=3\)時(shí)，\(M_3\)的值為______。答案：7。當(dāng)\(p=3\)時(shí)，\(M_3=2^31=81=7\)。5.若\(n=15\)，則小于\(n\)且與\(n\)互質(zhì)的正整數(shù)的個(gè)數(shù)為______。答案：8。因?yàn)閈(15=3\times5\)，根據(jù)歐拉函數(shù)公式\(\varphi(15)=15\times(1\frac{1}{3})\times(1-\frac{1}{5})=15\times\frac{2}{3}\times\frac{4}{5}=8\)。三、計(jì)算題（每題10分，共30分）1.求解同余方程組\(\begin{cases}x\equiv2\pmod{3}\\x\equiv3\pmod{5}\\x\equiv2\pmod{7}\end{cases}\)解：首先，\(M=3\times5\times7=105\)，\(M_1=\frac{M}{3}=35\)，\(M_2=\frac{M}{5}=21\)，\(M_3=\frac{M}{7}=15\)。然后求\(M_1\)在模3下的逆元\(y_1\)，即求解\(35y_1\equiv1\pmod{3}\)，因?yàn)閈(35\equiv2\pmod{3}\)，則\(2y_1\equiv1\pmod{3}\)，\(y_1=2\)；求\(M_2\)在模5下的逆元\(y_2\)，即求解\(21y_2\equiv1\pmod{5}\)，因?yàn)閈(21\equiv1\pmod{5}\)，則\(y_2=1\)；求\(M_3\)在模7下的逆元\(y_3\)，即求解\(15y_3\equiv1\pmod{7}\)，因?yàn)閈(15\equiv1\pmod{7}\)，則\(y_3=1\)。根據(jù)中國(guó)剩余定理\(x\equiva_1M_1y_1+a_2M_2y_2+a_3M_3y_3\pmod{M}\)，其中\(zhòng)(a_1=2\)，\(a_2=3\)，\(a_3=2\)。\(x\equiv2\times35\times2+3\times21\times1+2\times15\times1\pmod{105}\)\(x\equiv140+63+30\pmod{105}\)\(x\equiv233\pmod{105}\)\(x\equiv23\pmod{105}\)。2.求\(3^{100}\pmod{13}\)的值。解：根據(jù)費(fèi)馬小定理，若\(p\)是質(zhì)數(shù)，\(a\)是整數(shù)且\(\gcd(a,p)=1\)，則\(a^{p1}\equiv1\pmod{p}\)。對(duì)于\(p=13\)，\(\gcd(3,13)=1\)，則\(3^{12}\equiv1\pmod{13}\)。因?yàn)閈(100=12\times8+4\)，所以\(3^{100}=(3^{12})^8\times3^4\)。\((3^{12})^8\equiv1^8\equiv1\pmod{13}\)，\(3^4=81\)，\(81\div13=6\cdots\cdots3\)，所以\(3^{100}\equiv3\pmod{13}\)。3.求\(\gcd(180,252)\)并將其表示為\(180\)和\(252\)的線性組合。解：用輾轉(zhuǎn)相除法：\(252=180\times1+72\)\(180=72\times2+36\)\(72=36\times2+0\)所以\(\gcd(180,252)=36\)。然后進(jìn)行回代：\(36=18072\times2\)又因?yàn)閈(72=252180\)，則\(36=180-(252180)\times2\)\(36=180\times3-252\times2\)。四、證明題（每題10分，共30分）1.證明：若\(a\)，\(b\)是整數(shù)，\(m\)是正整數(shù)，則\(\gcd(ma,mb)=m\gcd(a,b)\)。證明：設(shè)\(d=\gcd(a,b)\)，則\(d\)能整除\(a\)和\(b\)，即\(a=dk_1\)，\(b=dk_2\)，其中\(zhòng)(\gcd(k_1,k_2)=1\)。那么\(ma=mdk_1\)，\(mb=mdk_2\)，所以\(md\)能整除\(ma\)和\(mb\)。設(shè)\(d_1=\gcd(ma,mb)\)，則\(d_1\)能整除\(ma\)和\(mb\)，即\(ma=d_1s\)，\(mb=d_1t\)。因?yàn)閈(d_1\)能整除\(ma\)和\(mb\)，所以\(d_1\)能整除\(m\gcd(a,b)\)（根據(jù)整除的性質(zhì)），又\(md\)能整除\(ma\)和\(mb\)，且\(md\)是\(ma\)和\(mb\)的一個(gè)公因數(shù)，所以\(d_1\)是\(md\)的因數(shù)，同時(shí)\(md\)是\(ma\)和\(mb\)的公因數(shù)，所以\(\gcd(ma,mb)=m\gcd(a,b)\)。2.證明：若\(p\)是質(zhì)數(shù)，\(a\)是整數(shù)且\(\gcd(a,p)=1\)，則\(a^{p1}\equiv1\pmod{p}\)（費(fèi)馬小定理）。證明：考慮模\(p\)的非零剩余類\(\{1,2,\cdots,p1\}\)。因?yàn)閈(\gcd(a,p)=1\)，那么\(a,2a,\cdots,(p1)a\)這\(p1\)個(gè)數(shù)模\(p\)兩兩不同余。假設(shè)\(ia\equivja\pmod{p}\)（\(1\leqi\ltj\leqp1\)），則\(p\mida(ji)\)，由于\(\gcd(a,p)=1\)，所以\(p\mid(ji)\)，但\(0\ltji\ltp1\)，矛盾。所以\(a,2a,\cdots,(p1)a\)模\(p\)的余數(shù)是\(1,2,\cdots,p1\)的一個(gè)排列。則\(a\times2a\times\cdots\times(p1)a\equiv1\times2\times\cdots\times(p1)\pmod{p}\)。即\(a^{p1}(p1)!\equiv(p1)!\pmod{p}\)。因?yàn)閈(\gcd((p1)!,p)=1\)（\(p\)是質(zhì)數(shù)），兩邊同時(shí)除以\((p1)!\)，得到\(a^{p1}\equiv1\pmod{p}\)。3.證明：若\(n\)是合數(shù)，則\(n\)一定有小于等于\(\sqrt{n}\)的質(zhì)因數(shù)。證明：因?yàn)閈(n\)是合數(shù)，則\(n\)可以分解為\(n=ab\)，其中\(zhòng)(1\lta\ltn\)，\(1\ltb\ltn\)。不妨設(shè)\(a\leqb\)，則\(a^2\leqab=n\)，即\(a\leq\sqrt{n}\)。若\(a\)是質(zhì)數(shù)，則\(a\)就是\(n\)的小于等于\(\sqrt{n}\)的質(zhì)因數(shù)；若\(a\)是合數(shù)，則\(a\)可以繼續(xù)分解，設(shè)\(a=p_1p_2\cdotsp_k\)（\(p_i\)為質(zhì)數(shù)），其中必有一個(gè)質(zhì)因數(shù)\(p_i\leq\sqrt{a}\leq\sqrt{n}\)，所以\(n\)一定有小于等于\(\sqrt{n}\)的質(zhì)因數(shù)。五、應(yīng)用題（10分）在RSA加密算法中，取\(p=3\)，\(q=11\)，\(e=7\)，求：（1）\(n\)和\(\varphi(n)\)的值；（2）私鑰\(d\)的值；（3）若明文\(m=5\)，求加密后的密文\(c\)。解：（1）\(n=pq=3\times11=33\)，\(\varphi(n)=(p1)(q1)=(31)\times(111)=20\)。（2）根據(jù)\(ed\equiv1\pmod{\varphi(n)}\)，即\(7d\equiv1\pmod{20}\)。用擴(kuò)展歐幾里得算法求\(d\)：\(20=7\times2+6\)\(7=6\times1+1\)\(1=7-6\)\(6=207\times2\)，則\(1=7-(207\times2)=7\times3-20\times1\)，所以\(d=3\)。（3）根據(jù)加密公式\(c=m^e\pmod{n}\)，已知\(m=5\)，\(e=7\)，\(n