2 марта 1947 г. родился Юрий Владимирович Матиясевич, российский математик, специалист в области математической логики, теории алгоритмов, теории чисел, дискретной математики
Внёс существенный вклад в теорию вычислимости, завершив решение десятой проблемы Гильберта
В этой проблеме требовалось найти единый метод для распознавания наличия решений в целых числах у произвольного диофантова уравнения
Он установил, что метода, требуемого Гильбертом, не существует
Это стало мощным средством для доказательства неразрешимости и других алгоритмических проблем
На этой базе может быть построено решение многих проблем криптографии и теории чисел
Матиясевич сделал также множество замечательных открытий в теоретической информатике, теории графов, аналитической теории чисел
Но самый красивый результат он получил, используя технику, наработанную при решении 10-й проблемы
Оказалось, что существует многочлен с целыми коэффициентами, множество всех неотрицательных значений которого (при положительных целых значениях переменных) совпадает с множеством простых чисел!
Количество переменных в многочлене Матиясевича — 10
Его степень — 15905
Решето Матиясевича-Стечкина — геометрический способ найти все простые числа
Для этого на обычной параболе y = x² отмечаем все точки с целыми координатами и проводим все хорды, соединяющие эти точки на правой и левой ветви
Такие хорды пересекают ось ординат в точках с целыми координатами
Оказывается, что все такие точки имеют координату, являющуюся составным числом, а точки, координаты которых — простые числа, никогда не попадут на такие хорды
Это легко показать:
Уравнение прямой, проходящей через точки А(–а; а²) и В(b; b²) имеет вид:
y = (b–а)x + ab.
Отсюда при x = 0 получаем y = ab
