习题2

1

设 $n$ 是正整数，证明： $\dfrac{21n+4}{14n+3}$ 是既约分数.

Sol
要证明 $\dfrac{21n+4}{14n+3}$ 是既约分数
只需证明 $\left(21n+4,14n+3\right)=1$
只需找到一组整数 $x,y$ 满足
$(21n+4)x+(14n+3)y=1$ 恒成立
整理得 $(21x+14y)n+(4x+3y)=1$
$\begin{cases} &21x+14y=0\\ &4x+3y=1\\ \end{cases}$
$\Rightarrow \begin{cases} &x = -2\\ &y = 3\\ \end{cases}$
由 Bezout定理，知 $\dfrac{21n+4}{14n+3}$ 是既约分数

2

设 $n$ 是正整数，证明： $(n!+1,(n+1)!+1)=1$ .

Sol
同样用 Bezout定理
$(n!+1,(n+1)!+1)=(n!+1,-n)$
试图找出一组整数 $x,y$ 满足
$(n!+1)x+(-n)y=1$
$\begin{cases} &n!x+(-n)!y=0\\ &x=1 \end{cases}$
$\Rightarrow \begin{cases} &x = 1\\ &y = (n-1)! \end{cases}$
由 Bezout定理，知 $(n!+1,(n+1)!+1)=1$

3

设 $m,n$ 为正整数， $m$ 是奇数.证明： $(2^m-1,2^n+1)=1.$

Sol
$\begin{aligned} &\because m是奇数\\ &2^n+1|2^{mn}+1\\ &又 \;2^m-1|2^{mn}-1\\ &\therefore p(2^n+1)=2^{mn}+1\\ &\quad\, q(2^m-1)=2^{mn}-1\\ &\therefore p(2^n+1)=q(2^m-1)+2\\ &\therefore 2^n+1|q(2^m-1)+2\\ &设\;(2^n+1,2^m-1)=d\\ &\therefore d|2^n+1\Rightarrow d|q(2^m-1)+2\\ &又 d|2^m-1\\ &\therefore d|2\\ &又\; d|2^n+1,\;\;d|2^m-1\\ &\therefore d\not = 2\\ &\therefore d=1 \end{aligned}$

4

设 $m,n,a$ 均为正整数，且 $a>1$ . 证明：
$(a^m-1,a^n-1)=a^{(m,n)}-1$

Sol
设 $(m,n)=d,\;\;m=pd,\;\;n=qd$ 有:
$a^m-1=a^{pd}-1=(a^d-1)(a^{(p-1)d}+a^{(p-2)d}+\cdots+a+1)$
$a^n-1=a^{qd}-1=(a^d-1)(a^{(q-1)d}+a^{(q-2)d}+\cdots+a+1)$
易知 $(a^m-1,a^n-1)\geqslant a^d-1$
只需证明
$(a^{(p-1)d}+a^{(p-2)d}+\cdots+a+1,a^{(q-1)d}+a^{(q-2)d}+\cdots+a+1)=1$ 即可
不妨假设 $m>n$
使用欧几里德算法可在有限步内得到最大公约数为 1.
令 $a_0=a^{(p-1)d}+a^{(p-2)d}+\cdots+a+1$
$b_0=a^{(q-1)d}+a^{(q-2)d}+\cdots+a+1$
$a_0=k_0b_0+a^r+a^{r-1}+\cdots+1$
$b_0=k_1(a^r+a^{r-1}+\cdots+1)+a^{r_1}+a^{r_1-1}+\cdots+1$
$\cdots$
$a+1=1\cdot (a+1)$
$\therefore (a^{(p-1)d}+a^{(p-2)d}+\cdots+a+1,a^{(q-1)d}+a^{(q-2)d}+\cdots+a+1)=1$
所以得证.

5

设 $a,b$ 是不为 0 或 $\pm1$ 的整数. 证明：存在整数 $x,y$ , 满足
$ax+by=(a,b)$
且 $0<|x|<|b|,\;0<|y|<|a|.$

Sol
若 $a|b$ 或 $b|a$ 易知结论成立.
若不满足上式：
先证明 $ax+by=(a,b)$ 有一组整数解
$\begin{aligned} &a= bq_0+r_0,\;\;(0<r_0<|b|)\\ &b= r_0q_1+r_1,\,\,(0<r_1<r_0)\\ &r_0=r_1q_2+r_2,(0<r_2<r_1)\\ &\vdots\\ &r_{n-2}=r_{n-1}q_n+r_n,(0<r_n<r_{n-1})\\ &r_{n-1}=r_nq_{n+1}\\ &\therefore (a,b)=r_n\\ \end{aligned}$
我们可以借此倒推回去：
通过上面倒数第二行有
$(a,b)=r_{n}=r_{n-2}-r_{n-1}q_n$
用 $r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}$
可以消去 $r_{n-1}$ ，有：
$(a,b)=(1+q_{n-1}q_n)r_{n-2}-r_{n-3}q_n$
如此反复，最终可解得一组整数解 $x,y$
现证明存在满足 $0<|x|<|b|,\;0<|y|<|a|$
不妨假设 $a>0,\;x_1=bq+r\;\;(0<r<|b|)$
有 $ax_1+by_1=a(bq+r)+by_1=(a,b)$
$a(bq+r)+by_1=ar+b(aq+y_1)$
$0<|aq+y_1|=\left|\dfrac{ar-(a,b)}\right|<|a|$
令
$\begin{cases} &x=r\\ &y= aq+y_1 \end{cases}$
得证:存在这样这样的一组 $x,y$

