本文最后更新于:2020年10月8日 早上

反证法在数论中的运用

这边的反证法包含狭义的反证法和广义的一切导出矛盾包括判断无解的方法

  • 方案 1 证明有素因子考虑没有素因子。
  • 方案 2 探究多项式的根中(尤其在数论中模 $p$ 意义下)不相等根的个数大于多项式的次数。
  • 方案 3 假设某个数的需要区间不成立。
  • 方案 4 引入两符号 $a,b$ 使得 $a,b$ 互素,导出 $(a,b)>1$。
  • 方案 5 引入符号 $S$ 为需要数值的极值,证明有比 $S$ 更大或更小的数。
  • 方案 6 有理数等于无理数。
  • 方案 7 其他逻辑矛盾或违反题意的情况。

多项式在数论中的应用

  • 应用 1方案 2
  • 应用 2 证明合数时运用因式分解。
  • 应用 3 构造勾股方程利用通解公式解题。
  • 应用 4 利用多项式化特殊为一般,提供解题的启发或直接获得答案。
  • 应用 5 其他巧妙的多项式运用。

组合数在数论题目中的策略

  • 策略 1 组合数公式:$kC^k_n=nC^{k-1}_{n-1}$。
  • 策略 2 组合数利用二项式定理化为二项式。

注:二项式定理即为:$(x+y)^n=\sum\limits^n_{k=0}C^n_kx^{n-k}y^k$。由于对称性,也有:$(x+y)^n=\sum\limits^n_{k=0}C^n_kx^{k}y^{n-k}$。

一些有关数论的定理

费马小定理 若 $p$ 为素数,$a$ 为整数,则 $a^p\equiv a\pmod{p}$;若 $p\nmid a$,则 $a^{p-1}\equiv1\pmod{p}$。

欧拉定理 $\forall a,m\in \mathbb{N^*},((a,m)=1),m≥2, a^{\varphi(m)}\equiv1\pmod{m}$。

注:当 $m$ 为素数的时候,即为费马小定理。

题目分析

第 1 题

设 $p$ 是素数,且满足 $p^2\mid2^{p-1}-1$,证明 $\forall n\in\mathbb{N^*}$,$(p-1)(p!+2^n)$ 至少有 $3$ 个不同的素因数。

$2^{p-1}$ 为偶数,所以 $p$ 是一个奇素数。于是 $p-1$ 为偶数,所以 $(p-1)(p!+2^n)$ 必有素因数 $2$。

不妨设剩下的两个素因数分别在 $(p-1)(p!+2^n)$ 的两个因式中。

下面证明 $p-1$ 有不同于 $2$ 的素因数。

利用方案 1,假设 $p-1$ 没有不同于 $2$ 的素因数,不妨设 $p-1=2^k(k\in\mathbb{N})$,于是 $p=2^k+1$。

下面考虑 $k$ 的奇偶性。

如果 $k$ 有 $>1$ 的奇因数 $b$,不妨设 $k=bc$,于是 $p=(2^c)^b+1=(2^c+1)(2^{c-1}-2^{c-2}+2^{c-3}-\cdots+1)$ 而 $2^c+1$ 和 $2^{c-1}-2^{c-2}+2^{c-3}-\cdots+1$ 都是正数,因此 $p$ 是合数,由方案 7,与 $p$ 为素数矛盾。于是 $k$ 没有 $>1$ 的奇因数。

则设 $k=2^t(t\in\mathbb{N})$,于是 $p^2 \mid2^t-1$,$p^2\mid(2^{2^t}+1)(2^{2^t}-1)$。则 $\forall l>t,(2^{2^l}+1,2^{2^t}+1)=1$,于是 $p\mid2^{p-1}-1$,矛盾。于是 $p-1$ 有不同于 $2$ 的素因数。

下面证明 $(p!+2^n)$ 有不同于 $2$ 的素因数。

仍然利用方案 1,假设 $(p!+2^n)$ 没有不同于 $2$ 的素因数,不妨设 $(p!+2^n)=2^k(k>n)$。

如果设 $k-n=m$,则 $p!=2^m(2^m-1)$。注意到 $2,p$ 互素,由费马小定理得 $2^{p-1}\equiv 1\pmod{p}$。

设 $2$ 模 $p$ 的阶为 $t$。因此 $t\mid m,p-1$。不妨设 $p-1=lt(l\nmid p)$。

$\because p^2\mid2^{p-1}-1$,则有 $p^2\mid2^n(2^m-1)=p!$,矛盾。

于是 $(p!+2^n)$ 有不同于 $2$ 的素因数。

于是 $(p-1)(p!+2^n)$ 至少有 $3$ 个不同的素因数。$\boxed{\mathbb{Q.E.D}}$。

