Изменения
→Доказательство бесконечности простых чисел
|statement= Простых чисел бесконечно много.
|proof=
Предположим, что простых чисел конечное число. Тогда любое число <tex>n = {p_1}^{\alpha_1}{p_2}^{\alpha_2}\dots{p_k}^{\alpha_k}</tex>, где <tex>k</tex> {{---}} это некоторая константа. Возьмём <tex>n</tex> наибольшей колмогоровской сложности. Тогда <tex>KS(n) \geqslant log_2 n</tex>, но также <tex>KS(n) \leqslant 2 k log_2 log_2 n + c</tex>, т.к. <tex>\alpha_i \leqslant log_2 n</tex>. Но это неравенство не будет выполняться на достаточно больших <tex>n</tex>, противоречие.
}}
