数论测试

一、请给出整除的概念及性质

对于整数 $a,b$ $(b\neq0)$，如果存在整数 $c$，使得 $a=bc$，

则称 $b$ 整除 $a$，记作 $b \mid a$；否则称 $b$ 不整除 $a$，记作 $b \nmid a$。

性质：

二、请给出同余的概念及性质

给定正整数 $m$ 称为模，$a,b$ 为任意两个整数，满足：

则称 $a,b$ 对 $m$ 同余，记作 $a \equiv b \pmod m$，简记为 $a \equiv b\ (m)$。

性质：

三、请给出模 $m$ 的完全剩余系的概念

若 $a_1,a_2,\dots,a_m$ 对模 $m$ 两两不同余，则这 $m$ 个数构成模 $m$ 的一个完全剩余系。

特殊的，任意连续的 $m$ 个整数都构成模 $m$ 的一个完全剩余系。

四、陈述裴蜀定理

对于任意整数 $a,b$，一定存在一组整数解 $x,y$ 使得 $ax+by=(a,b)$。

五、陈述费马小定理

若 $p$ 是素数，则 $a^p\equiv a\pmod p$。

特别的，若 $a\perp p$，则 $a^{p-1}\equiv1\pmod p$。

六、给定模 $m$ 的一组完全剩余系 $x_1,\dots,x_m$，若 $a \perp m$，请证明 $ax_1,\dots,ax_m$ 也是模 $m$ 的一组完全剩余系

反证：假设 $ax_1,\dots,ax_m$ 不是模 $m$ 的完全剩余系。

则一定存在 $i\neq j$ 使得 $ax_i\equiv ax_j\pmod m$。

因为 $a \perp m$，因此有 $x_i\equiv x_j\pmod m$。

与 $x_1,\dots,x_m$ 为模 $m$ 的完全剩余系不符。

假设不成立，故 $ax_1,\dots,ax_m$ 是模 $m$ 的完全剩余系。

七、设 $n$ 是整数，请证明：$120 \mid n(n^2-1)(n^2-5n+26)$

定理：连续 $n$ 个整数的乘积一定被 $n!$ 整除。

对于这 $n$ 个数都是正整数的：

而如果这 $n$ 个数存在不是正整数的，那么一定跨过了 $0$，乘积为 $0$，整除是显然的。

证明：

因为：

因此 $120\mid(n-3)(n-2)(n-1)n(n+1)+20(n-1)n(n+1)$。

即 $120 \mid n(n^2-1)(n^2-5n+26)$。

八、设 $n$ 是正整数，且 $2n+1$ 与 $3n+1$ 都是完全平方数。请证明：$40 \mid n$

性质1：奇数的完全平方数模 $8$ 同余于 $1$。

性质2：任何一个数的平方模 $5$ 同余于 $0,\pm1$。

证明：

因为 $2n+1$ 是奇数且是完全平方数，则

所以，$n$ 是偶数，$3n+1$ 是奇数且是完全平方数，则

且

则有

因此 $n\equiv0\pmod{40}$，即 $40 \mid n$。

九、求 $10^{10} \bmod 7$

即 $10^{10}\bmod7=4$。

十、求满足以下条件的正整数解：$(a,b)+[a,b]+a+b=ab$

设 $d=(a,b)$，则记 $a=a_0d$，$b=b_0d$（$a_0\perp b_0$）。

因为 $a_0b_0\ge a_0b_0,a_0,b_0\ge1$，所以 $0<d\le4$。

当 $d=1$ 时，$a_0+b_0+1=0$，无解。

当 $d=2$ 时，

• $a_0-1=1$，$b_0-1=2$；$a_0=2$，$b_2=3$；$a=4$，$b=6$。
• $a_0-1=2$，$b_0-1=1$；$a_0=3$，$b_2=2$；$a=6$，$b=4$。

当 $d=3$ 时，

• $2a_0-1=1$，$2b_0-1=3$；$a_0=1$，$b_2=2$；$a=3$，$b=6$。
• $2a_0-1=3$，$2b_0-1=1$；$a_0=2$，$b_2=1$；$a=6$，$b=3$。

当 $d=4$ 时，

• $3a_0-1=2$，$3b_0-1=2$；$a_0=b_0=1$；$a=b=4$。
• $2a_0-1=1$，$2b_0-1=4$；不存在整数解。
• $2a_0-1=4$，$2b_0-1=1$；不存在整数解。

因此，可行解有：