數論構造題，有的是經過命題人精心設計而出，我們往往可以透過逐步逼近慢慢分析來解決；又有一些題可能是先猜後證，這時候估計變成了重要的手段，它考察學生對數量級的感知，不算困難但十分靈性。本文就整理了一些透過估計解決數論構造題的例子（如果有別的好的例子可以私信發我，我可以即時更新），希望能體會它的精髓
例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）
提示：此題解答並不優美，估計意圖十分明顯，只需結合庫默爾定理對整體進行估計即可，此題可作為估計的練習題而不是本文的核心練習
