整数的定义和带余除法

整数的定义和带余除法

整除的定义

设 $a,b\in \mathbb{Z}$ , 且 $b\ne 0$。若存在 $q\in \mathbb{Z}$, 有 $a=qb$, 则称 $b$ 是 $a$ 的因数 (或约数), 或 $a$ 是 $b$ 的倍数, 或 $b$ 能整除 $a$, 或 $a$ 能被 $b$ 整除, 记作 $b\mid a$。若对任意的 $q\in \mathbb{Z}$, 有 $a\ne qb$, 则称 $a$ 不能被 $b$ 整除, 记作 $b\nmid a$。

命题1

设 $a,0\ne b\in \mathbb{Z}$ (此处假设 $\mathbb{Z}$ 代表整数集), 则:

1. $b\mid 0$; 即0是任何非0整数的因数
2. $1\mid a$; 即1是任何整数的因数
3. 当 $a\ne 0$ 时, $a\mid a$. 即任何一个非0整数都是它自身的因数

命题2

设 $a,0\ne b,s\in \mathbb{Z}$ (此处假设 $\mathbb{Z}$ 代表整数集), 则:

1. 若 $b\mid a$, 则 $b\mid as$;
2. $b\mid a$ 当且仅当 $-b\mid a$ (即 $a$ 的因数总是成对出现);
3. $b\mid a$ 当且仅当 $b\mid |a|$. (即 $a$ 与 $|a|$ 的所有因数相同)

定理1

设$a,0\ne b,0\ne c\in \mathbb{Z}$,则若$b\mid a,c\mid b$,则$c\mid a$。 （整除的传递性）

定理2

设 $a,b\in \mathbb{Z}$ 都是 $m$ 的倍数, 则 $a\pm b$ 也都是 $m$ 的倍数.

也就是说$m\mid a,m\mid b\Rightarrow m\mid (ka+cb)$

例题1

已知$x,y\in \mathbb{Z}$,若$5\mid (x-y)$,证明$5\mid (3x+2y)$。

• $3x+2y=3(x-y)+5y,且5\mid 5y,5\mid 3(x-y)\Rightarrow 5\mid (3x+2y)$, 证毕。

例题2

已知$x,y\in \mathbb{Z}$,若$5\mid (x-y)$,证明$5\mid (6x-11y)$。

• $6x-11y=6(x-y)-5y,且5\mid 5y,5\mid 6(x-y)\Rightarrow 5\mid (6x-11y)$, 证毕。

定理3

设 $a_1,a_2,\dots ,a_n\in \mathbb{Z}$ 都是 $m$ 的倍数, $q_1,q_2,\dots ,q_n\in \mathbb{Z}$, 则 $q_1{a}_1+q_2{a}_2+\cdots +q_n{a}_n$ 也是 $m$ 的倍数。

这个定理是定理2的一个扩展，用数学语言表示为

若$m\mid a_i(i=1,2,\dots ,n),q_i\in \mathbb{Z},$则$m\mid (q_1{a}_1+q_2{a}_2+\cdots +q_n{a}_n)$。

命题3

1. 若 $c\mid a,c\nmid b$, 则 $c\nmid (a\pm b)$;
2. 若 $b\mid a,c\ne 0$, 则 $bc\mid ac$; 反之, 若 $bc\mid ac$, 则 $b\mid a$;
3. 若 $b\mid a,c\mid d$, 则 $bc\mid ad$;
4. 若 $a=b+c,d\mid a,d\mid b$, 则 $d\mid c$。

来证一下$3$和$4$

• $3$的证明： $b\mid a,\exists p\in \mathbb{Z},st.a=bp,c\mid d,\exists q\in \mathbb{Z},st.d=cq\Rightarrow ad=(pq)(bc)$，由整数的定义得证。
• $4$的证明： $d\mid a,\exists p\in \mathbb{Z},st.a=dp,同理b=dq\Rightarrow dp=dq+c\Rightarrow c=d(p-q)$得证。

命题4

1. 若 $n$ 是正整数, $a\ne b$, 则 $a-b\mid a^n-b^n$;
2. 若 $n$ 是正奇数, $a\ne -b$, 则 $a+b\mid a^n+b^n$;
3. 若 $n$ 是正偶数, $a\ne -b$, 则 $a+b\mid a^n-b^n$.

