Some arrangement of division and congruence theory in elementary number theory.

整除理论

记号

• $\mathbb{Z}=\{0,\pm 1,\pm 2,\cdots\}$
• $\mathbb{Q}=\{\frac{a}{b}|a,b\in \mathbb{Z}$ 且 $b\ne 0\}$
• $\mathbb{R}=\{$全体实数$\}$
• $\mathbb{C}=\{$全体复数$\}$

基础

设 $a,b\in \mathbb{Z}$,则 $a<b,a>b$ 或 $a=b$

• 若 $a<b$,则 $a\le b-1$
• 若 $a>b$,则 $a\ge b+1$

引题

观察:$1,4,9,16,25,36,49\cdots$

• 求方程 $x^2+y^2=z^2$ 的所有正整数解 $(x,y,z)$
• $\sum\limits_{i=1}^{n} i=\frac{n(n+1)}{2}=\dbinom{n+1}{2}$,是否存在无穷多正整数 $n$ 使得 $\frac{n(n+1)}{2}$ 为完全平方数？请求出是哪些 $n$?
  证明:
  令原式为 $y^2$,则 $n(n+1)=2y^2$,因此 $4n(n+1)=8y^2$
  从而 $(2n+1)^2-8y^2=1$
  即证:$x^2-8y^2=1$ 有无穷个正整数解 $(x,y)$
  理由:
• $3^2-8*1^2=1$,即 $(x,y)=(3,1)$ 是一组正整数解
• 如果 $(x_0,y_0)$ 是原方程的一组正整数解,那么 $\begin{cases}x_0^2-8y_0^2=1\\3^2-8*1^2=1\end{cases}$,因此 $(x_0^2-8y_0^2)(3^2-8*1^2)=1$
  从而 $(3x_0+8y_0+\sqrt{8}x_0+3\sqrt{8}y_0)(3x_0+8y_0-\sqrt{8}x_0-3\sqrt{8}y_0)=1$
  即有 $(3x_0+8y_0)^2-8(x_0+3y_0)^2=1$
  令 $\begin{cases}x_1=3x_0+8y_0\\y_1=x_0+3y_0\end{cases}$,则 $x_1^2-8y_1^2=1$,且 $x_1>x_0,y_1>y_0$
  即得结论成立
  注记:
• 将符合条件的正整数 $n$ 按照从小到大的顺序排列,分别记为 $a_1,a_2,\cdots$,求数列 $\{a_k\}_{k=1}^{+\infty}$

整除的定义

设 $a,b\in \mathbb{Z}$,如果存在$q\in \mathbb{Z}$,使得 $a=bq$,那么称 $b$ 整除 $a$,记为 $b\mid a$
否则,$q$ 不存在,那么称 $b$ 不整除 $a$,记为 $b\nmid a$
注记:

• 若 $b\mid a$,则称 $a$ 为 $b$ 的倍数,$b$ 为 $a$ 的约数或因子
• 若 $b\mid a$,则 $\pm b\mid \pm a$
• 若 $b\mid a$ 且 $a=0$,则 $b$ 为任意的整数,因此 $0$ 的因子为全体实数
• 用 $\tau (a)$ 表示 $a$ 所有的不同的正因子的个数

整除的基本性质

• 若 $a\mid b$,$b\mid c$,则 $a\mid c$
• 若 $a\mid b$,$a\mid c$,则 $a\mid bx+cy$

带余除法定理

设 $a,b\in \mathbb{Z}$ 且 $b>0$,那么存在唯一的 $q,r\in \mathbb{Z}$ 使得:

$a=bq+r$

其中 $0\le r<b$
注记:

