笔记 - 数论

· · 算法·理论

上课时做的笔记，可能略显凌乱，不建议作为数论入门用，但是可以用作知识补充，或者结论与证明合集。

整除

b \mod a = 0 \Rightarrow a|b a|b, b|c \Rightarrow a|c a|b,a|c \Rightarrow a|mb+nc, m,n \in \Z

例 2.1. 证：若 n 为整数，则 6|n(n+1)(n+2)。

\because 2|n(n+1)(n+2), 3|n(n+1)(n+2) \therefore 6|n(n+1)(n+2)

例 2.2. 证：若 n 为整数，则 6|n(n+1)(2n+1)。

① n=3k \Rightarrow 3|n(n+1)(2n+1)

② n=3k+1 \Rightarrow 2n+1=6k+3 \Rightarrow 3|n(n+1)(2n+1)

③ n=3k+2 \Rightarrow n+1=3k+3 \Rightarrow 3|n(n+1)(2n+1)

又 \because 2|n(n+1)(2n+1)

\therefore 6|n(n+1)(2n+1)

习题 1.1. 证：12|n(n+1)(n+2)(n+3)

\because 3|n(n+1)(n+2)(n+3), 4|n(n+1)(n+2)(n+3) \therefore 12|n(n+1)(n+2)(n+3)

习题 1.2. 证：6|n(4n+1)(7n+5)

① n=2k \Rightarrow 2|n(4n+1)(7n+5)

② n=2k+1 \Rightarrow 7n+5=14k+12 \Rightarrow 2|n(4n+1)(7n+5)

\qquad\Rightarrow 2|n(4n+1)(7n+5)

① n=3k \Rightarrow 3|n(4n+1)(7n+5)

② n=3k+1 \Rightarrow 7n+5=21k+12 \Rightarrow 3|n(4n+1)(7n+5)

③ n=3k+2 \Rightarrow 4n+1=12k+9 \Rightarrow 3|n(4n+1)(7n+5)

\qquad\Rightarrow 3|n(4n+1)(7n+5) \therefore 6|n(4n+1)(7n+5)

例 3.1. 求所有整数 n 使 n|n^2+4

\frac{n^2+4}{n}=n+\frac{4}{n} \in \Z \Rightarrow n|4 \Rightarrow n=\pm 1,\pm 2,\pm 4

例 3.2. 求所有整数 n 使 n+1|n^2+5

（换元法）设 m=n+1,n=m-1，则 m|(m-1)^2+5 \Rightarrow m|m^2-2m+6

\therefore \frac{m^2-2m+6}{m}=m-2+\frac{6}{m} \in \Z \therefore m=\pm 1,\pm 2,\pm 3,\pm 6\\ \therefore n=5,2,1,0,-2,-3,-4,-7

例 3.4. 求所有整数 n 使 n-1|n^3+5

设 m=n-1,n=m+1，则 m|(m+1)^3+5 \Rightarrow m|m^3+3m^2+3m+6

\therefore \frac{m^3+3m^2+3m+6}{m} = m^2+3m+3+\frac{6}{m} \therefore m=\pm 1,\pm 2,\pm 3,\pm 6\\ \therefore n=7,4,3,2,0,-1,-2,-5

整数的可整除性特征

  1. 被 2 或 5 整除的数特征是末位数字能被 2 或 5 整除

  2. 被 4 或 25 整除的数特征是末两位数字能被 4 或 25 整除

    证明：除了末两位以外的所有数是 100 的倍数，而 100 可被 4 和 25 整除。

    如果末两位能被 4 或 25 整除，那么整个数也能被 4 或 25 整除，否则则不行

  3. 被 8 或 125 整除的数特征是末三位数字能被 8 或 125 整除

证明类似上文

例 1.1. 证：若 2a+b=16，则 \overline{5ab} 能被 4 整除

4|\overline{4ab}\\ \Leftarrow 4|\overline{ab}\\ \Leftarrow 4|10a+b\\ \Leftarrow 4|8a+2a+b\\ \Leftarrow 4|2a+b \because 2a+b=16\\ \therefore 4|2a+b\\ \therefore 4|\overline{4ab}

例 1.2. 证：若 4b+2c+d=16，则 \overline{3bcd} 能被 8 整除

8|\overline{3bcd}\\ \Leftarrow 8|\overline{bcd}\\ \Leftarrow 8|100b+10c+d\\ \Leftarrow 8|4b+2c+d \because 4b+2c+d=16\\ \therefore 8|4b+2c+d\\ \therefore 8|\overline{3bcd}

  1. 被 3 整除的数特征是各位数字的和能被 3 整除

  2. 被 9 整除的数特征是各位数字的和能被 9 整除

  3. 被 99 整除的数特征是把多位数从个位开始两位一段，所有数段的和能被 99 整除

例 2. 整数 \overline{13ab456} 能被 99 整除，则 a,b 的值？

\because 99|\overline{13ab456} \therefore 99|1+\overline{3a}+\overline{b4}+56\\ \Rightarrow 99|91+a+10b\\ \Rightarrow a=8,b=0

习题 4. 六位数 \overline{2a01b8} 能被 12 整除，这样的六位数有多少个？

12|\overline{2a01b8} \Rightarrow 3|\overline{2a01b8}$ 且 $4|\overline{2a01b8} 4|\overline{2a01b8} \Rightarrow 4|10b+8 \Rightarrow b=0,2,4,6,8 例 $4$. $72\ |\ \overline{a275} \times \overline{472b} \because 72\ |\ \overline{a275} \times \overline{472b}, 72=8 \times 9 \therefore 8|\overline{472b} \Rightarrow 8|\overline{72b} \Rightarrow b=0,8 b=0 \Rightarrow 9|\overline{a275} \Rightarrow 9|a+14 \Rightarrow a=4 b=9 \Rightarrow \overline{472b}=4728 \Rightarrow 3|4728 \\ \Rightarrow 3|\overline{a275} \Rightarrow 3|a+14 \Rightarrow a=1,4,7