这里可以利用因式分解

$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}{b}^2+\cdots +a{b}^{n-2})$那么$1$显然是成立的

当$n$是正奇数的时候，有$a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}{b}^2-\cdots -a{b}^{n-2}+b^{n-1})$ 那么$2$也显然成立

当$n$是正偶数的时候，有$a^n-b^n=(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}{b}^2-\cdots +a{b}^{n-2}-b^{n-1})$ 那么$3$也显然成立

命题5

1. 若 $c\mid ab$, 且 $(b,c)=1$ (此处 $(b,c)$ 表示 $b$ 和 $c$ 的最大公约数), 则 $c\mid a$;
2. 若 $b\mid a,c\mid a$, 且 $(b,c)=1$ (此处 $(b,c)$ 表示 $b$ 和 $c$ 的最大公约数), 则 $bc\mid a$;
3. 若 $b\mid a,c\mid a$, 则 $[b,c]\mid a$ (此处 $[b,c]$ 表示 $b$ 和 $c$ 的最小公倍数).

Bézout’s Identity（贝祖/裴蜀定理）

对于两个不全为0的整数$a$和$b$,存在一对整数$x$和$y$，使得$ax+by=gcd(a,b)$，简单来说就是，若$gcd(a,b)=d$,则

$\exists x,y\in \mathbb{Z},$有$d=ax+by$。这里我们先不做证明，等到后面再证，这里先直接拿来用即可，求解$x,y$需要用到扩展欧几里得算法。

贝祖定理告诉我们，两个整数 $a$ 和 $b$ 的最大公约数，总可以表示成 $a$ 和 $b$ 的某个整数倍的组合（即线性组合）。而且，能够写成 $ax+by$ 这种形式的最小正整数，恰好就是 $a$ 和 $b$ 的最大公约数。

还有一个需要用到的小结论是$bc=gcd(b,c)lcm(b,c)$即两个数的乘积等于这两个数的最大公约数乘以最小公倍数。

证明

• $1$的证明： $c\mid ab\Rightarrow \exists q\in \mathbb{Z},使得ab=cq.又因为(b,c)=1\Rightarrow \exists s,t\in \mathbb{Z}使得bs+ct=1(贝祖定理)\Rightarrow$

• $a(bs+ct)=a=(ab)s+cat=cqs+cat=c(qs+at)$即$a=c(qs+at)$从而可以得到$c\mid a$ 证毕。

• $2$的证明： $b\mid a\Rightarrow \exists p\in \mathbb{Z},使得a=bp.$

• $c\mid a\Rightarrow \exists q\in \mathbb{Z},使得a=cq.$

• $(b,c)=1\Rightarrow \exists s,t\in \mathbb{Z}使得bs+ct=1(贝祖定理)$

• 等式两边同时乘以$a$然后将$a=bp,a=cq$带入化简得

• $a(bs+ct)=abs+act=cqbs+bpct=bc(qs+pt)=a$从而可以推出$bc\mid a$ 证毕。

• $3$的证明： 不妨设$m=[b,c]=lcm(b,c)$ 分类讨论

• 当$a=0$时，则$b|a,c|a,[b,c]|a$都成立 (由命题1可得到)

• 当$a\ne 0$时，$b\mid a\Rightarrow \exists p\in \mathbb{Z},使得a=bp.\Rightarrow b=\frac{a}{p}$

• $c\mid a\Rightarrow \exists q\in \mathbb{Z},使得a=cq.\Rightarrow c=\frac{a}{q}$

• $a\ne 0\Rightarrow p\ne 0,q\ne 0$由$m=[b,c]=\frac{bc}{(b,c)}=\frac{\frac{a}{p}\frac{a}{q}}{bs+ct}$

• 从而$m(pq)(bs+ct)=a^2$

• $m(pqbs+pqct)=m(aqs+apt)=ma(qs+pt)=a^2$而$a\ne 0$可以约去

• 所以$m(qs+pt)=a$ 所以$[b,c]\mid a$ 证毕。

不难看出$2$是$3$的特殊情况，当$gcd(b,c)=1$时，它俩的最小公倍数就是$bc$。

带余除法的定义(定理4)

定理4

