Задача
NT-B2-M12-P015 Составные члены \(2^{2^n}+3\)
#15
★★★★☆ Уровень 4 из 5
Докажите, что в последовательности \(2^{2^n}+3\), \(n=1,2,\ldots\), бесконечно много составных чисел.
1001 Problems in Classical Number Theory (method inspiration) · Задача 355
Попробуйте найти простой модуль \(p\), для которого \(-3\) является степенью двойки.
По модулю \(19\) имеем \(2^4=16\equiv-3\). Поэтому достаточно добиться \(2^n\equiv4\pmod{18}\), так как порядок \(2\) по модулю \(19\) делит \(18\). Остатки \(2^n\pmod{18}\) периодичны, и \(2^n\equiv4\pmod{18}\) при \(n\equiv2\pmod6\). Значит, для всех \(n\equiv2\pmod6\) число \(2^{2^n}+3\) делится на \(19\). При \(n>2\) оно больше \(19\), следовательно, составно. Таких \(n\) бесконечно много.
Эта задача хорошо показывает периодичность “показателя показателя”.