美文网首页
习题二

习题二

作者: 洛玖言 | 来源:发表于2019-09-29 10:25 被阅读0次

习题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)}{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.

Sol
证：
必要性：
已知方程有整数解
设 d_0=(a_1,a_2,\cdots,a_n)
则有：
d_0|a_1,\;d_0|a_2,\;\cdots,\;d_0|a_n
又 d 是 a_1,a_2,\cdots,a_n 的线性组合
\therefore d_0|a_1x_1+a_2x_2+\cdots+a_nx_n\Rightarrow d_0|d

充分性：
已知 d_0|d
a_1y_1+a_2y_2+\cdots+a_ny_n=d_0 有整数解
又 d_0|d ，所以方程两边同乘以 m=\dfrac{d}{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{b}{(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{b}{(a,b)}(y-y_0)\\ &\therefore \dfrac{b}{(a,b)}\bigg|\dfrac{b}{(a,b)}(x-x_0)\\ &又\left(\dfrac{a}{(a,b)},\dfrac{b}{(a,b)}\right)=1\\ &必有\dfrac{b}{(a,b)}\bigg|x-x_0\\ &\therefore x-x_0=\dfrac{b}{(a,b)}t\;\;(t\in\mathbb{Z})\\ &\therefore x=x_0+\dfrac{b}{(a,b)}t\\ &\dfrac{a}{(a,b)}\dfrac{b}{(a,b)}t=\dfrac{b}{(a,b)}(y_0-y)\\ &\therefore y= y_0-\dfrac{a}{(a,b)}t \end{aligned}

\begin{aligned} &\therefore \begin{cases} &x=x_0+\frac{b}{(a,b)}t,\\ &y=y_0-\frac{a}{(a,b)}t,&t\in\mathbb{Z}\\ \end{cases} \end{aligned}

整数与多项式-【目录】

相关文章

网友评论

      本文标题：习题二

      本文链接：https://www.haomeiwen.com/subject/olffpctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|习题二|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！