第 5 题

求 $2^{561}-2,3^{561}-3,\cdots,561^{561}-1$ 的最大公因数。

考虑 $2^n-2,3^n-3,\cdots,n^n-n$。设 $d=(2^n-2,3^n-3,\cdots,n^n-n)$。

首先证明一个引理:素数 $p \mid d$ 的充分必要条件是 $p-1\mid n-1$。

先证 $p\mid d \implies p-1\mid n-1$。

设素数 $p\mid d$,于是 $p\mid i^n-i(i=1,2,\cdots,n)$。

根据方案 3,若 $p>n$ 则 $p\mid i(i^{n-1}-1)$,又 $i<n$,于是 $p\mid i^{n-1}-1$。

根据方案 2,多项式 $x^{n-1}-1$ 在模 $p$ 的意义下有 $n$ 个不同的根 $1,2,\cdots,n$。而由代数基本定理得多项式恰有 $n-1$ 的根,矛盾。于是 $p\leq n$。一样可以得到 $p\mid i^{n-1}-1$。

对于 $i=1,2,\cdots,p-1$,由于 $i,p$ 互素,由费马小定理得 $i^{p-1}\equiv 1\pmod{p}$,所以 $i^{p-1}-1\equiv 0\pmod{p}$。于是 $p-1\mid n-1$。

再证 $p\mid d \impliedby p-1\mid n-1$。

若 $p\mid a,a\in [2,n]$,则 $p\mid a^n-a$,结论显然成立;

反之,若 $p \nmid a$,因为 $p$ 为素数,所以 $p,a$ 互素。则由费马小定理得 $a^{p-1}-1\equiv 0\pmod{p}$。

由于 $p-1\mid n-1$,因此 $p\mid a^{n-1}-1$,则 $p\mid a^n-a$,于是 $p\mid d$。

因此由引理得 $d=\prod\limits_{p 是素数且p-1\mid n-1} p$。则当 $n=561$ 时,答案即为 $\boxed{2\times3\times5\times11\times17\times29\times41\times71\times113\times281}$。

第 9 题

证明 $\forall k\in \mathbb{N^*},(k^2)!\prod\limits^{k-1}_{j=0}\dfrac{j!}{(j+k)!}$ 是整数。

$$
\begin{align}
\texttt{注意到} & (k^2)!\prod\limits^{k-1}{j=0}\dfrac{j!}{(j+k)!}\texttt{是整数}\
&{\iff \forall p\texttt{为素数},\sum\limits
{i=1}^{+\infty}\left[\dfrac{k^2}{pi}\right]+\sum\limits^{+\infty }{i=1}\sum\limits^{k-1}{j=0}\left[\dfrac{j}{pi}\right]≥\sum\limits^{+\infty }{i=1}\sum\limits^{k-1}{j=0}\left[\dfrac{j+1}{pi}\right]\
\iff \sum\limits^{+\infty}{i=1}\left(\left[\dfrac{k^2}{pi}\right]+\sum\limits^{k-1}{j=0}\left[\dfrac{j}{pi}\right]\right)≥\sum\limits^{+\infty}{i=1}\sum\limits^{k-1}{j=0}\left[\dfrac{j+k}{pi}\right]\
\iff \forall i\in\mathbb{N^},\left[\dfrac{k^2}{pi}\right]+\sum\limits^{k-1}{j=0}\left[\dfrac{j}{pi}\right]≥\sum\limits^{k-1}{j=0}\left[\dfrac{j+k}{pi}\right]\\iff \forall i\in\mathbb{N^},\left[\dfrac{k^2}{pi}\right]+\sum\limits^{k-1}{j=0}\left[\dfrac{j}{pi}\right]>\sum\limits^{k-1}{j=0}\left[\dfrac{j+k}{pi}\right]-1\
\iff \forall i\in\mathbb{N^},\dfrac{k^2}{pi}-\left{\dfrac{k^2}{pi}\right}+\sum\limits^{k-1}{j=0}\left(\dfrac{j}{pi}-\left{\dfrac{j}{pi}\right}\right)>\sum\limits^{k-1}{j=0}\left(\dfrac{j+k}{pi}-\left{\dfrac{j+k}{pi}\right}\right)-1\
\iff \forall i\in\mathbb{N^
},\sum\limits^{k-1}{j=0}\dfrac{k}{pi}+\sum\limits^{k-1}{j=0}\dfrac{j}{pi}+\sum\limits^{k-1}{j=0}\left{\dfrac{j+k}{pi}\right}+1>\sum\limits^{k-1}{j=0}\dfrac{j+k}{pi}+\left{\dfrac{k^2}{pi}\right}+\sum\limits^{k-1}{j=0}\left{\dfrac{j}{pi}\right}\
\iff \forall i\in\mathbb{N^*},\sum\limits^{k-1}
{j=0} \left{\dfrac{j+k}{pi}\right}+1>\sum\limits^{k-1}_{j=0} \left{\dfrac{j}{pi}\right}+\left{\dfrac{k^2}{pi}\right}.}
\end{align}
$$