勘误：这题实际上有问题，最后的结论应该改成：
$0\leqslant|x|<|b|,\;0\leqslant|y|<|a|.$

先看第一个反例， $a=b=2$ 时，有 $2x+2y=2\rightarrow x+y=1$
又 $<|x|<2,\;0<|y|<2$
易知只有 $x=\pm1,\;y=\pm1$
显然等式 $x+y=1$ 没有满足条件的整数解
即 $a=b=2$ 时，等式没有满足条件的整数解
这时候想的还是只要把满足的条件，四个不等号随便把一个改成 $\leqslant$ 都可以

然后这时候，有同学说，第一步也不是那么显然，然后发现好像也有点问题

不妨假设 $b|a$ ，有 $a=mb>0$
$ax+by=(a,b)=b$
$mx+y=1$
我们可以轻松的找到一组整数解
$\begin{cases} &x_0 = b\\ &y_0 = 1-a \end{cases}$
引用以下第(11)题的结论
通解为
$\begin{cases} &x = x_0+t=b+t\\ &y = y_0-mt=1-a-mt\\ &t\in\mathbb{Z} \end{cases}$
试图找到一组 $x,y$
$0<|x|<|b|$ 即 $0<|b+t|<|b|$
解得 $-2b<t<0$ 且 $t\not =0$
同理
$0<|y|<|a|$ 即 $0<|1-a-mt|<|a|$
不妨设 $m>0$
解得 $t>\dfrac1m$ 或 $t<\dfrac{1-2a}{m}$

由上可知 $-2b<t<\dfrac{1-2a}{m}=\dfrac1m-2b\leqslant1-2b$
所以不存在这样的整数 $t$
若 $m<0$ 同理可知不存在这样的 $t$ .

所以题目的条件大约是有问题的，个人觉得比较好的解决方案就是，把最后的满足改为
$0\leqslant|x|<|b|,\;0\leqslant|y|<|a|$
这样的话就是真的显然了.

9

设 $n$ 为正整数， $k$ 为正奇数，证明
$(1+2+\cdots+n)|(1^k+2^k+\cdots+n^k)$

Sol
欲证 $(1+2+\cdots+n)|(1^k+2^k+\cdots+n^k)$
只需证 $n(n+1)|2(1^k+2^k+\cdots+n^k)$
又有
$\begin{aligned} &n|1^k+(n-1)^k\\ &n|2^k+(n-1)^k\\ &\cdots\\ &n|n^k\\ &\therefore n|2(1^k+2^k+\cdots+n^k) \end{aligned}$
又有
$\begin{aligned} &n+1|1^k+n^k\\ &n+1|2^k+(n-1)^k\\ &\cdots\\\ &\therefore n+1|2(1^k+2^k+\cdots+n^k) \end{aligned}$
又 $(n,n+1)=1$
$\therefore n(n+1)|2(1^k+2^k+\cdots+n^k)$

10

设 $a_1,a_2,\cdots,s_n$ 是不全为零的整数，则方程
$a_1x_2+a_2x_2+\cdots+a_nx_n=d$
有整数解 $x_1,x_2,\cdots,x_n$ 的充分必要条件是 $(a_1,a_2,\cdots,a_n)|d$ .

充分性：
已知 $d_0|d$
$a_1y_1+a_2y_2+\cdots+a_ny_n=d_0$ 有整数解
又 $d_0|d$ ，所以方程两边同乘以 $m=\dfrac2cccccccc8{d_0}\in\mathbb{N}$
有 $a_1(my_1)+a_2(my_2)+\cdots+a_n(my_n)=d$
令 $x_k=my_k$ ，所以有
$a_1x_1+a_2x_2+\cdots+a_nx_n=d$ 有整数解.

11

设 $a,b,c$ 为整数， $(a,b)|c$ . 设 $x=x_0,\;y=y_0$ 是方程
$ax+by=c \tag{1}$
的一组整数解（称为方程(1)的特解），则方程(1)的全部整数解（通解）为
$x=x_0+\dfrac{(a,b)}t,\\y=y_0-\dfrac{a}{(a,b)}t.$
其中 $t$ 为任意整数.

Sol
已知 $x_0,y_0$ 是方程的一组解
$\begin{aligned} &\therefore ax_0+by_0=c\\ &\quad\; ax+by=c\\ &\Rightarrow ax_0+by_0=ax+by\\ &\Rightarrow a(x-x_0)=b(y_0-y)\\ &\dfrac{a}{(a,b)}(x-x_0)=\dfrac{(a,b)}(y-y_0)\\ &\therefore \dfrac{(a,b)}\bigg|\dfrac{(a,b)}(x-x_0)\\ &又\left(\dfrac{a}{(a,b)},\dfrac{(a,b)}\right)=1\\ &必有\dfrac{(a,b)}\bigg|x-x_0\\ &\therefore x-x_0=\dfrac{(a,b)}t\;\;(t\in\mathbb{Z})\\ &\therefore x=x_0+\dfrac{(a,b)}t\\ &\dfrac{a}{(a,b)}\dfrac{(a,b)}t=\dfrac{(a,b)}(y_0-y)\\ &\therefore y= y_0-\dfrac{a}{(a,b)}t \end{aligned}$