首页 > 其他 > 详细

[05/06/20] 数论学习笔记

时间:2020-05-06 16:03:33      阅读:73      评论:0      收藏:0      [点我收藏+]

SS1

  1.数论问题在 \(\mathbb Z\) 上进行研究。

    公约:

    1.\((a,b)\) 表示 \(a,b\) 最大公因数,\([a,b]\) 为最小公倍数.

    2.\(<<<\) 表示远小于,\(>>>\) 表示远大于.

    3.形如 \(a|b\) 的式子被称为整除式.

    4.多行圆括号表示解答过程(优先级最高),单箭头表示分析过程,书写时一般逆写.

    5.下列整数基本性质由题目给出,非其最基本性质.

    整数基本性质(\(a,b\in\mathbb Z\)):

    1.\(\mathbb Z\) 为一个数环,即以下性质 \(3.\)

    2.\(a>b\iff a\geq b+1\iff a-1\geq b\iff a=b+k(k>0).\)

    3.\(c=a+b\in\mathbb Z,d=a-b\in\mathbb Z,e=a*b\in\mathbb Z,f=\frac ab\in Z(b\not=0).\)

    4.\(a|b\iff b=ka(k\not=0,k\in \mathbb Z).\)

    5.使 \(f(a)|g(a)\) 成立的 \(a\) 的全体组成的集合 \(A_1\) 与使 \(f(a)|g(a)-kf(a)\) \((k\in \mathbb Z)\) 成立的 \(a\)

    的全体组成的集合 \(A_2\) 相等.

    6.设集合 \(A=\{P(a)|a\in\mathbb Z\}\)\(B={Q(a)|a\in\mathbb Z}\),命题 \(P1=\) 使整除式 \(P(a)|P(b)\) 成立

    的 \(a\) 的全体组成的集合 \(S\) 为无限集,命题 \(P2=A\subseteq B\),有 \(P1=P2.\)

    7.性质 \(5\) 上经常使用性质 \(f(a)*f(b)=0\iff f(\varepsilon)=0(\varepsilon\in(a,b)).\)

    8.设有整除式 \(a|b\) ,使 \((k-1)a<|b|<ka\) 恒成立的 \(a\) 使整除式不成立.

    特点:离散,无限

    核心:无限 \(\to\) 有限。

      操作方式:整除,同余,估计。

        同余:$Z \to $ 同余类(给集合做划分)(提取代表元)

        \(S_{1,1}\)\(\begin{cases}构造(反面)\\ 论证(抽屉) \end{cases} \to 同余系\) (解析略)

          同余;

        放缩:确定某多项式与 其加上(或减去)某不为零的多项式后 的大小关系。

        \(S_{1,2}\):存在性 \(\to\) 构造 \(\to\) 选取 \(i,j\) \(\to\) 希望 \(\begin{cases}a_i+a_j \uparrow\\ (a_i,a_j)\downarrow\end{cases}\) \(\to\) 希望 \((a_i,a_j)=1\)

        \(\to\) (互质问题不可回避) \(\to\) (不互质 \(\to\) 互质) (结论一)

        考虑互质情况,则需证 \(a_i+a_j\geq 2n-1=p\) \(\to\) \(p|a_i+a_j\) \(\to\) 例一 (结论二)

        对于结论二分类:\(\begin{cases}若有? p|a_i,取 p\not| a_j,易证;\\若有?p\not|a_i,取剩余系(非完系)两两分组,易证;\end{cases}\)

        对于结论一分类:\(\begin{cases}若有? p|a_i+a_j,有\frac{a_i}{(a_i,a_j)}\geq p,易证;\\若有? p|a_i-a_j,由a_i-a_j<a_i+a_j,易证;\end{cases}\)

          同余;构造;放缩;

        估计\(\begin{cases}a|b\\b\not=0\end{cases} \to |b|\geq a\) \(\to\) 有界离散 \(\to\) 有限解 \(\to\) 高次小于低次(多项式) \(\to\)

        放缩(即估计当变量取何值时某式恒成立)

        分离:考虑 \(f_1(a^m)|f_2(a^n)\)\(a^k\) 表示最高次项),作 \(m=n+k\) ,

        令 \(f_1(a^m)=f_3(a^n)*f_4(a^k)\)\(f_2(a^n)*f_5(a^k)=f_6(a^m)\) (常用)

        然后计算 \(f_3\)\(f_2\)\(f_6\)\(f_1\)

        无穷递降:通过 \(m\) \(\to\) \(m‘\),常以 \(m,m‘\) 为根韦达构造(或解关于 \(m\) 的)二次方程

        以保证具有相同性质\(P\),且 \(m,m‘\) 地位相等,可论证 \(m‘\) 为常数或推导出矛盾。

        \(S_{1,3}\)\(\begin{cases}是\to 构造\\否\to 反证\to 优先选择,各个角度分类筛不符合条件\end{cases}\to\begin{cases}存在(构造域)\\不存在(证毕)\end{cases}\)

        \(\to\) 常规方法:无穷递降,取最小,证存在更小(由当前最小的推出) \(\to\) 做减法

        放缩,设 \(?a>10a_m>10^m\) \(\to\) 构造 \(b\) ,使:\(\begin{cases}b=a-ka_m\\a-ka_m 无退位\end{cases}\)

        注意到 \(9a_m+1=10^m\),并有 \(a\) 首位必不为零 \(\to\)\(a\) 做位值拆分。

        设函数 \(S(x)\)\(x\) 各位数之和,分析进位有 \(S(a-10^r+10^{r-m})\) 严格小于 \(S(a)\).

          无穷递降;估计;

        \(S_{1,4}\)\(\begin{cases}m=n,k=m^2;\\m\not=n,m≡n(2); \end{cases}\)

        \(k\) 为完方,分子为完方 \(\to\) 分母为完方 \(\to\) 分母简化 \(\to\) \(m,n\) 换元 \(m+n,m-n\)

        设 \(m=n+2t(t\not=0)\),有 \(k=\frac{(m-t)^2}{4mt^2+1}\)\(4mt^2k+k=m^2-2mt+t^2\)

        整理成关于 \(m\) 的一个一元二次方程,有两根 \(m,m‘\) 地位相等,且均满足条件

        \(m^2-(4kt^2+2t)m+t^2-k=0\),韦达得 \(m+m‘=2t+4kt^2\in \mathbb Z\)

        有 \(m,m‘\in \mathbb Z\)\(mm‘=t^2-k<t^2\),不妨设 \(m<|t|\)

        \(\begin{cases}m‘>0,有0<(m-t)^2<(2t)^2<4mt^2+1,矛盾;\\m‘=0,k=t^2;\\m‘<0,k=\frac{(m‘-t)^2}{4m‘t^2+1}<0,矛盾;\end{cases}\)

          无穷递降;构造;

        整除:最大公约数基本运算,分析其约数。

        \(S_{1,5}\):由欧几里得辗转相除过程中导出结论 \((n^a-1,n^b-1)=n^{(a,b)}-1\)

        有 \((2^{2a}-1,2^{2b}-1)=(2^{(a,b)}-1)(2^{(a,b)}+1)\)

        且\((2^a-1)(2^a+1)=2^{2a}-1\)\((2^b-1)(2^b+1)=2^{2b}-1\)

        \(\to\)\(AC,BD\) 地位相等猜想结论 \((AB,CD)=(A,C)(B,D)(A,D)(B,C)\)

        其中 \(A=2^a-1\)\(B=2^a+1\)\(C=2^b-1\)\(D=2^b+1\)

        \(\to\) \(A,B,C,D\) 满足条件 \((A,B)=1,(C,D)=1\).

        \(\to\) 有如下结论 \(k(a,b)=(ka,kb)(k\not=0)\)\((\sum_1^n a_n,)=((\sum_1^m a_m),\sum_m^n a_n)\)

        及条件 \((D,C)=1\)

        \(\to\) \((A,C)(A,D)=(A(A,D),C(A,D))=(A^2,AD,AC,CD)\)

        \(=(A(A,C,D),CD)=(A,CD)\)

        \(\to\) \((A,C)(B,D)(A,D)(B,C)=(A,CD)(B,CD)=(AB,CD)\),猜想得证。

          整除;最大公因子理论(传递关系);

        \(S_{1,6}\):是否 \(\to\)\(\to\) 有限个 \(\to\) 有界 \(\to\) 高次 \(\leq\) 低次 \(\to\) 在整除式左边添互质因式

        \(n!+1|(2012n)!\to (n!+1)(n!)|(2012n)!\to (n+1)(n!)^{2012}|(2012n)!\)

        由 \((n!)^{2012}|(2012n)!\) \(\iff\) \(\tbinom{2012n}{n,n,...,n,n}\in\mathbb Z\)\((n!+1,(n!)^{2012})=1\)

        有 \((n!+1)(n!)^{2012}|(2012)!\),只需把 \(n!\) 变为同阶多项式,

        (又有 \(Strling\) 公式 \(n!\sim \sqrt {2\pi n}(\frac n e)^n\),)

        \(\to\) 只需证 \(n!>(\frac n e)^n \iff ln_n+ln_{n-1}+...+ln_1>nln_n-n\),归纳

        \(\to\)\(\leftarrow\)\(ln_{n+1}>(n+1)ln_{n+1}-nlnn-1\)

        \(\to\)\(\leftarrow\)\(1>n(ln_{n+1}-ln_n)\) \(\to\) \(1>ln_{{(1+\frac 1n)}^n}\)

        \(\to\)\(\leftarrow\)\(e>(1+\frac 1n)^n\) ,引理得证。

        \((2012n)^{2012n}>(2012n)!\geq (n!+1)(n!)^2012>(n!)^{2013}>(\frac ne)^{2013}\)

        \(\to\) 高次小于低次 \(\to\) 有界 \(\to\) 有限 \(\to\) 否。

          整除;估计;放缩;

        \(S_{1,7}\):最多只有 \(\to\) 反证 \(\to\) 假设存在两种方案 \(\to\) 分析约数 \(\to\) 找矛盾

        设 \(ab=cd=\frac{n^4}{16}(a>c\geq d>b),n\geq a-b\).

        发现各数分担各因子,考虑用最大公因数换元表示各数。

        设 \((a,c)=p\to a=pq,c=pr,(q,r)=1\to qb=rd\)

        \(\to b=rs,d=qs\to pq>pr\geq qs>rs\to q>r,p>s\)

        \(\to\)(放缩)\(n\geq a-b=pq-rs\geq(s+1)(r+1)-rs=r+s+1\)

        \(\to\) \(r+s\leq n-1\to b\leq \frac{(n-1)^2}2\to a\leq b+n=\frac{(n+1)^2}2\)

        \(\to\) \(ab\leq(\frac{n^2-1}2)^2<\frac {n^4}{16}\)

          整除;用大小关系放缩消元;最大公因数理论;均值不等式;

      \(S_{1,8}\):高次小于低次 \(\to\) 降高次或升低次 \(\to\) 估计,分离 \(\to\) 低次乘 \(x\)

      估计 \(x(x^n+2^n+1)=x^{n+1}+2^nx+x>x^{n+1}+2^{n+1}+1\to x\geq2\)

      估计 \((x-1)(x^n+2^n+1)=x^{n+1}+2^nx+x-x^n-2^n-1<x^{n+1}+2^{n+1}+1\)

      \(\to\) \(x(2^n+1)<3*2^n+x^n+2\to\) 要求 \(n\) 的次数足够大

      (若满足以上二式,则说明 被除式 被夹在 除式 的两相邻倍数之间,即整除式不成立)

      放缩要求 \(x^n>x(2^n+1)\to x^{n-1}\geq2^n+1(x\geq2)\)\(x\) 增长幅度 \(>2\) 增长幅度

      \(\to\) 考虑最小情况 \(n=2\to x\geq5\) \(\to\)\(n\geq2\) 时分类

      \(\begin{cases}n=1,x=4 \or 11\to(1,4)\or(1,11);\\n\geq2,{\begin{cases}x=1,2^n+2|2^{n+1}+2,舍;\\x=2,2^{n+1}+1|2^{n+2}+1,舍;\\x=3,3^n+2^n+1|3^{n+1}+2^{n+1}+1,舍;\\x=4,2^{2n}+2^n+1|2^{2n+2}+2^{n+1}+1,舍;\\x\geq5,x^n=x*x^n-1\geq x*(2^n+1),舍;\end{cases};}\end{cases}\)

        分离;估计;放缩;

      \(S_{1,10}\):无限解问题 \(\to\) 估计或分离找有限解 \(\to\) 放缩后约为 \(a^{m-n}\),分类考虑。

      \(\begin{cases}m\leq n,a^{m-1}+1\geq a^{n-1}+a,矛盾;\\m>n,m=n+k\to a^n+a^2-1|a^{k+2}-a^k-a+1\\a^{k+2}-a^k-a+1=(a-1)(a^{k+1}+a^k-1),\begin{cases}a=1时成立;\\a有无穷多解;\end{cases}\\\to a^n+a^2-1|a^{k+1}+a^k-1\\构造辅助函数 f(x)=x^n+x^2-1,g(x)=x^{k+1}+x^k-1\\有f(0)*f(1)<0\to存在\varepsilon\in(0,1)使f(\varepsilon)=0\to g(\varepsilon)=0\\\to\begin{cases}\varepsilon^{k+1}+\varepsilon^k-1=0;\\\varepsilon^n+\varepsilon^2-1=0;\end{cases}\to \varepsilon^{k+1}-\varepsilon^n=\varepsilon^2-\varepsilon^k\\\to\begin{cases}k<2,RHS<0,|LHS|>>>|RHS|,舍;\\k>2,n>k+1>k>2,|LHS|<<<|RHS|,舍;\end{cases} \\\to只有k=2且n=k+1=3时成立\to(5,3); \end{cases}\)

        化归;降次(夹在两差距极小倍数之间);

\(\begin{cases}\end{cases}\)

[05/06/20] 数论学习笔记

原文:https://www.cnblogs.com/alexiswithlucifer/p/12836611.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!