而注意到

$$
1>\left{ \dfrac{k^2}{pi} \right},\sum\limits^{k-1}{j=0} \left{\dfrac{j+k}{pi}\right} > \sum\limits^{k-1}{j=0} \left{ \dfrac{j}{pi} \right}.
$$

两式相加即为上式。$\boxed{\mathbb{Q.E.D}}$。

第 11 题

求所有正整数对 $(m,n)$,使得 $m,n+1$ 互素,且 $\sum\limits^n_{k=1}\dfrac{m^{k+1}}{k+1}C^k_n$ 为整数。

注意到策略 1

$$
\begin{align}
& \sum\limits^n_{k=1} \dfrac{m^{k+1}}{k+1}C^k_n,\
=& \sum\limits^n_{k=1} \dfrac{C^{k+1}{n+1}}{n+1}m^{k+1},\
=& \dfrac{1}{n+1}\sum\limits^{n+1}
{i=2} C^i_{n+1}m^i,\
=& \dfrac{1}{n+1}\sum\limits^{n+1}{i=0} C^i{n+1}m^i-C^1_{n+1}m-1,\
=& \dfrac{1}{n+1}\left[(m+1)^{n+1}-(n+1)m-1\right].
\end{align}
$$

于是

$$
n+1\mid (m+1)^{n+1}-1.
$$

若 $m$ 为奇数,则 $(m+1)^{n+1}-1$ 也是奇数,于是 $n+1$ 是奇数。

若 $m$ 为偶数,则由 $m$ 和 $n+1$ 互素得 $n+1$ 为奇数。

因此,无论 $m$ 的奇偶性,$n+1$ 均为奇数。

设 $p$ 是 $n+1$ 的最小素因数,于是

$$
(m+1)^{n-1}\equiv 1\pmod{p}.
$$

由于 $m+1$ 与 $p$ 互素,则有费马小定理

$$
(m+1)^{p-1}\equiv 1\pmod{p}.
$$

设 $d=(n-1,p-1)$,于是 $d=1$。

因此

$$
(m+1)^d\equiv 1\pmod{p}.
$$

于是

$$
m\equiv 0\pmod{p}.
$$

所以

$$
p\mid (m,n+1).
$$

方案 7,矛盾。

因此,满足条件的 $m,n$ 不存在。$\boxed{\mathbb{Q.E.D}}$。

第 13 题

证明 $\sum\limits^{504}{k=1} (-1)^k C^k{2017}\equiv 3(2^{2016}-1)\pmod{2017^2}$。

设 $p=2017$,则 $p$ 为素数。则由策略 1 得:$kC^k_p=pC^{k-1}_{p-1}$。

所以

$$
C^k_p=\dfrac{p}{k}C^{k-1}_{p-1}=\dfrac{p}{k}(-1)^{k-1}\pmod{p^2}.
$$

$$
\tag{1} C^k_{2017}=(-1)^{k-1}\dfrac{2017}{k}\pmod{2017^2}.
$$

$$
\tag{2}\dfrac{C^k_{2017}}{2017}=\dfrac{(-1)^{k-1}}{k}\pmod{2017}.
$$

于是

$$
\sum\limits^{504}{k=1} (-1)^kC^k{2017}\stackrel{(1)}{=}
\sum\limits^{504}{k=1} (-1)^k(-1)^{k-1}\dfrac{2017}{k}=
-2017\sum\limits^{504}
{k=1} \dfrac{1}{k}\pmod{2017^2}.
$$

设 $S_n=\sum\limits^n_{k=1}\dfrac{1}{k}$,则

$$
S_{2n}-S_n=\sum\limits^{2n}_{k=1}(-1)^{k-1}\dfrac{1}{k}.
$$

$$
S_{504}=S_{1008}-\sum\limits^{1008}{k=1} (-1)^{k-1}\dfrac{1}{k}=
S
{2016}-\sum\limits^{2016}{k=1} (-1)^{k-1}\dfrac{1}{k}-\sum\limits^{1008}{k=1} (-1)^{k-1}\dfrac{1}{k}.
$$

$$
S_{2016}=\dfrac{1}{2}\sum\limits^{2016}{k=1}\left(\dfrac{1}{k}+\dfrac{1}{2017-k}\right)=\dfrac{2017}{2}\sum\limits^{2016}{k=1}\dfrac{1}{k(2017-k)}=0\pmod{2017}.
$$