• $\frac{a}{b}=q+\frac{r}{b},0\le \frac{r}{b}<1$,因此 $q=\left\lfloor\frac{a}{b}\right\rfloor$,熟知$x-1<\left\lfloor x\right\rfloor,\forall x\in \mathbb{R}$,$\frac{a-(b-1)}{b}\le \left\lfloor\frac{a}{b}\right\rfloor\le \frac{a}{b}$
• 设 $n,b$ 均为正整数,问 $1,2,\cdots,n$ 中能被 $b$ 整除的整数的个数为几个？
  解:
  不妨设 $n=bq+r,0\le r<b$
  个数即为 $q$ 个,分别为$r,2r,\cdots,qr$
• 设 $\{a_n\}$ 是给定的 $n$ 个整数,证明:$\{a_n\}$中一定存在部分数和为 $n$ 的倍数。
  证明:
  考虑一下项的和:$\sum\limits_{i=1}^{1}a_i$,$\sum\limits_{i=1}^{2}a_i$,$\sum\limits_{i=1}^{3}a_i$,$\cdots$,$\sum\limits_{i=1}^{n}a_i$
  分类讨论：
  若上述 $n$ 式中有一个值为 $n$ 的倍数,那么结论显然成立
  若上述 $n$ 式中没有一个值为 $n$ 的倍数,那么由抽屉原理,存在 $1\le i<j\le n$ 使得:
  $\sum\limits_{k=1}^{i}a_k$,$\sum\limits_{k=1}^{j}a_k$ 除以 $n$ 所得余数相同，因此有：

$n\mid \sum\limits_{k=i+1}^{j}a_k$

综上所述,结论成立

公因子和最大公因子的定义

• 设 $a,b\in \mathbb{Z}$,不全为 $0$,如果 $d\mid a$ 且 $d\mid b$,那么称 $d$ 为 $a,b$ 的一个公因子
• 设 $a,b\in \mathbb{Z}$,不全为 $0$,如果 $d$ 是 $a,b$ 的一个公因子,且 $d$ 是最大的,那么称 $d$ 为 $a,b$ 的最大公因子,记为:

$d=(a,b)$

最大公因子的性质

• $(a,0)=|a|$,$(a,1)=1$
• $(a,b)=(b,a)=(\pm a,\pm b)$
• $(a,b)=(a-b,b)$
  证明:
  令 $d=(a,b),d_1=(a-b,b)$,即证:$d=d_1$
  先证 $d\le d_1$:由于 $d=(a,b)$,那么 $d\mid a$ 且 $d\mid b$,因此 $d\mid a-b$ 且 $d\mid b$,又 $d_1=(a-b,b)$,即得 $d\le d_1$
  再证 $d\ge d_1$:由于 $d_1=(a-b,b)$,那么 $d_1\mid a-b$ 且 $d_1\mid b$,因此 $d_1\mid (a-b)+b=a$ 且 $d_1\mid b$,又 $d=(a,b)$,即得 $d\ge d_1$
  综上所述,结论成立
• 辗转相除法:$(a,b)=(a-bq,b),\forall q\in \mathbb{Z}$
  证明:
  若 $q\ge 1$,则$(a,b)=(a-b,b)=\cdots=(a-bq,b)$
  若 $q=0$,则$(a,b)=(a-bq,b)$
  若 $q\le -1$,则$(a,b)=(a+b,b)=\cdots=(a+b|q|,b)=(a-bq,b)$

Bezout 定理

设 $a,b\in \mathbb{Z}$,不全为 $0$,那么存在 $s,t\in \mathbb{Z}$ 使得:

$as+bt=(a,b)$

证明:
先构造一个集合 $S=\{ax+by|x,y\in \mathbb{Z}\}$
显然,$\pm a,\pm b \in S$,因此 $S$ 中存在正整数
不妨设 $S$ 中最小的正整数为 $d$,则 $d\in S$,从而:

$d=ax_0+by_0$

• $d\mid a$ 且 $d\mid b$
• 对任意的 $d_1\in \mathbb{Z}$,$d_1\mid a$ 且 $d_1\mid b$,由于 $d=ax_0+by_0$,那么 $d_1\mid d$
  综上所述,$(a,b)=d=ax_0+by_0$

