Question

1. Найдите все натуральные
, что число
- простое, состоящее из не более, чем

19 цифр.
2. см рис.
3.Докажите, что не существует натурального , при котором
делится на 101
хоть с чем-нибудь)​

$n$
${n}^{n} + 1$
${n}^{2} + n+1$

Answer 1

Пусть $n^n+1=p$ простое число, большее 2 (если $p=2$, то $n=1$). Тогда $n$ четно. Заметим, что $16^{16}=2^{4\times16}=2^{64}(10^3)^{6,4}=10^{19,2}10^{19}$, случай с 18-ю уже очевидно не подходит. Возможные кандидаты: четные числа от 2 до 16.

Согласно малой теореме Ферма $n^{p-1}\equiv1\mod p$, вместе с тем $n^n\equiv-1\mod p$. Сложив оба сравнения, получим $n^{p-1}+n^{n}\equiv 0\mod p \Leftrightarrow n^{n}(1+n^{p-1-n})\equiv 0\mod p$, откуда ясно, что $n^{p-1-n}\equiv 0\mod p$. Эта процедура похожа на алгоритм Евклида. Повторив такую операцию еще несколько раз, получим $n^{r}\equiv-1\mod p$, где $r$ определяется так: $p-1\equiv r\mod n$. Но $p-1=n^n\equiv 0\equiv r\mod n$, то есть $r=0$. Тогда $n^{0}=1\equiv-1\mod p \Leftrightarrow 2\;|\;p$, противоречие.

Есть еще случай, когда, производя операцию (алгоритм Евклида), мы не приходим к 0 (попадаем в цикл). Это происходит тогда и только тогда, когда $p-1-nk=n\Leftrightarrow p=n(k+1)+1$. Небольшая проверка дает $k=1$: $n^n+1=2n+1\Leftrightarrow n^n=2n \Rightarrow n=2$.

ответ: $n=1,\;n=2$

Представим себе последовательность прямоугольных треугольников в системе координат. Ровно один катет треугольника вертикален и ровно один горизонтален. Пусть каждый треугольник "цепляется" вершиной за предыдущий так, что гипотенузы треугольников образуют монотонно снижающуюся ломаную. Тогда неравенство очевидно: кратчайший путь есть отрезок между верхней вершиной первого треугольника в последовательности и нижней вершиной нижнего. Равенство достигается тогда, когда треугольники попарно подобны.

Предположим обратное.

Заметим, что все $n$, такие что $n\equiv 1\mod 101$ не подходят. Поскольку 101 является простым, то $n-1$ взаимно просто со 101. Значит, $\forall n\in\mathbb{N}:101 \nmid n^2+n+1 \Leftrightarrow 101\nmid (n-1)(n^2+n+1) \Leftrightarrow 101\nmid n^3-1$.

Более того, согласно малой теореме Ферма $n^{101-1}=n^{100}\equiv 1\mod 101$. Значит, порядок числа $n$ по модулю 101 делит как 3, так и 100, но 3 и 100 взаимно просты. Противоречие.