同余

a \bmod m = b \bmod m \Leftrightarrow a \equiv b (\bmod\ m)

性质 1

a \equiv b (\bmod\ m)\\ \Leftrightarrow m|(a-b)\\ \Leftrightarrow a-b=mk

性质 2

a \equiv b (\bmod\ m), c \equiv d (\bmod\ m)\\ \Leftrightarrow a+c \equiv b+d (\bmod\ m)
a+c \equiv r_1+r_2 (\bmod\ m) \equiv b+d (\bmod\ m)

性质 3

a \equiv b (\bmod\ m), c \equiv d (\bmod\ m)\\ \Leftrightarrow ac \equiv bd (\bmod\ m)\\ \Leftrightarrow a^n \equiv b^n (\bmod\ m)

例 1. 证：3^{2020}+4^{2019} 被 5 整除

4^{2019} \equiv (-1)^{2019} (\bmod\ 5) \equiv -1 (\bmod\ 5) 3^{2020} \equiv 9^{1010} (\bmod\ 5) \equiv (-1)^{1010} (\bmod\ 5) \equiv 1 (\bmod\ 5) \therefore 3^{2020}+4^{2019} \equiv 0 (\bmod\ 5)

例 2. n \in \Z^+，证：3|(n^3-n)

3|(n^3-n) \Leftrightarrow n^3 \equiv n (\bmod\ 3)

① n \equiv 0 (\bmod\ 3) \Rightarrow n^3 \equiv 0 (\bmod\ 3), n \equiv 0 (\bmod\ 3) \Rightarrow n^3 \equiv n (\bmod\ 3)

② n \equiv 1 (\bmod\ 3) \Rightarrow n^3 \equiv 1 (\bmod\ 3), n \equiv 1 (\bmod\ 3) \Rightarrow n^3 \equiv n (\bmod\ 3)

③ n \equiv 2 (\bmod\ 3) \Rightarrow n^3 \equiv 2 (\bmod\ 3), n \equiv 2 (\bmod\ 3) \Rightarrow n^3 \equiv n (\bmod\ 3)

费马小定理：\large\mathbf{k|n^k-n}

7^{3k} \equiv 1 (\bmod\ 9)

末位数问题

  1. 0,1,5,6$ 的任何正整数幂，末位数仍然是 $0,1,5,6
\Leftrightarrow 10 | n^{m+4}-n^m n^{m+4}-n^m = n^{m-1}(n^5-n) \because 5|n^5-n, 2|n^5-n \therefore 10|n^5-n \therefore 10|n^{m-1}(n^5-n) \Rightarrow 10 | n^{m+4}-n^m

同余的应用

质数与合数

$n$ 的正因数个数为 $(a_1+1)(a_2+1)\dots(a_k+1) \sum_{x|n}^{x>0}1=\prod_{i=1}^{k}(a_i+1) n$ 的所有正因数和为 $(1+p_1^1+p_1^2+ \dots +p_1^{a_1})(1+p_2^1+p_2^2+ \dots +p_2^{a_2})(1+p_3^1+p_3^2+ \dots +p_3^{a_3}) \dots (1+p_k^1+p_k^2+ \dots +p_k^{a_k}) \sum_{x|n}^{x>0}x=\prod_{i=1}^{k}\sum_{j=0}^{a_i}p_i^j

因数

\gcd(a,b)=\gcd(b,a) $\gcd(a,b)=\gcd(b,a \bmod b)$（辗转相除法） $\gcd(a,b,c)=\gcd(\gcd(a,b),c) \gcd(ka,kb)=k \times \gcd(a,b) $\gcd(a,b)\times\textrm{lcm}(a,b)=a \times b
a=p_1^{ \alpha_1} \times p_2^{ \alpha_2} \times \dots \times p_k^{\alpha_k} b=p_1^{ \beta_1} \times p_2^{ \beta_2} \times \dots \times p_k^{\beta_k} a \times b=p_1^{ \alpha_1+\beta_1} \times p_2^{ \alpha_2+\beta_2} \times \dots \times p_k^{ \alpha_k+\beta_k} \gcd(a,b)=p_1^{\min(\alpha_1,\beta_1)} \times p_2^{\min(\alpha_2,\beta_2)} \times \dots \times p_k^{\min(\alpha_k,\beta_k)} \textrm{lcm}(a,b)=p_1^{\max(\alpha_1,\beta_1)} \times p_2^{\max(\alpha_2,\beta_2)} \times \dots \times p_k^{\max(\alpha_k,\beta_k)}

斐波那契数列

见此处。

完全剩余系（完系）

根据 \bmod\ m 的余数把整数分为 m 类，每一类中取出一个组成完全剩余系

  1. 性质 1：a_1,a_2,\dots,a_m 模 m 的结果互不相同，则构成 m 的一个完全剩余系

  2. 性质 2：连续 m 个数构成 m 的一个完全剩余系，且这些数中包含 m 的倍数

费马小定理

若 p 为质数，a 为正整数。

a^{p-1} \equiv 1 (\bmod\ p) a^p \equiv a (\bmod\ p)

裴蜀定理

若 a,b 是整数且 \gcd(a,b)=d，则对于任意整数 m,n；d|am+bn，特别的，一定存在整数 m,n 使 am+bn=d