Найти НОД (очень старая олимпиадная задача)

[Ktina]

Найти НОД всех чисел вида

$$3^{2n+3}+40n+1957$$

, где $n\in\mathbb N$

[hippie]

Ответ: 64.

$\text{НОД}(3^{2\cdot 1+3}+40\cdot 1+1957,\ 3^{2\cdot 2+3}+40\cdot 2+1957)=\text{НОД}(2240,\ 4224)=64.$

То, что при всех $n\quad 3^{2n+3}+40n+1957$ кратно 64 эквивалентно тому, что $27(9^n-1)\equiv 24n\ (\mod 64),$ что, в свою очередь, эквивалентно $1+9+9^2+\dots+9^{n-1}\equiv n\ (\mod 8).$

[Ktina]

hippie,
Добавлю лишь, что задача предлагалась на Ленинградской Математической Олимпиаде в 1957г.