推论

• 设 $a,b\in \mathbb{Z}$,不全为 $0$,如果 $d$ 为 $a,b$ 的一个公因子,则有:

$d\mid (a,b)$

证明:
由 Bezout 定理,有$as+bt=(a,b)$,又 $d\mid a$ 且 $d\mid b$,那么 $d\mid as+bt=(a,b)$

• 设 $a,b\in \mathbb{Z}$,不全为 $0$,那么存在 $s,t\in \mathbb{Z}$ 使得:

$as+bt=(a,b)$

因此,$\frac{a}{(a,b)}s+\frac{b}{(a,b)}t=1$,从而:

$(\frac{a}{(a,b)},\frac{b}{(a,b)})=1$

注记:

• 若 $(a,b)=1$,则称 $a,b$ 是互质或互素的
• $(a,a+1)=1$,$(2k-1,2k+1)=1$,$(2^a,2k+1)=1$

整除的高级性质

• 若 $(a,b)=1$,且 $a\mid bc$,则有 $a\mid c$
  证明:
  由于 $(a,b)=1$,由 Bezout 定理,有 $as+bt=1$
  在上式的两边同时乘上 $c$,有 $acs+bct=c$
  又 $a\mid bc$,$a\mid a$,那么 $a\mid acs+bct$,从而 $a\mid c$
• 如果 $(a,b)=1$,且 $a\mid c$,$b\mid c$,则$ab\mid c$
  证明:
  由于 $(a,b)=1$,那么存在 $s,t\in \mathbb{Z}$ 使得 $as+bt=1$
  在上式的两边同时乘上 $c$,有 $acs+bct=c$
  又 $a\mid c$,则 $ab\mid bc$,又 $b\mid c$,则 $ab\mid ac$,因此 $ab\mid abs+cbt$,从而 $ab\mid c$

最大公因子的高级性质

• 若 $(a,b)=1$,则 $(a,bc)=(a,c)$
  证明:
  令 $d=(a,bc),d_1=(a,c)$,即证 $d=d_1$
  先证 $d\mid d_1$:由于 $d_1=(a,c)$,那么 $d_1\mid a$ 且 $d_1\mid c$,又 $c\mid bc$,那么 $d_1\mid bc$ 且 $d_1\mid a$,又 $d=(a,bc)$,即得 $d_1\mid d$
  再证 $d_1\mid d$:由于 $d=(a,bc)$,则 $d\mid a$ 且 $d\mid bc$,又 $(a,b)=1$,由 Bezout 定理,有 $as+bt=1$,因此 $acs+bct=c$,从而 $d\mid c$,又 $d\mid a$ 且 $d_1=(a,c)$,即得 $d_1\mid d$
  综上所述,结论成立
• 令 $d=(ab,c),d_1=(a,c),d_2=(b,c)$,则 $d=d_1d_2$
  证明:
  先证:$d\mid d_1d_2$:由 Bezout 定理,有 $\begin{cases}as_1+ct_1=d_1\\bs_2+ct_2=d_2\end{cases}$
  因此 $d_1d_2=(as_1+ct_1)(bs_2+ct_2)$,从而 $abs_1s_2+c(as_1t_2+bs_2t_1+ct_1t_2)$
  又 $d=(ab,c)$,则 $d\mid ab$ 且 $d\mid c$,从而 $d\mid d_1d_2$
  再证:$d_1d_2\mid d$:由于 $(a,b)=1$,由 Bezout 定理,有 $as+bt=1$,从而 $acs+cbt=c$
  由于 $d_1=(a,c)$,$d_2=(b,c)$,那么 $d_1\mid a$ 且 $d_1\mid c$,$d_2\mid b$ 且 $d_2\mid c$
  因此 $d_1d_2\mid ab$,$d_1d_2\mid ac$,$d_1d_2\mid bc$
  又 $d=(ab,c)$,即得 $d_1d_2\mid d$
  综上所述,结论成立