$$
S_{504}=-\sum\limits^{2016}{k=1}(-1)^{k-1}\dfrac{1}{k}-\sum\limits^{1008}{k=1}(-1)^{k-1}\dfrac{1}{k}\pmod{2017}.
$$

所以

$$
\begin{align}
\sum\limits^{504}{k=1} (-1)^k C^k{2017} &=-2017\left(-\sum\limits^{2016}{k=1}(-1)^{k-1}\dfrac{1}{k}-\sum\limits^{1008}{k=1}(-1)^{k-1}\dfrac{1}{k}\right)\
&\stackrel{\texttt{要证}}{=}3(2^{2016}-1)\pmod{2017^2},\
&\iff\sum\limits^{2016}{k=1}(-1)^{k-1}\dfrac{1}{k}+\sum\limits^{1008}{k=1}(-1)^{k-1}\dfrac{1}{k}=\dfrac{3(2^{2016}-1)}{2017}\pmod{2017}.
\end{align}
$$

注意到

$$
\begin{align}
\sum\limits^{2016}{k=1}(-1)^{k-1}\dfrac{1}{k}+\sum\limits^{1008}{k=1}(-1)^{k-1}\dfrac{1}{k}&\stackrel{(2)}{=}\sum\limits^{2016}{k=1}\dfrac{C^k{2017}}{2017}+\sum\limits^{1008}{k=1}\dfrac{C^k{2017}}{2017}\
&=\dfrac{1}{2017}\left(\sum\limits^{2016}{k=1}C^k{2017}+\sum\limits^{1008}{k=1}C^k{2017}\right)\
&=\dfrac{3}{2\times 2017}\sum\limits^{2016}{k=1}C^k{2017}\
&\stackrel{\texttt{策略 2}}{=}\dfrac{3}{2\times 2017}[(1+1)^{2017}-1-1]=\dfrac{3(2^{2016}-1)}{2017}\pmod{2017}.
\end{align}
$$

上面用到了策略 2

于是

$$
\sum\limits^{504}{k=1} (-1)^k C^k{2017}\equiv 3(2^{2016}-1)\pmod{2017^2}.
$$

$\boxed{\mathbb{Q.E.D}}$。

第 18 题

记 $\alpha$ 为方程 $x^2+x=5$ 的正根,正整数 $n$ 及非负整数 $c_0,c_1,\cdots,c_n$ 满足 $\sum\limits^n_{k=0}c_k\alpha^k=2015$。证明 $\sum\limits^n_{k=0}c_k\equiv2\pmod{3}$。

设 $f(x)=\sum\limits^n_{k=0}c_kx^k-2015=(x^2+x-5)g(x)+h(x)$。

其中 $h(x)=ax+b$,$g(x),h(x)$ 均为整系数多项式。

由于 $\alpha$ 是方程的根,于是 $a\alpha+b=0$。由于 $\alpha$ 为无理数,则 $a=b=0$。

于是
$$
f(x) =(x^2+x-5)g(x).
$$
因此
$$
\begin{align}
\sum\limits^n_{k=0}c_k &=f(1)+2015\
&=-3g(1)+2015\
&=2\pmod{3}.
\end{align}
$$
上面通过一些题目具体说明了反证法、多项式、组合数和有关数论的定理在数论中综合的运用。下面总结一些思想。

数论中常用的思想

  1. 化归 在数论题目的证明中,尽可能的使用已经被证明的等式或引理。
  2. 反证法 反证法在数论题目中很常见。主要是因为有的数论题目给出的条件确实比较少,而使用反证法数论本身的特点能为反证法提供许多矛盾,这就相辅相成了。
  3. 转化法 通过等价变换将需要求证的转化为容易证得的或一些显然的结论。
  4. 引入素数 在证明某些式子中学会去引入恰当的素数,则能通过一些方法将引入的素数从本身的「题目复杂化」到「题目简单化」。一般来讲,引入的素数可以是某一般的式子的最大公约数等等。
  5. 先寻找一般的结论 先寻找一般的结论,后代入。一般的结论更容易发现一些结论。
  6. 确定素数的范围 可以确定奇偶性,所在区间(用反证法),然后利用性质解题。
  7. 运用阶 根据阶的特点(这里费马小定理的使用导出阶非常常见)获得整除或最大公因数为阶。

其他方法

同一法 满足同一法则的命题若为真命题则其逆命题也为真命题。

同一法则:如果一个命题的题设和结论都是唯一的事项


本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

CF1405A 题解 上一篇
皮亚诺公理简介 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。