数论构造还是相当玄学的版块,经常出现什么都没学的萌新能做出来但是数论较好的人卡题的现象……
在其他的笔记我多少已经记录了专题类的构造,这里更多是记录一些综合性的/莫名其妙的构造。
例1
证明:对任意正整数 \(n\) ,存在正整数 \(k\) ,满足 \(51^k\equiv 17\:(mod~2^n)\)
这是典型的归纳构造题,根据升幂定理,我们看到 \(v_2(51^{2^k}-1)=k+2\)
我们对 \(n\) 归纳证明,实际上,若对 \(n\) 存在正整数 \(k\) ,则
\(51^k\equiv 17+s\cdot 2^n\:(mod~2^{n+1})\)
\(51^{k+2^{n-2}}\equiv 17+t\cdot 2^n\:(mod~2^{n+1})\)
根据 \(v_2(51^{2^{n-2}}-1)=n\) 可知 \(s\ne t\) ,有一个是偶数,完成了归纳。
注:还有一个做法是 \((51^2)^k\) 模 \(2^n\) 意义下遍历所有模 \(8\) 余 \(1\) 的数,这个做法非常精妙。
例2
设 \(a_n=2^{n^3+1}-3^{n^2+1}+5^{n+1}\) ,证明: \(\{p\mid p是素数,\exists n,p\mid a_n\}\) 是无限集
我们取素数 \(p\) 满足 \(p\equiv 1,7\:(mod~8),p\equiv 2\:(mod~3),p\equiv 2,3\:(mod~5)\) ,看到 \((\frac 2p)=1,(\frac 3p)=(\frac 5p)=-1\)
下面取 \(n=\frac {p-1}2\) ,看到 \(n^3+1,n^2+1,n+1\equiv 1+\frac {p-1}2\:(mod~p-1)\) ,从而 \(a_n\equiv 2+3-5=0\:(mod~p)\)
由 \(Dirichlet\) 定理,这样的素数无穷。
注:别问我这是怎么来的,我凑了半个多小时。标答假设素因子有限然后控制素因子幂次做的,也是很标准的方法。
例3
定义 \(\omega(n)\) 表示 \(n\) 的不同的素因子个数。求证:存在无穷个 \(n\) 满足 \(\omega(n)<\omega(n+1)<\omega(n+2)\)
不能再自然的想法是令 \(n=2^k\) ( \(2\) 就够了),我们只需要 \(\omega(2^k+1)<\omega(2^{k-1}+1)+1\)
我们将分析数列 \(a_n=\omega (2^n+1)\) ,证明存在无穷多 \(a_n\ge a_{n+1}\) ,我们用反证法,假设从某个 \(N\ge 2\) 开始有 \(a_n+1\le a_{n+1}\)
于是 \(a_{3N}\ge a_n+2N\) ,我们看到 \(2^{3N}+1\ge p_1p_2...p_{2N}\) ,但 \(p_3\) 开始就有 \(p_i\ge 4\) ,我们看到 \(2^{3N}+1\ge 4^{2N-1}\) ,这是显然矛盾的。
例4
定义 \(P(n)\) 表示 \(n\) 的最大素因子。求证:存在无穷个 \(n\) 满足 \(P(n)<P(n+1)<P(n+2)\)
取 \(n+1=p^{2^m}\) ,显然序列 \(a_m=p^{2^m}+1\) 两两互素,而 \(n=p^{2^m}-1=a_{m-1}a_{m-2}...a_1(p-1)\)
我们只要在数列中找到一个 \(m\) ,使得 \(P(a_1),P(a_2),...,P(a_{m-1})<p<P(a_m)\) 。只要找到第一个 \(P(a_m)>p\) 即可。
我们说了,序列 \(a_m\) 两两互素,所以有无穷多素因子,肯定有一个这样的 \(m\) 。
上述分析对所有素数 \(p>2\) 有效,由素数的无穷性给出结论。
标签:frac,数论,51,构造,ge,无穷,equiv,mod From: https://www.cnblogs.com/Rocking-Yoshi/p/18329863