素数与合数

• 设正整数 $n>1$,如果 $n$ 的所有不同正因子恰好为 $1$ 和它本身,那么称 $n$ 为素数(Euclid 定理:素数有无穷多个)
• 设正整数 $n>1$,如果 $n$ 不是素数,那么称 $n$ 为合数
• 任意正整数 $n$,存在连续的几个正整数均为合数
  解:
  $(n+1)!+2,(n+1)!+3,\cdots,(n+1)!+(n+1)$
• 任意正整数 $n$,存在连续的几个正整数均为合数,且每一个正整数均不能写成两个整数的平方和
  猜想:
  存在无穷个正整数 $n$,使得 $n!+1$ 为素数
• 存在无穷个正整数 $n$,使得 $n!+1$ 为合数

素数的性质

• 设 $p$ 为素数,$a\in \mathbb{Z}$,则 $(a,p)=1$ 或 $p\mid a$
  证明:
  令 $d=(a,p)$,则 $d\mid a$ 且 $d\mid p$,因此 $d=1$ 或 $p$
  若 $d=1$,那么 $(a,p)=1$,结论成立
  若 $d=p$,那么 $p\mid a$,结论成立
  综上所述,结论成立
• 设 $p$ 为素数且 $p\mid ab$,$a,b\in \mathbb{Z}$,则 $p\mid a$ 或 $p\mid b$
  证明:
  分类讨论:
  若 $p\mid a$,则结论显然成立
  若 $p\nmid a$,那么 $(a,p)=1$,又 $p\mid ab$,因此 $p\mid b$,结论成立
  综上所述,结论成立

算术基本定理

设正整数 $n>1$,那么 $n$ 可以写成有限个素数之积,如果不考虑乘积的顺序,则这种分解就是唯一的,即:

$n=p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_t^{\alpha_t}$

其中 $p_1<p_2<p_3<\cdots<p_t$,$\alpha_i\ge 1,i=1,2,\cdots,t$

• 令 $S_k(n)=\sum\limits_{i=1}^{n}i^k$
  显然$\begin{cases}S_1(n)=\sum\limits_{i=1}^{n}i=\frac{n(n+1)}{2}\\S_2(n)=\sum\limits_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}\\S_3(n)=\sum\limits_{i=1}^{n}i^3=(\frac{n(n+1)}{2})^2\end{cases}$
  观察:$S_k(1),S_k(2),\cdots,S_k(n),\cdots$
  一般情况,计算 $S_k(n)$ 的值
  解:
  $(x+1)^{k+1}-x^{k+1}=\sum\limits_{i=0}^{k}x^i\dbinom{k+1}{i}$
  因此,$(n+1)^{k+1}-1=\sum\limits_{i=1}^{k}S_i(n)\dbinom{k+1}{i}+n$
• 证明$641\mid 2^{32}+1$
  证明:
  $RHS=2^{32}+1=4294967297$
  因此,$641\mid 2^{32}+1$
  注记:
• 称该式为 $n$ 的标准分解式
• 推论:设 $n$ 为正整数,则有 $n=2^ab$,其中 $2\nmid b$,$a>0$

同余理论

同余的定义

设 $m$ 为正整数,$a,b\in \mathbb{Z}$,如果 $m\mid a-b$,那么称 $a$ 同余 $b$ 模 $m$,记为

$a\equiv b\pmod{m}$

否则,若 $m\nmid a-b$,那么称 $a$ 不同余 $b$ 模 $m$,记为

$a\not\equiv b\pmod{m}$

注记:
$a\equiv b\pmod{m}\iff m\mid a-b\iff a=b+mq,\exists q\in \mathbb{Z}$

