2025年大学《数理基础科学》专业题库- 数论证明技巧讨论

2025年大学《数理基础科学》专业题库——数论证明技巧讨论考试时间：______分钟总分：______分姓名：______一、1.设$a,b$是整数，$a\neq0$。若存在整数$q,r$使得$b=qa+r$，且$0\leq|r|<|a|$，则称$r$是$a$除$b$的余数。证明：若$d$是$a,b$的一个公因数，则$d$也是$a$除$b$的余数$r$的因数。2.设$p$是素数，$a$是整数。证明：若$p\mida^2$，则$p\mida$。二、1.证明：对于任意整数$n\geq2$，$n!+1$不是一个素数的平方。2.设$n$是正整数。证明：若$2^n-1$是素数，则$n$是素数。三、1.设$a\equivb\pmod{m}$，$c\equivd\pmod{m}$。证明：$a+c\equivb+d\pmod{m}$，$ac\equivbd\pmod{m}$。2.解同余方程$3x\equiv4\pmod{7}$。四、1.设$n$是正整数。证明：若$n$不是完全平方数，则$\sqrt{n}$不是有理数。2.证明：存在无穷多个形如$4k+3$的素数。五、1.证明：对于任意正整数$n$，$n^3+5n$能被6整除。2.设$a,b,c$是整数，且$a^2+b^2=c^2$。证明：若$a,b,c$都不是完全平方数，则其中至少有两个数是偶数。六、1.证明：若$p$是素数，则$\phi(p)=p-1$，其中$\phi$是欧拉函数。2.设$n$是正整数，$a$是整数。证明：若$a^n\equiva\pmod{m}$，则$a^{n-1}\equiv1\pmod{m}$或$a\equiv0\pmod{m}$。七、1.证明：若$a\equivb\pmod{m}$，则$\gcd(a,m)=\gcd(b,m)$。2.应用中国剩余定理，解同余方程组：\[\begin{cases}x\equiv2\pmod{3}\\x\equiv3\pmod{5}\\x\equiv2\pmod{7}\end{cases}\]试卷答案一、1.证明：由$b=qa+r$知$d|b$且$d|a$。又由$r=b-qa$知$d|r$。因此，$d$是$a$除$b$的余数$r$的因数。2.证明：若$p\mida^2$，则存在整数$k$使得$a^2=pk$。若$p\nmida$，则根据欧几里得算法，存在整数$q,r$使得$a=qp+r$，且$0<r<p$。则$a^2=(qp+r)^2=p^2q^2+2pqr+r^2$。由于$p|a^2$，则$p|r^2$。又因为$0<r<p$，所以$r^2<p^2$，这与$p|r^2$矛盾。因此，$p\mida$。二、1.证明：用反证法。假设存在整数$n\geq2$，$n!+1$是一个素数的平方，设为$p^2$，则$n!=p^2-1=(p-1)(p+1)$。由于$n\geq2$，则$n!\geq2!=2$。因此，$p-1$和$p+1$是两个大于1的连续整数，它们必然有一个合数，且这个合数不大于$n!$。这与$n!=(p-1)(p+1)$是素数的乘积矛盾。因此，$n!+1$不是一个素数的平方。2.证明：用反证法。假设存在素数$p=2^k-1$，其中$k>1$不是素数，设$k=ab$，其中$a,b>1$。则$p=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\cdots+2^a+1)$。由于$a>1$，则$2^a-1>1$。因此，$p$是一个合数，这与$p$是素数矛盾。因此，若$2^n-1$是素数，则$n$是素数。三、1.证明：由$a\equivb\pmod{m}$知存在整数$k_1$使得$a=b+k_1m$。由$c\equivd\pmod{m}$知存在整数$k_2$使得$c=d+k_2m$。则$a+c=(b+k_1m)+(d+k_2m)=(b+d)+(k_1+k_2)m$。因此，$a+c\equivb+d\pmod{m}$。同理，$ac=(b+k_1m)(d+k_2m)=bd+bk_2m+dk_1m+k_1k_2m^2=bd+(bk_2+dk_1+k_1k_2m)m$。因此，$ac\equivbd\pmod{m}$。2.解：由$3x\equiv4\pmod{7}$，两边同时乘以$\gcd(3,7)=1$的逆元$5$（因为$3\cdot5=15\equiv1\pmod{7}$），得$x\equiv4\cdot5\pmod{7}$，即$x\equiv20\pmod{7}$，即$x\equiv6\pmod{7}$。四、1.证明：用反证法。假设$\sqrt{n}$是有理数，则存在整数$p,q$，其中$q>0$且$\gcd(p,q)=1$，使得$\sqrt{n}=\frac{p}{q}$。平方两边得$n=\frac{p^2}{q^2}$，即$nq^2=p^2$。因此，$p^2$是一个完全平方数，$n$也是完全平方数。这与$n$不是完全平方数矛盾。因此，$\sqrt{n}$不是有理数。2.证明：用反证法。假设不存在无穷多个形如$4k+3$的素数，则所有素数都形如$4k$或$4k+1$。考虑所有形如$4k$的数，它们都是4的倍数，因此不是素数（除了$p=2$）。考虑任意整数$N$，存在一个最大的形如$4k+1$的素数$p_N$，使得$p_N\leqN$。则$4(p_N-1)=4p_N-4=4N-4$是一个合数，它不能被任何小于等于$N$的形如$4k+1$的素数整除。因此，它必须被一个形如$4k+3$的素数整除。设这个素数为$p$，则$p|4N-4$，即$p|4(N-1)$。由于$p$是形如$4k+3$的素数，所以$p\neq2$，因此$p$不能整除4，所以$p$必须整除$N-1$。则存在整数$k$使得$N-1=pk$，即$N=pk+1$。由于$p$是形如$4k+3$的素数，则$pk$形如$4k'$+3，因此$N=pk+1$形如$4k'+4=4(k'+1)$，即$N$形如$4k$。这与$N$被$p_N$整除且$p_N$形如$4k+1$矛盾。因此，存在无穷多个形如$4k+3$的素数。五、1.证明：$n^3+5n=n(n^2+5)$。若$n$是偶数，则$n$能被2整除，因此$n(n^2+5)$能被2整除。若$n$是奇数，则$n^2$是奇数，$n^2+5$是偶数，因此$n^2+5$能被2整除，从而$n(n^2+5)$能被2整除。因此，$n^3+5n$能被2整除。又因为$n(n^2+5)=n(n^2+4+1)=n(n^2+4)+n=n(n+2)(n-2)+n=n(n+2)(n-2)+n(n+1)(n-1)$。若$n$是偶数，则$n(n+2)(n-2)$能被4整除。若$n$是奇数，则$n(n+1)(n-1)$能被4整除。因此，$n^3+5n$能被4整除。综上所述，$n^3+5n$能被2整除且能被3整除，因此$n^3+5n$能被6整除。2.证明：用反证法。假设$a,b,c$都不是完全平方数，且它们都是奇数。则$a^2,b^2,c^2$都是奇数，且$a^2+b^2=c^2$表示一个奇数的平方等于两个奇数的平方和。这与勾股定理的结论矛盾（两个奇数的平方和不可能是一个奇数的平方）。因此，若$a^2+b^2=c^2$，则$a,b,c$不可能都是奇数。因此，$a,b,c$中至少有两个数是偶数。六、1.证明：由欧拉函数的定义，$\phi(p)$是小于$p$的正整数中与$p$互质的数的个数。由于$p$是素数，小于$p$的正整数都与$p$互质。因此，$\phi(p)$等于小于$p$的正整数的个数，即$\phi(p)=p-1$。2.证明：若$a\equiv0\pmod{m}$，则$a^{n-1}\equiv0^{n-1}\equiv0\pmod{m}$，命题成立。若$a\not\equiv0\pmod{m}$，则$\gcd(a,m)=1$。由$a^n\equiva\pmod{m}$得$a^{n-1}\equiv1\pmod{m}$。七、1.证明：由$\gcd(a,m)=d$知存在整数$k_1,k_2$使得$a=dk_1$，$m=dk_2$，且$\gcd(k_1,k_2)=1$。由$a\equivb\pmod{m}$知存在整数$k_3$使得$b=a+mk_3=dk_1+dk_2k_3=d(k_1+k_2k_3)$。因此，$d|b$。又因为$\gcd(k_1,k_2)=1$，所以$\gcd(k_1+k_2k_3,k_2)=1$。因此，$d=\gcd(a,m)=\gcd(dk_1,dk_2)=d\cdot\gcd(k_1,k_2)=d\cdot1=d$。同理可证$\gcd(b,m)=d$。因此，$\gcd(a,m)=\gcd(b,m)$。2.解：首先，解第一个同余方程$x\equiv2\pmod{3}$。其通解为$x=3k+2$，其中$k$是整数。将这个通解代入第二个同余方程$x\equiv3\pmod{5}$，得$3k+2\equiv3\pmod{5}$，即$3k\equiv1\pmod{5}$。由于$3\cdot2=6\equiv1\pmod{5}$，所以$k\equiv2\pmod{5}$。其通解为$k=5j+2$，其中$j$是整数。将这个通解代入$x=3k+2$，得$x=3(5j+2)+2=15j+8$。因此，$x\equiv8\pmod{15}$。将这个解代入第三个同余方程$x\equiv2\pmod{7}$，得$15j+8\equiv2\pmod{7