Number Theory problem

[Keter]

Доказать, что $\forall a \in \mathbb{N}, 1<a \le 100$ существует хотя бы одно натуральное число $n \le 6,$ для которого число $a^{2^n}+1$ составное.

Мини-задача
Доказать, что $k, (k-1), (k^2+k-1), k \in \mathbb{N}, k>1$ попарно взаимно простые.

Prove that $ \forall a \in \mathbb{N}, 1 <a \le 100 $ has at least one natural number $ n \le 6, $ for which the number of $ a^{2^n}+1 $ is composite.

Mini-problem
Prove that $ k, (k-1), (k ^ 2 + k-1), k \in \mathbb{N}, k> 1 $ pairwise relatively prime.

[Cash]

см. Серпинский "250 задач..."

мини-задача: честно применить алгоритм Евклида.

[ewert]

Зачем Евклид? Из, скажем, $k-1=mz$ следует, что $k^2+k-1=(m^2z+3m)z+1\neq nz$.

[Cash]

А что сложного? В каждом случае один раз с остатком поделить?
$k=1 \cdot (k-1)+1$
$k^2+k-1=k\cdot k+(k-1)$
$k^2+k-1=(k+2)\cdot (k-1)+1$

[nnosipov]

Keter в сообщении #736136 писал(а):

Доказать, что $\forall a \in \mathbb{N}, 1<a \le 100$ существует хотя бы одно натуральное число $n \le 6,$ для которого число $a^{2^n}+1$ составное.

Вариация на тему из Серпинского, предложенная в финале XXXV Всероссийской олимпиады: даны натуральные числа $x$ и $y$ из отрезка $[2;100]$; докажите, что при некотором натуральном $n$ число $x^{2^n}+y^{2^n}$ --- составное.

-- Чт июн 13, 2013 21:51:22 --

ewert в сообщении #736163 писал(а):

Зачем Евклид?

Евклид здесь нужен концептуально. Что касается альтернативы, то можно рекомендовать язык сравнений как весьма эффективное средство: если $k-1 \equiv 0 \pmod{z}$, то $k^{\text{2 (или 222, что неважно)}}+k-1 \equiv 1 \pmod{z}$.