Квадратичные вычеты

Предположим противное, пусть существует конечное число простых чисел вида Пусть это

Построим число:

Заметим, что так как для всех и

Посмотрим на делители

Если простое, то оно новое простое вида —– противоречие. Если составное, рассмотрим любой его простой делитель Тогда: так как Заметим, что

Следовательно, — квадратичный вычет по модулю т.е.:

Раскроем символ Лежандра:

Упростив, получим:

Таким образом, все простые делители числа имеют вид противоречие, так как