数论-整除

整除是数论中的基础知识。
【flag】博主想要写一套数论整合博客,此博客是第一篇。

声明

本系列博客中提到的数都是整数,

所用的字母除特别申明以外也都表示整数。

整除

设有$a,b$两个数,且满足$b≠0$,如果存在一个数$c$使得$a=bc$,则我们称之为$b$整除$a$,记作$b|a$,显然$b$是$a$的一个约数(因子),而称$a$为$b$的一个倍数。如果不存在上述的数$c$,我们说$b$不能整除$a$,符号是$|$上面加一撇,可以上百度查一下,博主并不会在markdown中打这个高端的符号。

几个简单的性质

传递性

若$b|c$,且$c|a$,则$b|a$,整除性质具有传递性。

加减律

若$b|a$,且$b|c$,则$b|(a+c)$,则为某一整数的倍数的整数之集关于加减运算封闭。

常用结论

若$b|a$,则或者$a=0$,或者$|b|\leq|a|$。因此,若$b|a$而且$a|b$,则$|a|=|b|$.

带余除法

有整数$a$和$b$($b>0$),那就会存在整数$q$和$r$使得$$a=bq+r,其中0\leq r<b$$
并且可以唯一确定。

重要性质

若$n$是正整数,则
$$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+…+xy^{n-2}+y^{n-1})$$
若$n$是正奇数,则
$$x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+…-xy^{n-2}+y^{n-1})$$
这两个结论可以证明$x^n\pm y^n$和$x\mp y$之间的整除关系。

习题

这里的习题大多是数学上的证明,因为数论的最终目的就是得到一个结论,那么程序实现就好弄多了。

习题一

求证:$1\underbrace{0…0}_{200个0}1$被1001整除。

证明:根据重要性质第二条,我们有
\begin{align}
1\underbrace{0…0}_{200个0}1&=10^{201}+1=(10^3)^{67}+1^{67}\
&=(10^3+1)(…) (这里省略不写)\
∴能被1001整除
\end{align}

习题二

设$0\leq n<m$,证明:$(2^{2^n}+1)|(2^{2^m}-1)$.

证明:根据重要性之第一条,我们取$x=2^{2^{n+1}}$,$y=1$,并以$2^{m-n-1}$代替那里的$n$,得出
\begin{align}
2^{2^m}-1&=(2^{2^{n+1}})[(2^{2^{n+1}})^{2^{m-n-1}-1}+…+2^{2^{n+1}}+1]\
故&(2^{2^{n+1}}-1)|(2^{2^{m}}-1)\
又&2^{2^{n+1}}-1=(2^{2^{n}}-1)(2^{2^{n}}+1)\
从而&(2^{2^{n}}+1)|(2^{2^{m}}-1)\
由传递性得证&(2^{2^{n}}+1)|(2^{2^{m}}-1)\
\end{align}

习题三

设整数$a、b、c、d$满足$ad-bc>1$证明:$a、b、c、d$中至少有一个数不能被$ad-bc$整除.

证明:运用反证法,先假设$a、b、c、d$都能被$ad-bc$整除。
所以有
\begin{align}
&(ad-bc)|a\ =>b|a且c|a\
&(ad-bc)|b\ =>a|b且d|b\
&(ad-bc)|c\ =>a|c且d|c\
&(ad-bc)|d\ =>b|d且c|d\
所以得到:&a=b=c=d\
又∵ad-bc>1\
∴矛盾,假设不成立。
\end{align}

#GG
数论——整除。

文章目录
  1. 1. 声明
  2. 2. 整除
    1. 2.1. 几个简单的性质
      1. 2.1.1. 传递性
      2. 2.1.2. 加减律
      3. 2.1.3. 常用结论
      4. 2.1.4. 带余除法
      5. 2.1.5. 重要性质
  3. 3. 习题
    1. 3.1. 习题一
    2. 3.2. 习题二
    3. 3.3. 习题三