a(1)=1，a(2)=2，a(n)=2a(n-1)+a(n-2)，证明：n≥5 时，a(n) 的质因数中有一模 4 余 1

天山草@

数列\( {a_n}  \) 满足 \( a_1=1, a_2=2, a_n=2a_{n-1}+a_{n-2}\),  证明：
当  \( n≥5  \) 时， 任一个 \( {a_n}  \) 的所有质因数中至少有一个是除以 4 余 1。


注： 这道题是 2020 年全国高中数学联合竞赛加试试题（A卷）中的第三题。此卷共有 4 道题，分别是 40分，40分，50分，50分。

天山草@

例如 \( a_5=29\)，而\(29=4×7+1\)，即\( a_5\) 符合要求。
又如\(a_{10}=2378\)，而 \(2378=2×29×41 \)，\(29\) 和 \(41\) 都符合除 \(4\) 余 \(1\) 的要求，即\( a_{10}\)的质因数中至少有一个符合要求。

ysr

a3=5,a4=12,a5=29,……。
29/4余1，所以，29是素数，算是因子？如果算的话至少有一个因子模4余数为1成立。
如果不算的话继续算：
a6=58+12=70=2*35=2*5*7,其中5是一个因子，5/4余1.
所以，命题成立，无需再算下去了。哈哈哈！

ysr

对，这样改就对了，哈哈哈！这样还要继续算下去，直到找出规律，证明任意一个an必有至少一个素因子除以4余1.
a7=140+29=169=13*13,而13/4余1，……。
规律：数列递推下去总是一奇一偶的，因为2*偶数+奇数为奇数，而2*奇数+偶数为偶数。
2*偶数得到的偶数除以4必然余数为0，而2*奇数得到的偶数除以4余数必然为2。
所以其中偶数是是4x型和4x+2型交互排列的。如a4=12=4*3，a6=70=4*17+2，a8=4*102.
仅此规律不能证明，继续算：
a8=338+70=408=4*102=4*3*34=4*6*17,而17/4余1.

ysr

a9=2*408+169=816+169=985,含有因子5，5除以4余1。
985=5*197，而197是素数，197除以4余1.
a10=2*985+408=1970+408=2378=2*29*41.
29除以4余1，41除以4余数1，
照此下去应该成立了，可能不会出现不含有因子除以4余1的了。
无法证明！

ysr

如下是程序计算的a3~a102项：
/5/12/29/70/169/408/985/2378/5741/13860
/33461/80782/195025/470832/1136689/2744210/6625109/15994428/38613965/93222358
/225058681/543339720/1311738121/3166815962/7645370045/18457556052/44560482149/107578520350/259717522849/627013566048
/1513744654945/3654502875938/8822750406821/21300003689580/51422757785981/124145519261542/299713796309065/723573111879672/1746860020068409/4217293152016490
/10181446324101389/24580185800219268/59341817924539925/143263821649299118/345869461223138161/835002744095575440/2015874949414289041/4866752642924153522/11749380235262596085/28365513113449345692
/68480406462161287469/165326326037771920630/399133058537705128729/963592443113182178088/2326317944764069484905/5616228332641321147898/13558774610046711780701/32733777552734744709300/79026329715516201199301/190786436983767147107902
/460599203683050495415105/1111984844349868137938112/2684568892382786771291329/6481122629115441680520770/15646814150613670132332869/37774750930342781945186508/91196316011299234022705885/220167382952941249990598278/531531081917181734003902441/1283229546787304717998403160
/3097990175491791170000708761/7479209897770887057999820682/18056409971033565286000350125/43592029839838017630000520932/105240469650709600546001391989/254072969141257218722003304910/613386407933224037990008001809/1480845785007705294702019308528/3575077977948634627394046618865/8631001740904974549490112546258
/20837081459758583726374271711381/50305164660422142002238655969020/121447410780602867730851583649421/293199986221627877463941823267862/707847383223858622658735230185145/1708894752669345122781412283638152/4125636888562548868221559797461449/9960168529794442859224531878561050/24045973948151434586670623554583549/58052116426097312032565778987728148
/140150206800346058651802181530039845/338352530026789429336170142047807838/816855266853924917324142465625655521/1972063063734639263984455073299118880/4760981394323203445293052612223893281/11494025852381046154570560297746905442/27749033099085295754434173207717704165/66992092050551637663438906713182313772/161733217200188571081311986634082331709/390458526450928779826062879981346977190

ysr

末尾数字好像是循环的，分别是5，2，9，0，9，8，5，8，1，0，1，2，后面开始循环了。

ysr

a32=627013566048=2*2*2*2*2*3*17*577*665857，其中的17除以4余1，577除以4余1.

ysr

比如5741是素数，除以4余1。这个也算正确吧。

ysr

6625109=37*179057，其中37除以4余1，179057除以4余数为1。
1136689=137*8297，其中137除以4余1，8297除以4余1.
15994428=2*2*3*19*29*41*59，其中29除以4余1，41除以4余1。
93222358=2*23*353*5741，其中353除以4余1，5741除以4余1。
80782=2*13*13*239，其中13除以4余1.
470832=2*2*2*2*3*17*577，其中17除以4余1，577除以4余1。