2025年大学《数理基础科学》专业题库- 数论证明技巧的应用案例

2025年大学《数理基础科学》专业题库——数论证明技巧的应用案例考试时间：______分钟总分：______分姓名：______一、试用数学归纳法证明：对于任意正整数$n$，都有$1^3+2^3+3^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2$。二、设$a,b$是任意整数，且$a\neq0$。证明：存在唯一的整数$q$和$r$，使得$b=qa+r$，且$0\leqr<|a|$。这里$|a|$表示$a$的绝对值。三、已知整数$n\geq2$，证明：$2^n-1$不是任何素数的平方。四、设$p$是一个素数，$a$是整数，且$p\nmida$（即$p$不能整除$a$）。证明：在模$p$的意义下，$a$有唯一的逆元（即存在唯一的整数$b$，使得$ab\equiv1\pmod{p}$）。五、证明：不存在整数$n$，使得$n^2+n+41$同时是两个不同的素数的平方。六、设$m,n$是正整数。证明：如果$m$和$n$互素（即$\gcd(m,n)=1$），那么对于任意正整数$k$，$m^k+n^k$和$m^n+n^n$也是互素的。七、设$p$是素数，$a$是整数，且$p\nmida$。证明：在整数范围内，方程$x^2\equiva\pmod{p}$有解的充要条件是$a$是$p-1$的倍数（即存在整数$k$，使得$a=k(p-1)$）。八、考虑整数序列$\{a_n\}$，其中$a_1=1$，$a_2=2$，且对于任意$n\geq3$，都有$a_n=a_{n-1}+a_{n-2}$。证明：对于任意正整数$m$，$m$整除$a_m$的充要条件是$m$是3的幂（即存在非负整数$k$，使得$m=3^k$）。试卷答案一、证明：基础情形：当$n=1$时，左边$=1^3=1$，右边$=\left(\frac{1(1+1)}{2}\right)^2=1^2=1$。等式成立。归纳假设：假设当$n=k$（$k\geq1$）时，等式成立，即$1^3+2^3+3^3+\cdots+k^3=\left(\frac{k(k+1)}{2}\right)^2$。归纳步骤：需要证明当$n=k+1$时，等式也成立。左边$=1^3+2^3+3^3+\cdots+k^3+(k+1)^3$根据归纳假设，$1^3+2^3+3^3+\cdots+k^3=\left(\frac{k(k+1)}{2}\right)^2$。所以，左边$=\left(\frac{k(k+1)}{2}\right)^2+(k+1)^3$$=(k+1)^2\left(\left(\frac{k}{2}\right)^2+(k+1)\right)$$=(k+1)^2\left(\frac{k^2}{4}+\frac{2k}{2}+\frac{4}{4}\right)$$=(k+1)^2\left(\frac{k^2+8k+4}{4}\right)$$=(k+1)^2\left(\frac{(k+2)(k+1)}{4}\right)$$=\left(\frac{(k+1)(k+2)}{2}\right)^2$$=\left(\frac{(k+1)((k+1)+1)}{2}\right)^2$。这就是当$n=k+1$时的右边形式。因此，当$n=k+1$时，等式也成立。由数学归纳法原理，对于任意正整数$n$，等式$1^3+2^3+3^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2$都成立。二、证明：存在性：利用欧几里得算法，对任意整数$a,b$（不妨设$a\neq0$），存在整数$q_1,r_1$，使得$b=aq_1+r_1$，且$0\leqr_1<|a|$。如果$r_1=0$，则$b=aq_1$，此时取$q=q_1$，$r=0$，显然满足$b=qa+r$，且$0\leqr<|a|$。如果$r_1\neq0$，则$r_1$是一个非负整数，且$r_1<|a|$。此时取$q=q_1$，$r=r_1$，则$b=qa+r$，且$0\leqr=r_1<|a|$。条件满足。因此，存在整数$q$和$r$，使得$b=qa+r$，且$0\leqr<|a|$。唯一性：假设存在另一组整数$q'$和$r'$，也满足$b=q'a+r'$，且$0\leqr'<|a|$。则$qa+r=q'a+r'$，即$(q-q')a=r'-r$。由于$0\leqr,r'<|a|$，所以$-|a|<r'-r<|a|$。因此，$|(r'-r)|<|a|$。又因为$a\neq0$，所以$|(q-q')|=\frac{|r'-r|}{|a|}$。这意味着$q-q'$是一个绝对值小于1的整数。由于$q,q'$都是整数，所以$q-q'=0$。即$q=q'$。将$q=q'$代入$qa+r=q'a+r'$，得到$qa+r=qa+r'$，所以$r=r'$。因此，整数对$(q,r)$是唯一的。三、证明：用反证法。假设存在整数$n\geq2$，使得$2^n-1$是某个素数$p$的平方，即$2^n-1=p^2$。考虑$n$的奇偶性：如果$n$是偶数，设$n=2k$（$k\geq1$）。则$2^n-1=2^{2k}-1=(2^k-1)(2^k+1)$。因为$k\geq1$，所以$2^k-1\geq2^1-1=1$，且$2^k+1\geq2^1+1=3$。这意味着$2^{2k}-1$是两个大于1的整数$2^k-1$和$2^k+1$的乘积。由于$2^{2k}-1=p^2$是一个素数的平方，它只能分解为$1\timesp^2$或$p\timesp$。但是$2^k-1\neq1$（因为$n\geq2$，所以$k\geq1$，$2^k\geq2$），且$2^k+1\neqp$（因为$2^k+1>2^k-1\geq1$）。因此，$2^{2k}-1$不能分解为两个大于1的整数的乘积。这与$2^{2k}-1=(2^k-1)(2^k+1)$矛盾。所以，$n$不能是偶数。如果$n$是奇数，设$n=2k+1$（$k\geq1$）。根据费马小定理，如果$p$是奇素数，且$a$是整数，$p\nmida$，则$a^{p-1}\equiv1\pmod{p}$。令$a=2$，则$p$是奇素数，$p\nmid2$，所以$2^{p-1}\equiv1\pmod{p}$。因为$p^2=2^n-1$，所以$p=\sqrt{2^n-1}$是奇数。将$p=\sqrt{2^n-1}$代入$2^{p-1}\equiv1\pmod{p}$，得到$2^{\sqrt{2^n-1}-1}\equiv1\pmod{\sqrt{2^n-1}}$。两边同时平方，得到$2^{2(\sqrt{2^n-1}-1)}\equiv1\pmod{2^n-1}$。即$2^{2\sqrt{2^n-1}-2}\equiv1\pmod{2^n-1}$。设$m=2\sqrt{2^n-1}-2$，则$2^m\equiv1\pmod{2^n-1}$。根据数论知识，如果$a^k\equiv1\pmod{m}$，则$a$的阶$d$整除$k$，且$d$是$m$的原根阶。这里$a=2$，$m=2^n-1$。$2^n-1=p^2$是素数的平方，其因数只有$1,p,p^2,2^n-1$。如果$d=1$，则$2^1\equiv1\pmod{2^n-1}$，即$2\equiv1\pmod{2^n-1}$，所以$2^n\equiv0\pmod{2^n-1}$，即$2^n-1\mid2^n$。这是不可能的，因为$n\geq2$。如果$d=p$，则$p\midm$，即$p\mid2\sqrt{2^n-1}-2$。因为$p=\sqrt{2^n-1}$，所以$p\mid2p-2$，即$p\mid2(p-1)$。由于$p$是奇素数，$p\nmid2$，所以$p\midp-1$。这意味着$p-1=kp$，其中$k$是整数。$p=kp+1$，即$p(k-1)=1$。由于$p$是素数，$p\neq1$，所以$k-1\neq0$，即$k\neq1$。因此，$p(k-1)=1$只有当$p=-1,k=0$或$p=1,k=1$时才成立。但$p$是素数，所以$p\neq1$，故$p\neq-1$。因此，$p(k-1)=1$无整数解。所以，$d\neqp$。如果$d=p^2$，则$p^2\midm$，即$p^2\mid2\sqrt{2^n-1}-2$。同样，$p^2\mid2p-2$，即$p^2\mid2(p-1)$。由于$p$是素数，$p\nmid2$，所以$p^2\nmid2$。因此，$p^2\midp-1$。这意味着$p-1=kp^2$，其中$k$是整数。$p=kp^2+1$，即$p(kp^2-1)=1$。由于$p$是素数，$p\neq1$，所以$kp^2-1\neq0$，即$kp^2\neq1$。因此，$p(kp^2-1)=1$无整数解。所以，$d\neqp^2$。$d$只能是$2^n-1$本身，即$d=2^n-1$。这意味着$2^{2\sqrt{2^n-1}-2}\equiv1\pmod{2^n-1}$，且$2^{2^n-1}\equiv1\pmod{2^n-1}$。即$2^{2\sqrt{2^n-1}-2}\equiv2^{2^n-1}\pmod{2^n-1}$。因为$2^n-1=p^2$，所以$2^n\equiv1\pmod{2^n-1}$。因此，$2^{2^n-1}\equiv2^1\equiv2\pmod{2^n-1}$。所以，$2^{2\sqrt{2^n-1}-2}\equiv2\pmod{2^n-1}$。即$2^{2\sqrt{2^n-1}-2}-2\equiv0\pmod{2^n-1}$。这意味着$2^n-1$整除$2^{2\sqrt{2^n-1}-2}-2$。令$t=\sqrt{2^n-1}$，则$t$是整数，$2^n-1=t^2$。上式变为$2^{2t-2}-2\equiv0\pmod{t^2}$。即$2^{2t-2}\equiv2\pmod{t^2}$。即$2^{2t-3}\equiv1\pmod{t^2}$。如果$t=1$，则$2^n-1=1^2=1$，所以$n=1$。但这与$n\geq2$矛盾。如果$t>1$，则$t^2>1$。考虑$2^{2t-3}\equiv1\pmod{t^2}$。根据欧拉定理，如果整数$a$与正整数$n$互素，则$a^{\phi(n)}\equiv1\pmod{n}$。令$a=2$，$n=t^2$。由于$t$是奇数（$2^n-1=t^2$是奇数），所以$t^2$是奇数。因为$2$与任何奇数互素，所以$2$与$t^2$互素。因此，$2^{\phi(t^2)}\equiv1\pmod{t^2}$。计算$\phi(t^2)=t^2-t=t(t-1)$。所以，$2^{t(t-1)}\equiv1\pmod{t^2}$。由于$t\geq3$（因为$n\geq2$，若$n=2$，则$2^2-1=3$，所以$t\geq3$），我们有$t-1\geq2$。$t(t-1)\geq3\times2=6$。因此，$2^{t(t-1)}$的阶$d$整除$t(t-1)$，且$d$是$t^2$的原根阶。如果$d=1$，则$2^1\equiv1\pmod{t^2}$，即$2\equiv1\pmod{t^2}$，这是不可能的。如果$d=2$，则$2^2\equiv1\pmod{t^2}$，即$4\equiv1\pmod{t^2}$，即$t^2\mid3$。这是不可能的，因为$t\geq3$。如果$d=3$，则$2^3\equiv1\pmod{t^2}$，即$8\equiv1\pmod{t^2}$，即$t^2\mid7$。这是不可能的。如果$d=6$，则$2^6\equiv1\pmod{t^2}$，即$64\equiv1\pmod{t^2}$，即$t^2\mid63$。这是不可能的，因为$t\geq3$。如果$d>6$，则$d$是$t^2$的原根阶，但原根阶至少是$\phi(t^2)=t(t-1)$，而$t\geq3$，$t(t-1)\geq6$。所以$d\geqt(t-1)\geq6$。这意味着$2^{t(t-1)}\equiv1\pmod{t^2}$，且$t(t-1)$是$t^2$的原根阶。这与$2^{2t-3}\equiv1\pmod{t^2}$矛盾。因为$2t-3\leq2t-4<t(t-1)$（对于$t\geq3$）。一个数的阶是$d$，则该数的$k$次幂$\equiv1\pmod{n}$当且仅当$k$是$d$的倍数。所以，$2^{2t-3}\equiv1\pmod{t^2}$要求$2t-3$是$t(t-1)$的倍数。但$2t-3<t(t-1)$且$2t-3$与$t(t-1)$互素（因为$t\geq3$）。所以，$2^{2t-3}\equiv1\pmod{t^2}$是不可能的。综合奇偶性和以上分析，无论$n$是奇数还是偶数，假设$2^n-1=p^2$都会导出矛盾。因此，不存在整数$n\geq2$，使得$2^n-1$是某个素数$p$的平方。四、证明：必要性：设$b$是$a$在模$p$意义下的逆元，即$ab\equiv1\pmod{p}$。这意味着存在整数$k$，使得$ab=1+kp$。因为$p\nmida$，所以$a$与$p$互素。根据贝祖定理，由于$\gcd(a,p)=1$，存在整数$x,y$，使得$ax+py=1$。令$x=b$，$y=k$，则有$ab+py=1$。这可以写成$ab=1-py$。因为$p\midpy$，所以$p\mid(1-py)$，即$p\mid1$。由于$p$是素数，所以$p\mid1$只有当$p=1$。这与$p$是素数矛盾（素数大于1）。因此，必要性不成立。修正：必要性其实是：如果$ab\equiv1\pmod{p}$，则$a$与$p$互素。因为$ab\equiv1\pmod{p}$意味着$ab-1=kp$对某个$k$成立，即$a(b-kp)=1$。所以$a$是$1$的倍数，$a$与$kp$互素。因为$p$是素数，所以$a$与$p$互素。实际上，必要性应该是：如果$b$存在，则$a$与$p$互素。充分性：假设$a$与$p$互素，即$\gcd(a,p)=1$。根据贝祖定理，存在整数$x,y$，使得$ax+py=1$。令$x=b$，则$ab+py=1$。这可以写成$ab=1-py$。两边同时取模$p$，得到$ab\equiv1-py\pmod{p}$。因为$p\midpy$，所以$py\equiv0\pmod{p}$。因此，$ab\equiv1\pmod{p}$。这表明$b$是$a$在模$p$意义下的一个逆元。现在证明唯一性：假设$b_1,b_2$都是$a$在模$p$意义下的逆元，即$ab_1\equiv1\pmod{p}$且$ab_2\equiv1\pmod{p}$。则$ab_1\equivab_2\pmod{p}$。因为$a$与$p$互素，所以可以消去$a$（乘以$a$的逆元），得到$b_1\equivb_2\pmod{p}$。由于$b_1,b_2$都是整数，且模$p$同余意味着它们只相差$p$的倍数，所以$b_1\equivb_2\pmod{p}$意味着$b_1=b_2$（因为$b_1,b_2$是整数，且通常考虑最小正剩余）。因此，逆元是唯一的。五、证明：用反证法。假设存在整数$n\geq2$，使得$n^2+n+41$同时是两个不同的素数$p$和$q$的平方，即$n^2+n+41=p^2$且$n^2+n+41=q^2$，其中$p\neqq$。则$p^2=q^2$。由于$p,q$都是素数，且$p\neqq$，所以$p,q$均为奇数。因此，$p^2,q^2$都是奇数。两个奇数的平方相等，只有当这两个奇数相等。即$p=q$。这与假设$p\neqq$矛盾。因此，不存在整数$n\geq2$，使得$n^2+n+41$同时是两个不同的素数的平方。六、证明：必要性：假设$m^k+n^k$和$m^n+n^n$不互素，即存在素数$p$，使得$p\midm^k+n^k$且$p\midm^n+n^n$。因为$p$是素数，所以$p\midm^k+n^k$意味着$m^k\equiv-n^k\pmod{p}$。同样，$p\midm^n+n^n$意味着$m^n\equiv-n^n\pmod{p}$。因为$\gcd(m,n)=1$，所以$m,n$都不是$p$的倍数，即$m\not\equiv0\pmod{p}$，$n\not\equiv0\pmod{p}$。将$m^k\equiv-n^k\pmod{p}$两边乘以$m^{n-k}$，得到$m^{k+n-k}\equiv-n^km^{n-k}\pmod{p}$，即$m^n\equiv-n^km^{n-k}\pmod{p}$。将$m^n\equiv-n^n\pmod{p}$代入上式，得到$-n^n\equiv-n^km^{n-k}\pmod{p}$。即$n^n\equivn^km^{n-k}\pmod{p}$。因为$p\midm^n+n^n$，所以$n^n\equiv-m^n\pmod{p}$。将$m^n\equiv-n^n\pmod{p}$代入上式，得到$n^n\equiv-(-n^n)\pmod{p}$，即$n^n\equivn^n\pmod{p}$。这个等式总是成立，但无法得出$p=1$或$p\midm,n$。我们尝试从$m^k\equiv-n^k\pmod{p}$和$m^n\equiv-n^n\pmod{p}$推导出矛盾。因为$\gcd(m,n)=1$，$p$不能同时整除$m$和$n$。假设$p\midm$，则$m\equiv0\pmod{p}$。$m^k\equiv0^k\equiv0\pmod{p}$，所以$-n^k\equiv0\pmod{p}$，即$n^k\equiv0\pmod{p}$。因为$n\not\equiv0\pmod{p}$，所以$n^k\not\equiv0\pmod{p}$。矛盾。假设$p\midn$，则$n\equiv0\pmod{p}$。$n^k\equiv0^k\equiv0\pmod{p}$，所以$-m^k\equiv0\pmod{p}$，即$m^k\equiv0\pmod{p}$。因为$m\not\equiv0\pmod{p}$，所以$m^k\not\equiv0\pmod{p}$。矛盾。因此，$p$不能整除$m$或$n$。现在，因为$p\midm^k+n^k$，且$p\nmidm,n$，所以$m^k\equiv-n^k\pmod{p}$。因为$p\nmidn$，所以$n^k\not\equiv0\pmod{p}$，从而$m^k\not\equiv0\pmod{p}$。同理，$m^n\equiv-n^n\pmod{p}$，且$m^n\not\equiv0\pmod{p}$，$n^n\not\equiv0\pmod{p}$。现在考虑$m^k+n^k\equiv0\pmod{p}$和$m^n+n^n\equiv0\pmod{p}$。因为$m^k\equiv-n^k\pmod{p}$，所以$m^k+n^k\equiv-n^k+n^k\equiv0\pmod{p}$。因为$m^n\equiv-n^n\pmod{p}$，所以$m^n+n^n\equiv-n^n+n^n\equiv0\pmod{p}$。这说明$p$整除$m^k+n^k$和$m^n+n^n$。这与$\gcd(m,n)=1$矛盾。根据贝祖定理，存在整数$x,y$使得$mx+ny=1$。如果$p\midm^k+n^k$且$p\midm^n+n^n$，那么$p$也应该整除$m(mx+ny)^k+n(mx+ny)^k$和$m(mx+ny)^n+n(mx+ny)^n$。但计算比较复杂，且之前的推导已表明假设矛盾。更简单的方法是：如果$p\midm^k+n^k$且$p\midm^n+n^n$，则$p\mid(m^k+n^k)(m^n+n^n)-m^kn^n-n^km^n$。即$p\midm^{k+n}+n^{k+n}+m^kn^n+n^km^n-m^kn^n-n^km^n$。即$p\midm^{k+n}+n^{k+n}$。因为$p\midm^k+n^k$和$p\midm^n+n^n$，且$\gcd(m,n)=1$，这推导出$p\midm^{k+n}+n^{k+n}$。这与$\gcd(m,n)=1$矛盾。所以，$m^k+n^k$和$m^n+n^n$必须互素。充分性：假设$m^k+n^k$和$m^n+n^n$互素，即$\gcd(m^k+n^k,m^n+n^n)=1$。需要证明$\gcd(m,n)=1$。用反证法。假设$\gcd(m,n)=d>1$。则$d\midm$且$d\midn$。因为$d>1$，所以$d$是一个素数或合数。如果$d$是素数，设$d=p$。则$p\midm$且$p\midn$。因为$p\neq2$（否则$m,n$均为偶数，$\gcd(m,n)\geq2$，但若$m=n=2$，则$\gcd(2^k+2^k,2^n+2^n)=4$，与互素矛盾。所以$d$不能是2）。因为$p\midm$，所以$p\midm^k$。因为$p\midn$，所以$p\midn^k$。所以$p\midm^k+n^k$。同理，$p\midm^n+n^n$。这意味着$p$是$m^k+n^k$和$m^n+n^n$的一个公约数。这与假设$\gcd(m^k+n^k,m^n+n^n)=1$矛盾。如果$d$是合数，设$d=ab$，其中$a,b$是大于1的正整数。则$d\midm$且$d\midn$。因为$d>1$，所以$a>1$且$b>1$。因为$d\midm$，所以$ab\midm$，即$a\midm$或$b\midm$（因为$a,b>1$）。假设$a\midm$，则$a\leqd$。同理，$a\midn$，则$a\leqd$。因此，$a$是$m,n$的一个公约数，且$a\leqd$。因为$d$是最大公约数，所以$a\leqd$，且$a$必须等于$d$（否则存在更大的公约数）。所以$d=a$是合数，且$d$是$m,n$的一个大于1的公约数。这同样与$\gcd(m,n)=1$矛盾。因此，假设$\gcd(m,n)=d>1$是错误的。所以，$\gcd(m,n)=1$。七、证明：必要性：假设方程$x^2\equiva\pmod{p}$有解，设整数$x_0$是其解，即$x_0^2\equiva\pmod{p}$。则$x_0^2-a=kp$对某个整数$k$成立。考虑$a=k(p-1)+a'$，其中$a'=a\pmod{p-1}$。因为$a\equivx_0^2\pmod{p}$，所以$a\equivx_0^2\pmod{p-1}$（因为$p-1\equiv-1\pmod{p}$，所以$x^2\equiva\pmod{p}$意味着$x^2\equiva\pmod{p-1}$）。因此，$a'$是$a$除以$p-1$的余数，且$0\leqa'<p-1$。根据欧拉定理，如果整数$a$与正整数$n$互素，则$a^{\phi(n)}\equiv1\pmod{n}$。令$a=a'$，$n=p-1$。因为$p$是素数，所以$p-1$是正整数。因为$p$是素数，所以$a'$与$p-1$互素（因为$a'<p-1$，且$a'$与$p$互素，所以$a'$与$p-1$互素）。因此，$a^{\phi(p-1)}\equiv1\pmod{p-1}$。计算$\phi(p-1)$。因为$p-1$是$p$的阶乘除以$p$的阶乘（对于$p$的倍数），且$p$是素数，所以$\phi(p-1)$是$p-1$的欧拉函数值。所以，$a^{\phi(p-1)}\equiv1\pmod{p-1}$。即$a^{\phi(p-1)}