数论构造题，有的是经过命题人精心设计而出，我们往往可以通过逐步逼近慢慢分析来解决；又有一些题可能是先猜后证，这时候估计变成了重要的手段，它考察学生对数量级的感知，不算困难但十分灵性。本文就整理了一些通过估计解决数论构造题的例子（如果有别的好的例子可以私信发我，我可以实时更新），希望能体会它的精髓
例1 证明：存在无穷多正整数 n ，使得 n^2+1 无平方因子（2015CTST）
证明：熟知 n^2+1 的素因子只能为 4k+1 型素数或是2，且 v_2( n^2+1 )\leq1
设 M 为任意给定正整数
考察集合 S=\left\{ 1^2+1,2^2+1,\cdots,M^2+1 \right\}
那么，S 中元素的平方因子只能是小于 M 的素数的幂，且这些素数都模4余1
设小于 M 的所有 4k+1 型素数为 p_1<p_2<\cdots <p_t
设 A_i=\left\{ n^2+1: n\leq M,p_{i}^{2}\mid n^2+1 \right\}
引理： \left| A_i \right|\leq2([\frac{M}{p_{i}^2}]+1)
引理的证明：考虑连续 p_i^2 个数 (a+1)^2+1,\cdots,(a+p_i^2)^2+1 中 p_i^2 的倍数
若 p_i^2\mid(a+j)^2+1,p_i^2\mid(a+k)^2+1,1\leq j<k\le p_i^2
\Rightarrow p_i^2 \mid (a+k)^2-(a+j)^2=(k-j)(2a+j+k)
\Rightarrow p_i^2 \mid j+k+2a
从而，若有一个 1\le j \le p_i^2 符合要求，不等于 j 的满足要求的 1\leq k \le p_i^2 唯一确定
因此连续 p_i^2 个数 (a+1)^2+1,\cdots,(a+p_i^2)^2+1 至多有两个数为 p_i^2 倍数
将 S 划分成至多 [\frac{M}{p_{i}^2}]+1 组连续 p_i^2 个数，则由上面的推导知 \left| A_i \right|\leq 2([\frac{M}{p_{i}^2}]+1) ，引理证毕
回到原题，由引理知 \left| A_1\cup \cdots \cup A_t \right|\le \left| A_1 \right|+\cdots +\left| A_t \right|\le 2\sum_{i=1}^{t}{([\frac{M}{p_{i}^2}]+1)} \left| S-A_1\cup \cdots \cup A_t \right|
\leq2t+2M(\frac{1}{p_1^2}+\cdots+\frac1{p_t^2})\le 2\cdot \frac{M}{4}+2M(\frac1{25}+\frac1{5\times9}+\frac1{9\times13}+\cdots)
\le\frac{M}2+2M(\frac1{25}+\frac14\cdot \frac15)=\frac{17}{25}M
从而 \left| S-A_1\cup \cdots \cup A_t \right| \ge M-\frac{17}{25}M=\frac{8}{25}M
又 M 可以任意大，因此存在无穷多 n^2+1\in S-A_1\cup \cdots \cup A_t 符合要求，命题得证
注释：此题估计的关键一个在引理，一个在于把平方因子归结为 4k+1 型素数
例2 证明：存在整数 n\geq2^{2018} ，使不存在正整数 x,y,u,v 满足 u,v>1 且 n=x^u+y^v （2018年北大金秋营）
证明：若 u=v=2 ，则 n=x^2+y^2\equiv0,1,2\left( mod4 \right)
设 N\geq 2^{2018} 为任意给定正整数
设 A=\left\{ n:2^{2018}\le n\le N,n\equiv 3 \left( mod 4 \right) \right\}
考察 A 中所含 x^u+y^v 个数，由前面的推导知这样的数对应的 u,v 不全为2
对 x^u+y^v\in A ，不妨设 u\ge 3 ，
当 x,y\geq2 时有 x^u,y^v\le N
\Rightarrow x\le N^{\frac13},y\le N^{\frac12},u,v\le log_2N
\Rightarrow 这样的数至多 N^{\frac56}\left( log_2{N} \right)^2 组
当 x 或 y=1 时，同上这样的数至多 2N^{\frac12}(log_2N) 组
从而 A 中至多 N^{\frac56}\left( log_2{N} \right)^2+2N^{\frac12}(log_2N)\le3N^{\frac56}\left( log_2{N} \right)^2 个数可表成题目要求的形式
又 \left| A \right|\ge \frac{N-2^{2018}}{4} 且 N 充分大时 \frac{ N-2^{2018}}{12N^{\frac56}\left( log_2{N} \right)^2}\rightarrow\infty
因此存在 n\ge 2^{2018} 不能表示为 n=x^u+y^v,u,v\ge2 的形式，命题得证
注释：此题估计的关键是 u,v 之一大于等于3的时候，所要求的形式的数量级会下降很多
例3 设 S=\left\{ 1,4,8,9,\cdots \right\} 为所有方幂构成的集合，将 S 中的数从小到大排列记为 a_1<a_2<\cdots<a_n<\cdots ，证明：存在无穷多 n 使得 9999\mid \left( a_{n+1}-a_n \right) （2020年东南数学奥林匹克竞赛）
证明：只要证明存在无穷多正整数 n 使得 a_{n}=(4999+9999t)^2,a_{n+1}=(5000+9999t)^2
假设 t\geq t_0 时均不存在 n 满足上式，
即对 \forall t\ge t_0 ， (4999+9999t)^2 和 (5000+9999t)^2 之间都存在一个至少3次幂
设 T\ge t_0 为任意给定的正整数，令 N=(5000+9999T)^2
考察 1,2,\cdots,N 中三次以上方幂的个数 K
一方面， 对 i\ge2 , 1,2,\cdots,N 中除1外的 i 次方幂至多 [N^{\frac1i}] 个
且对 i>log_2N ， 1,2,\cdots,N 中除1外无 i 次方幂
\Rightarrow K\leq \sum_{i=3}^{[log_2N]}{\left[ N^{\frac1i} \right]}+1<N^{\frac13}log_2N
另一方面，由假设知对每个 t_0\le t\le T ,(4999+9999t)^2 和 (5000+9999t)^2 间存在一个至少3次方幂
\Rightarrow K\ge T-t_0=\frac{1}{9999}(N^{\frac12}-5000)-t_0
又 t,N 充分大时， \frac{\frac{1}{9999}(N^{\frac12}-5000)-t_0}{N^{\frac13}log_2N}\rightarrow\infty ，矛盾！
因此假设不成立，从而原命题得证
注释：此题的估计是猜到合适的结论并对方幂出现的频率有大致的数学感觉（与例2类似）
最后，留下一个超级复杂的估计构造题练习
练习 给定正整数 k ，对正整数 n ，若组合数 C_{n}^{0},\cdots,C_{n}^{n} 中被 k 整除的数个数不少于 0.99n ，则称 n 是「好的」，证明：存在正整数 N 使得 1,2,\cdots,N 中至少有 0.99N 个是「好的」（2018CTST）
提示：此题解答并不优美，估计意图十分明显，只需结合库默尔定理对整体进行估计即可，此题可作为估计的练习题而不是本文的核心练习
