数论构造

数论构造还是相当玄学的版块，经常出现什么都没学的萌新能做出来但是数论较好的人卡题的现象……

在其他的笔记我多少已经记录了专题类的构造，这里更多是记录一些综合性的/莫名其妙的构造。

例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\) 有效，由素数的无穷性给出结论。