设$a,b\in \mathbb{Z}$且$b>0$,则存唯一的两个整数$q$和$r$,使得$a=bq+r$,其中$0\le r<b$. （带余除法） 或者说$amodb=r$

这个定理是说$a$除以$b$的余数是$r$.

定理4推论1

设$a,b\in \mathbb{Z}$且$b\ne 0$，则存在唯一一对整数$q$和$r$,使得$a=bq+r$,其中$0\le r<\left|b\right|$

这个和定理4不一样的地方在于$b$的范围 证明很容易：

• 当$b>0$时，由定理4，存在唯一的一对整数$q,r$ ,有$a=bq+r$且$0\le r<b=\left|b\right|$
• 当$b<0$时，则$-b>0$，由定理4，存在唯一的一对整数$q,r$,有$a=(-b)q+r=b(-q)+r$,且$0\le r<-b=\left|b\right|$

定义2

在定理4中，$q$叫做$a$被$b$除的不完全商,$r$叫做a被b除的**余数 **

例 2

求下列给定的$a$被$b=15$除所得的不完全商和余数

$(1)a=255;(2)a=417;(3)a=-81$

• $255=15\times 17+0$所以不完全商$q=17$,余数$r=0$
• $417=15\times 27+12$所以不完全商$q=27$,余数$r=12$
• $-81=15\times (-6)+9$所以不完全商$q=-6$,余数$r=9$

例 3

利用带余除法证明：

（1） 任何两个连续整数中必定有一个是偶数；

（2） 任何三个连续整数中必定有一个是$3$的倍数；

（3） 任何四个连续整数中必定有一个是$4$的倍数；

（4） 一般地，任何$n$个连续整数中必定有一个是$n$的倍数；

• 第一题，两个连续的整数被$2$整除，得到的余数$r$只可能是$0,1$或者$1,0$由此可知两个数中有一个被$2$整除的余数是0，故得证，其余三个题是类似的，必定有一个数的余数是$0$。

例 4

证明$3\mid n(n+1)(2n+1)$,其中$n$是任意整数

• 证明：
• 因为$n$是整数，所以$n$被$3$除的余数只有三种情况$r=0,1,2$
• $r=0,n=3k$,带入得显然可以被$3$整除
• $r=1,n=3k+1$同理带入可证
• $r=2,n=3k+2$ 同理

练习 2

试证：对于任意整数$n$必有：

（1） $6\mid n(n+1)(n+2)$

（2）$12\mid n(n+1)(n+2)(n+3)$

（3）$30\mid (n^5-n)$

• 对于（1），有连续的两个整数和三个整数出现，说明其中必定有一个数可以被$2$整除，也必定有一个数能够

  被$3$整除。 所以乘起来一定可以被$6$整除，当然这是通俗的语言。

  数学语言$2\mid n(n+1)(n+2),3\mid n(n+1)(n+2),由命题5可以知道gcd(2,3)=1,所以6\mid n(n+1)(n+2)$

• 对于（2）也是同理的 ，只不过用的是命题$5$的$3$ ($gcd(3,4)=1$)

• 对于（3）,首先想到的肯定是因式分解

• $n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=(n-1)n(n+1)(n^2+1)$

• 然后我们用第一问的结果，由于$6\mid (n-1)n(n+1)$, 然后我们只需要证明 $5\mid (n^5-n)$即可

• 这个也好证，我们只需要把$n^2+1$拆成$(n+2)(n+3)-5(n+1)$即可 这样式子就变成了

• $(n-1)n(n+1)(n+2)(n+3)-5(n-1)n(n+1)(n+1)$前面那部分是连续$5$个数，一定可以被$5$整除，后面那个就不用多说了，也是一定可以被$5$整除的 于是我们就证完了

例 5

求所有的整数$n$,使得$n-1\mid n^2+3n+2$.

反过来思考，如果存在这样的$n$，那么$\frac{n^2+3n+2}{n-1}$应该是一个整数

我们令$t=n-1$带入化简得到$\frac{n^2+3n+2}{n-1}=t+5+\frac{6}{t}$ t也是整数，所以得到$\frac{6}{t}$也是整数

所以$t=\pm 1,\pm 2,\pm 3,\pm 6$ 也即 $n-1=\pm 1,\pm 2,\pm 3$ 所以$n=0,-1,-2,-5,2,3,4,7$ 这就是所要求的$n$。