解答题
1
| |
手算可以用辗转相除法。比如：
| |
2
| |
手算可以用短除法。比如：
| |
另外最小公倍数必须是正整数（不然可以无穷小）。
3
在 linux bash 环境下，factor 可以用于较小数字的分解：
| |
手算短除。
4
| |
即：$$x^4 - 3x^2 + 9 = (x^2 - 3x + 3)(x^2 + 3x + 3)$$
所以 $$a^4 - 3a^2 + 9$$ 是合数。
手算方法：$$a^4 -3a^2 + 9 = (a^2 + 3)^2 - 9a^2 = (a^2 -3a +3)(a^2 +3a - 3)$$
证明题
1
引理：$$a | n, b | n \Rightarrow lcd(a, b) | n$$
$$2|n, 5|n, 7|n \Rightarrow lcd(2,5,7) | n \Rightarrow70 | n$$
2
引理：
- $$a | n, b | n \Rightarrow lcd(a, b) | n$$
- $$a | n \Leftrightarrow n \equiv 0 \pmod{a}$$
- $$a |b, c | d \Rightarrow ac | bd$$
设三个连续正整数 $$a, a+1, a+2$$
考虑 $$\mathbb{Z}_3$$，因为 $$a \not\equiv a+1 \not\equiv a+2 \pmod{3}$$，三数必构成模 3 完全剩余系，存在 $$x \equiv 0 \pmod{3} $$
考虑 $$\mathbb{Z}_2$$，因为 $$a \not\equiv a+ 1 \pmod{2}$$，二数必构成模 2 的完全剩余系，存在 $$ y \equiv 0 \pmod{2}$$
当 $$x = y$$ 时，$$2 | x, 3 | x \Rightarrow 6 | n \Rightarrow 6 | a(a+1)(a+2)$$
当 $$x \neq y$$ 时，$$2 | y, 3 | x \Rightarrow 6 | xy \Rightarrow 6 | a(a+1)(a+2)$$
NOTE: 穷举最简单
3
引理：$$a(a+1) = 2k$$
设奇数 $$2n+1$$：
$$(2n + 1)^2 = 4n^2 + 4n + 1 = 4n(n+1) + 1 = 8k + 1$$
4
$$\displaystyle mn + pq = (m - p) * \frac{(m-p)n +p(n + q)}{m - p} = (m - p)(n + \frac{p(n+q)}{m-p})$$
因此：$$m-p | p(n+q)$$
$$\displaystyle mq + np = (m - p) * \frac{(m-p)q + p(n + q)}{m-p} = (m-p)(q + \frac{p(n+q)}{m - p})$$
因此：$$m - p | mq + np$$
5
用 sympy.polys.factor 分解 $$a^3 - a = a(a+1)(a - 1)$$。
考虑 $$\mathbb{Z}_3$$，因为 $$a \not\equiv a+1 \not\equiv a - 1 \pmod{3}$$，三数必构成模 3 完全剩余系，存在 $$x \equiv 0 \pmod{3} $$
$$a^3 - a \equiv 0 \pmod{3} \Leftrightarrow 3 | a^3 -a$$
6
令 $$a = (k+1)!$$，
则 $$a+i = (k(k-1)..(a-1)(a+1)…2*1)(a + 1), i \in {2, 3, … k, k+1}$$
7
设 $$k = gcd(a+b, a-b) \Rightarrow a + b = ks, a-b = kt, \text{where } gcd(s, t) = 1$$
则：$$\displaystyle a = \frac{1}{2} k(s+t), b = \frac{1}{2} k(s-t)$$
再设：$$m = gcd(s+t, s-t)$$，
则必有：$$\displaystyle gcd(a, b) = \frac{1}{2}km = 1 \Rightarrow km =2 \Rightarrow k \in {1,2}$$
再证明存在性：$$a = 1, b = 3, gcd(4,2) = 2; a = 2, b = 3, gcd(5,1)=1$$
8
引理：
- $$gcd(a, b) = gcd(a, ak + b)$$
- $$gcd(a, b) = gcd(a, bk)$$
同 7 设 $$k = gcd(a+b, a-b) \Rightarrow a + b = ks, a-b = kt, \text{where } gcd(s, t) = 1$$
则：$$\displaystyle gcd(a+b, a^2 + b^2) = gcd(ks, \frac{1}{2}k^2(s^2 + t^2)) = k *gcd(s, \frac{1}{2}k(s^2 + t^2) )$$
当 $$k=2$$ 时：
- $$gcd(a+b, a^2+b^2) = 2 * gcd(s, s^2 + t^2) = 2 * gcd(s, t^2) =2 * gcd(s, t) = 2$$
当 $$k = 1$$ 时：
- $$\displaystyle gcd(a+b, a^2+b^2) = gcd(s, \frac{1}{2}(s^2 + t^2)) = gcd(s, s^2 + t^2) = 1$$
9
引理：$$\displaystyle a^{st} - 1 = (a^s - 1)(\sum_{i=1}^{t} a^{s(t-i)})$$
设 $$r = gcd(m,n), m = rs, n = rt$$，
对于 $$\displaystyle a^m - 1 = a^{rs} - 1 = (a^r - 1)(\sum_{i=1}^s a^{r(s - i)}) = (a^r - 1)\sum_{i = 0}^{s-1}a^{ri}$$，令 $$\displaystyle T_s = \sum_{i=0}^{s-1} a^{ri}$$
同理可以得到：$$\displaystyle a^n - 1 = a^{rt} - 1 = (a^r - 1)T_t$$
可以用辗转相除证明：
若 s, t 互素，$$\exist u(x), v(x)$$ 为多项式函数，使得 $$u(a) * T_s + v(a) * T_t = 1$$
所以 $$ T_s, T_t$$ 互素，则有：$$gcd(a^m - 1, a^n - 1) = a^r - 1$$
10
引理：$$n(n+1) = 2k(2k+1)$$
$$p_n = n^4 + 2 n^3 + 11n^2 +10n = n(n + 1)(n(n+1) + 10) $$
$$2k(2k+1)(4k^2 + 2k +10) = 4k(2k + 1)(2k^2 + k +5)$$
当 $$k \equiv 0 \pmod{3}$$ 时，$$3 | k \Rightarrow 12 | 4k \Rightarrow12 | p_n$$
当 $$k \equiv 1 \pmod{3}$$ 时，$$3 | 2k + 1 \Rightarrow 12 |4(2k+1) \Rightarrow 12 | p_n$$
当 $$k \equiv 2\pmod{3}$$ 时，$$3 | 2k^2 +k + 5\Rightarrow 12 | p_n$$
11
因为：
对于 $$a \equiv 0 \pmod{3}$$，有 $$a^2 \equiv 0 \pmod{3}$$
对于 $$a \equiv 1 \pmod{3}$$，有 $$a^2 \equiv 1 \pmod{3}$$
对于 $$a \equiv 2 \pmod{3}$$，有 $$a^2 \equiv 1 \pmod{3}$$
所以不存在任何 x，使得 $$x^2 \equiv 2 \pmod{3}$$
对于 $$3 | a^2 +b^2$$，若 $$a^2 \equiv 1 \pmod{1}$$，则 $$b^2 \equiv 2 \pmod{3}$$，这是不存在的。
所以 $$a^2 \equiv 0 \pmod{3}, b^2 \equiv 0 \pmod{3} \Rightarrow 3 |a, 3|b$$
12
对于 $$\mathbb{Z}_{10}$$，用穷举方式很容易验证：$$\forall x, x^5 \equiv x \pmod{10}$$
所以对任意 n 的个位数 $$n_0$$：$$n_0^{k-1} n_0^5 \equiv n_0^{k-1}n_0 \pmod{10} \Rightarrow n_0^{k+4} \equiv n_0^{k} \pmod{10} $$
13
$$n^2 + (n+1)^2 = m^2 + 2 \Leftrightarrow$$
$$2n^2 + 2n + 1 = m^2 + 2$$
因为 $$2n^2 + 2n + 1 \equiv 1 \pmod{2}$$，所以 $$m \equiv 1 \pmod{2}$$
带入：$$m = 2k + 1$$，
$$2n^2 + 2n + 1 = 4 k^2 + 4 k +3 \Leftrightarrow n^2 + n = 2k^2 + 2 k + 1$$
$$n^2 + n \equiv 0 \pmod{2}, 2k^2 + 2 k + 1 \equiv 1 \pmod{2}$$，等式恒不成立。
14
考虑 $$\mathbb{Z}_{n}$$，
设 n 个整数为有序数列 $$a_1, a_2, …a_n$$，其前 m 项和为 $$\displaystyle S_m = \sum_{i=1}^{m} a_i, m= 1,2, …, n$$
若对 $$S_m \equiv T_m \pmod{n}$$ 的取值空间分析，显然其取值空间大小为 n，
- 若 $$\forall i,j \in [1, n], i\neq j \Rightarrow T_i \neq T_j$$，必有 $$\exist S_i \equiv 0 \pmod{n}$$
- 若 $$\exist i,j \in [1, n], i\neq j, T_i = T_j$$，令 $$S_0 = S_i - S_j, S_0 \equiv 0 \pmod{n}$$
15
对于任何 $$k \in [1, 2n], \exist A,B, k = A*2^B, \text{where } A \equiv 1 \pmod{2}, B \ge 0$$
考虑 A 的取值，可知 A 最大为 $$2n-1$$，因此 A 的取值空间大小为 n。
若取出 n+1 个数，则必存在 $$k_1 = A_i 2^{B_1}, k_2 = A_i2^{B_2}$$，二者必存在整除关系
16
同 15，对于任何 $$k \in [1, n], \exist a,b, k = a*2^b, \text{where } a \equiv 1 \pmod{2}, b \ge 0$$
我们令 b 取值空间中的最大值为 B，可知 B 的最大值只出现一次：
- 若出现两次，即存在 $$2^{B} a_1 \neq 2^{B} a_2$$，那么必然存在 $$2^{B+1}a_0 \in [2^Ba_1, 2^Ba_2]$$ ，这与 B 为最大值矛盾。设这个数字为：$$K = 2^{B} A$$
对于 $$\displaystyle S_n = 1 + \frac{1}{2} + … + \frac{1}{n}$$
同乘 $$2^{B-1} a_0 a_1…a_{s-1}$$，其中 s 是 a 的取值空间大小：$$\displaystyle 2^{B-1} a_0 a_1…a_{s-1} S_n = P + 2^{B-1} a_0 a_1…a_{s-1} *\frac{1}{K}$$，其中 P 是一个整数。
显然，$$\displaystyle 2^{B-1} a_0 a_1 … a_{s-1} *\frac{1}{K} = \frac{a_0 a_1 … a_{s-1}}{2 * A}$$ 不是整数，那么 $$S_n$$ 也不是整数。
17
定义：
- 对于 n 为完全平方数，即存在正整数 k，使得 $$k^2 = n$$
引理：
- $$mn$$ 为完全平方数的充要条件是 $$m,n$$ 均为完全平方数
充分性是很显然的。
必要性：
不失一般性，对于 $$\displaystyle n = p_1^{a_1} p_2^{a_2} … p_s^{a_s}$$，我们设仅 $$\alpha_1 \equiv 1 \pmod{2}$$
即证明：对于素数 $$p_1$$，奇数 $$\alpha_1 \equiv 1 \pmod{2}$$，$$p_1^{\alpha_1}$$ 不可能为完全平方数。
对于 $$\forall n \in [1, p_1^{\alpha_1}]$$，有且仅有 $$n = p_1, p_1^{\alpha_1} \equiv 0 \pmod{n}$$
若存在 $$k^2 = p_1^{\alpha_1}$$，则：$$k^2 \equiv 0 \pmod{p_1} \Rightarrow k = p_1 \Rightarrow p_1^2 = p_1^{\alpha_1}$$
由于 $$\alpha_1 \equiv 1 \pmod{2}$$，则 $$p_1 = 1$$，这与 $$p_1$$ 是素数矛盾。
18
若 $$\sqrt[3]{5}$$ 为无理数，设 $$\displaystyle \sqrt[3]{5} = \frac{q}{p}, \text{where }gcd(p, q) = 1$$
则 $$5p^3 = q^3 \Rightarrow 5 | q, q = 5k \Rightarrow p^3 = 5^2k^3 \Rightarrow 5|p \Rightarrow gcd(p,q) \neq 1$$
这与假设矛盾。