• 设 $a\in \mathbb{Z}$,则 $a^2\equiv 0,1\pmod{4}$
  特别地,若 $2\nmid a$,则 $a^2\equiv 1\pmod{8}$
  证明:
  若 $a=2k$,那么 $a^2=(2k)^2=4k^2\equiv 0\pmod{4}$
  若 $a=2k+1$,那么 $a^2=(2k+1)^2=4k^2+4k+1=4k(k+1)+1\equiv 1\pmod{8}$
  综上所述,结论成立
• 对每个正整数 $n$,均有 $\left\lfloor\sqrt{n}+\sqrt{n+1}\right\rfloor=\left\lfloor\sqrt{n}+\sqrt{n+2}\right\rfloor$
  分析:

$\left\lfloor x\right\rfloor$的性质

$x=\left\lfloor x\right\rfloor+\{x\}$,其中 $\left\lfloor x\right\rfloor\in \mathbb{Z}$,$0\le\{x\}<1$
$x-1<\left\lfloor x\right\rfloor\le x<\left\lfloor x\right\rfloor+1$
$\left\lfloor x+n\right\rfloor=\left\lfloor x\right\rfloor +n$,$x\in \mathbb{R}$,$n\in \mathbb{Z}$
$\{x+n\}=\{x\}$,$\forall n\in \mathbb{Z}$
$\left\lfloor x\right\rfloor+\left\lfloor y\right\rfloor\le \left\lfloor x+y\right\rfloor\le \left\lfloor x\right\rfloor+\left\lfloor y\right\rfloor+1$
$\left\lfloor {-x}\right\rfloor=\begin{cases}{-\left\lfloor -x\right\rfloor,x\in \mathbb{Z}}\\{\left\lfloor -x\right\rfloor+1,x\notin \mathbb{Z}}\end{cases}$

回到原题

反证法,如果结论不对,那么存在正整数 $n$,使得 $\left\lfloor\sqrt{n}+\sqrt{n+1}\right\rfloor\ne\left\lfloor\sqrt{n}+\sqrt{n+2}\right\rfloor$
因此,$\left\lfloor\sqrt{n}+\sqrt{n+1}\right\rfloor<\left\lfloor\sqrt{n}+\sqrt{n+2}\right\rfloor$
令 $k=\left\lfloor\sqrt{n}+\sqrt{n+2}\right\rfloor$,则 $\left\lfloor\sqrt{n}+\sqrt{n+1}\right\rfloor<k\le\left\lfloor\sqrt{n}+\sqrt{n+2}\right\rfloor$
因此,$(\left\lfloor\sqrt{n}+\sqrt{n+1}\right\rfloor)^2<k^2\le(\left\lfloor\sqrt{n}+\sqrt{n+2}\right\rfloor)^2$
从而,$2n+1+2\sqrt{n^2+n}<k^2\le 2n+2+2\sqrt{n^2+2n}$,$2n+1+2\sqrt{n^2}<k^2\le 2n+2+2\sqrt{n^2+2n+1}$
因此,$4n+1<k^2<4n+4$
从而,$k^2=4k+2$ 或 $4k+3$,$k^2\equiv 0$ 或 $1\pmod{4}$,矛盾
综上所述,结论成立

同余的基本性质

• $a\equiv a\pmod{m}$,反身性
• 若 $a\equiv b\pmod{m}$,则 $b\equiv a\pmod{m}$,对称性
• 若 $a\equiv b\pmod{m}$,$b\equiv c\pmod{m}$,则 $a\equiv c\pmod{m}$,传递性
  注记:
  若 $a_1\equiv a_2\pmod{m},a_2\equiv a_3\pmod{m},\cdots,a_{t-1}\equiv a_t\pmod{m}$,则:$a_1\equiv a_2\equiv a_3\cdots\equiv a_t\pmod{m}$

同余的性质

• 若 $a\equiv b\pmod{m}$,$c\equiv d\pmod{m}$,那么:

$a+c\equiv b+d\pmod{m}$

