数论测试

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

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

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

性质：

\def\arraystretch{1.1} \begin{array}{rlrl} 1.&a\mid b&\Longrightarrow&\pm a \mid \pm b\\ 2.&a \mid b,\ b\mid c&\Longrightarrow&a \mid c\\ 3.&\forall i:b\mid a_i&\Longrightarrow&b\mid\Sigma\ a_ik_i\\ 4.&b\mid a&\Longrightarrow&bc\mid ac\ (c\in\mathbb Z,c\neq0)\\ 5.&b\mid a\ (a\neq0)&\Longrightarrow&|b|\le|a|\\ 5.&b\mid a,\ |a|<|b|&\Longrightarrow&a=0\\ \end{array}

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

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

\def\arraystretch{1.1} \begin{array}{ll} a=q_1m+r_1,&0\le r_1<m\\ b=q_2m+r_2,&0\le r_2<m\\ \end{array}

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

性质：

\def\arraystretch{1.1} \begin{array}{rlrl} 1.&a \equiv a \pmod m\\ 2.&a \equiv b \pmod m &\Longleftrightarrow& b\equiv a \pmod m\\ 3.&a\equiv b\pmod m,\ b\equiv c\pmod m&\Longrightarrow&a\equiv c\pmod m\\ 4.&aK\equiv bK\pmod m&\Longrightarrow&a\equiv b\pmod{\frac{m}{(m,k)}}\\ 5.&a\equiv b\pmod m,\ c\equiv d\pmod m&\Longrightarrow&a\pm c\equiv b\pm d\pmod m\\ 6.&a\equiv b\pmod m,\ c\equiv d\pmod m&\Longrightarrow&ac\equiv bd\pmod m\\ \end{array}

三、请给出模 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 个数都是正整数的：

\begin{array}{l} (a+1)(a+2)\dots(a+n)=\frac{(a+n)!}{a!}=n!\frac{(a+n)!}{n!a!}=n!\binom{a+n}{a} \end{array}

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

证明：

\def\arraystretch{1.1} \begin{array}{ll} &n(n^2-1)(n^2-5n+26)\\ =&n(n+1)(n-1)[(n-2)(n-3)+20]\\ =&(n-3)(n-2)(n-1)n(n+1)+20(n-1)n(n+1) \end{array}

因为：

\def\arraystretch{1.1} \begin{array}{rcl} 120&\mid& (n-3)(n-2)(n-1)n(n+1)\\ 6&\mid& (n-1)n(n+1)\\ 120&\mid& 20(n-1)n(n+1) \end{array}

因此 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。

(2k+1)^2\equiv4k(k+1)+1\equiv1\pmod8

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

\def\arraystretch{1.1} \begin{array}{lcll} t&\equiv&0,\pm1,\pm2&\pmod5\\ t^2&\equiv&0,\pm1&\pmod5 \end{array}

证明：

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

\def\arraystretch{1.1} \begin{array}{rcll} 2n+1&\equiv&1&\pmod8\\ n&\equiv&0&\pmod4 \end{array}

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

\def\arraystretch{1.1} \begin{array}{rcll} 3n+1&\equiv&1&\pmod8\\ n&\equiv&0&\pmod8 \end{array}

且

\def\arraystretch{1.1} \begin{array}{rcll} 2n+1&\equiv&0,\pm1&\pmod5\\ 3n+1&\equiv&0,\pm1&\pmod5 \end{array}

则有

\def\arraystretch{1.1} \begin{array}{rcll} (2n+1)+(3n+1)&\equiv&2&\pmod5\\ 2n+1&\equiv&1&\pmod5\\ 3n+1&\equiv&1&\pmod5\\ n&\equiv&0&\pmod5 \end{array}

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

九、求 10^{10} \bmod 7

\def\arraystretch{1.1} \begin{array}{ll} &10^{10} \bmod 7\\ =&(10 \bmod 7)^{10\bmod 6}\bmod 7\\ =&3^4\bmod7\\ =&81\bmod7\\ =&4 \end{array}

即 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）。

\def\arraystretch{1.1} \begin{array}{rcl} (a,b)+[a,b]+a+b&=&ab\\ d+a_0b_0d+a_0d+b_0d&=&a_0b_0d^2\\ a_0b_0+a_0+b_0+1&=&a_0b_0d \end{array}

因为 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 时，

\def\arraystretch{1.1} \begin{array}{rcl} a_0b_0+a_0+b_0+1&=&2a_0b_0\\ a_0b_0-a_0-b_0&=&1\\ a_0(b_0-1)-(b_0-1)&=&2\\ (a_0-1)(b_0-1)&=&2\\ \end{array}

• 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 时，

\def\arraystretch{1.1} \begin{array}{rcl} a_0b_0+a_0+b_0+1&=&3a_0b_0\\ 2a_0b_0-a_0-b_0&=&1\\ 4a_0b_0-2a_0-2b_0&=&2\\ 2a_0(2b_0-1)-(2b_0-1)&=&3\\ (2a_0-1)(2b_0-1)&=&3\\ \end{array}

• 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 时，

\def\arraystretch{1.1} \begin{array}{rcl} a_0b_0+a_0+b_0+1&=&4a_0b_0\\ 3a_0b_0-a_0-b_0&=&1\\ 9a_0b_0-3a_0-3b_0&=&3\\ 3a_0(3b_0-1)-(3b_0-1)&=&4\\ (3a_0-1)(3b_0-1)&=&4\\ \end{array}

• 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；不存在整数解。

因此，可行解有：

(a,b)=(4,6),(6,4),(3,6),(6,3),(4,4)