Арифметика целых чисел

Каждое нечётное простое число имеет вид $4 k+1$ или $4 k-1$. Используя мультипликативность множества $S$ из п. 1, доказать бесконечность множества простых чисел вида $4 k-1$.

Доказать, что существует бесконечно много простых чисел вида $4 k+1$, опираясь на следующее нетривиальное утверждение.

Если $n, m \in \mathbb {Z}, \operatorname {НОД~ }(n, m)=1$, и если $p$ — простое число, делящее $n^{2}+m^{2}$, то $p=4 k+1$.

Если натуральное число $n$ делится в точности на $r$ различных простых чисел $p_{1}, \ldots , p_{r}$, то количество чисел, меньших $n$ и взаимно простых с $n$, равно

Функция $\varphi : \mathbb {N} \rightarrow \mathbb {N}$ называется функцией Эйлера.

Проверить справедливость формулы для значений $\varphi (n)$ при $n \leqslant 25$ и при $n=p^{m}$.

Используя биномиальную формулу, индукцией по $n$ доказать, что если $p$ — простое число, то $n^{p}-n$ делится на $p$ при любом $n \in \mathbb {Z}$.