$a-c\equiv b-d\pmod{m}$

$ac\equiv bd\pmod{m}$

• 若 $ab\equiv ac\pmod{m}$,则 $b\equiv c\pmod{\frac{m}{(a,m)}}$

同余的高级性质

• 若 $a_1\equiv b_1\pmod{m},a_2\equiv b_2\pmod{m},\cdots,a_t\equiv b_t\pmod{m},t\ge 2$,则:

$\sum\limits_{i=1}^{t}a_i\equiv\sum\limits_{i=1}^{t}b_i\pmod{m}$

$\prod\limits_{i=1}^{t}a_i\equiv\prod\limits_{i=1}^{t}b_i\pmod{m}$

• 若 $a\equiv b\pmod{m}$,则:

$a^t\equiv b^t\pmod{m},\forall t\in \mathbb{Z}\ge 1$

• 设 $f(x)=\sum\limits_{i=0}^{n}a_ix^i\in \mathbb{Z}\left\lfloor x\right\rfloor$ 且 $a_n\ne 0$,若 $a\equiv b\pmod{m}$,那么:

$f(a)\equiv f(b)\pmod{m}$

• 设 $a,b,c$ 均为正整数,在以下的三个数中至少有一个不是平方数:$a^2bc+2$,$b^2ac+2$,$c^2ab+1$
  证明:
  反证法,假如结论不对,那么三个数均为平方数,不妨设 $\begin{cases}a^2bc+2=x^2\\b^2ac+2=y^2\\c^2ab+2=z^2\end{cases}$
  分类讨论:
  若 $a,b,c$ 中有偶数,不妨设 $2\mid a$,那么 $x^2=a^2bc+2\equiv 2\pmod{4}$,矛盾
  若 $a,b,c$ 均为奇数,则 $a,b,c\equiv \pm1\pmod{4}$,由抽屉原理,存在两数模 $4$ 同余,不妨设 $a\equiv b\pmod{4}$,则 $ab\equiv 1\pmod{4}$,矛盾
  综上所述,结论成立

Fermat 小定理

设 $p$ 为素数,$a\in \mathbb{Z}$ 且 $(a,p)=1$,则 $a^{p-1}\equiv 1\pmod{p}$
证明:
考虑以下的 $p-1$ 个数,$1,2,\cdots,p-1$
将这 $p-1$ 个数均乘 $a$,得 $a,2a,\cdots,a(p-1)$
该式中的数均不是 $p$ 的倍数,而且这 $p-1$ 个数模 $p$ 互不同余,理由如下:
若 $ai\equiv aj\pmod{p}$,其中 $1\le i,j\le p-1$,因为 $(a,p)=1$,所以 $i\equiv j\pmod{p}$,即得 $p\mid i-j$
又 $-(p-2)=1-(p-1)\le i-j\le (p-1)-1=p-2$,即 $|i-j|\le p-2$,因此 $i-j=0$,即 $i=j$
不妨设 $ai$ 除以 $p$ 的余数为 $r_i$,那么 $1\le r_i\le p-1$,因此 $ai\equiv r_i\pmod{p},i=1,2,\cdots,p-1$
因此,$a^{p-1}(p-1)!\equiv \prod\limits_{i=1}^{p-1}r_i\pmod{p}$
又因为 $(p-1)!\equiv \prod\limits_{i=1}^{p-1}r_i\pmod{p}$
所以 $(p,(p-1)!)=1$,那么:

$a^{p-1}\equiv 1\pmod{p}$

注记:

• 设 $p$ 为素数,$a\in \mathbb{Z}$ 且 $(a,p)=1$,则 $a^{p-1}\equiv 1\pmod{p}$
• 设 $p$ 为素数,$a\in \mathbb{Z}$,则$a^p\equiv a\pmod{p}$
• 设 $p$ 为素数,$a\in \mathbb{Z}$,则 $a^{p-1}\equiv 0,1\pmod{p}$