Если взять неполное частное q' при делении на N^r, а потом остаток от деления q' на N — то как раз C_M^r и будет. А и неполное частное, и остаток мы выражать уже умеем!
Чтобы добиться исходной цели — задать простоту с помощью экспоненциальных многочленом — остаётся выразить соотношение c=C_M^r. Но биномиальный коэффициент это коэффициент в биноме Ньютона. Так давайте возьмём ну очень большое (относительно M и r) число N и посмотрим на (N+1)^M.
А деление с остатком мы выразить можем: чтобы q было неполным частным от деления A на B, нужно, чтобы выполнялись неравенства A>=B*q и A<B*(q+1) А нестрогое неравенство — это равенство, если добавить к меньшей части ещё одну свободную переменную (а для строгого нужно ещё 1 добавить). Итого соотношение q=r! выражается системой на неотрицательные целые переменные
// M достаточно большое относительно r, // M^r = q*(C_M^r) + x_1, (q+1)*(C_M^r) = M^r + 1 + x_2
Тогда отношение M^r / (C_M^r) чуть-чуть больше r! ; поэтому если M^r на C_M^r поделить с остатком, то при всех достаточно больших M мы как раз r! и получим.
Математические байкиБолее того, если чуть-чуть расширить класс многочленов до экспоненциальных многочленов, разрешив ещё возводить одну переменную в степень другой, то такой многочлен строится совсем "вручную". Для начала вообще представим себе, что мы имеем право использовать…
И пара (k,b) тут — "сертификат простоты" числа p, который есть для всех простых p и только для них.
А как быть, если наш бюрократ не понимает факториалы? Нужно "соотношение факториальности" как-нибудь выразить: p=k+2 c+1-b*p=0 //а тут какие-нибудь уравнения, задающие c=(p-1)! //
А через что мы можем факториал выразить, где он появляется? Первое, что приходит в голову — биномиальные коэффициенты. И действительно, если нам нужно r!, а число M очень большое, то посмотрим на C_M^r = M(M-1)...(M-r+1) / r!
Более того, если чуть-чуть расширить класс многочленов до экспоненциальных многочленов, разрешив ещё возводить одну переменную в степень другой, то такой многочлен строится совсем "вручную".
Для начала вообще представим себе, что мы имеем право использовать ещё операцию "факториал". Как тогда можно задать простоту числа p? Во-первых, нужно попросить, чтобы p было не меньше 2. Ну, тут мы уже видели, как это сделать: одно из уравнений системы будет p=k+2. А как проверить, что p не делится ни на что, кроме 1 и себя? Цикл использовать нельзя — но можно вместо него воспользоваться факториалом. А именно — давайте посмотрим на (p-1)! ; число p простое тогда и только тогда, когда оно взаимно просто с (p-1)!, а это проверяется алгоритмом Евклида: a*(p-1)!-b*p=1. На самом деле, теорема Валлиса утверждает, что простота p равносильна сравнимости (p-1)! с (-1) по модулю p, так что одну переменную можно сэкономить, и написать просто (p-1)!+1-b*p=0.
Ну и — на идейном уровне теперь можно понять, как именно должен работать тот порождающий простые числа многочлен: остальные переменные это "сертификат простоты" для искомого k+2 (спасибо А. Горденко за рисунок!).
Поэтому более правильно определять диофантовость так: подмножество A в Z_+^k называется диофантовым, если существует многочлен P(a_1,...,a_k,x_1,...,x_n), такой, что (a_1,...,a_k) из A <=> существуют (x_1,...,x_n) из Z_+^n, для которых P(a_1,...,a_k,x_1,...,x_n)=0.
(а систему из нескольких диофантовых уравнений можно свернуть в одно взятием суммы их квадратов)
Математические байкиНу и прежде, чем обсуждать, почему это так, давайте ещё чуть-чуть посмотрим на эту формулу. И заметим, что эта формула для простых чисел... для удобства пользователя разложена на множители!
Но если присмотреться, то видно, что вторая скобка это 1 минус сумма квадратов. Поэтому, если значение P положительное, то вторая скобка должна быть равна 1, а каждый квадрат внутри неё должен обращаться в ноль. Поэтому эту теорему можно переформулировать так: число k+2 простое тогда и только тогда, когда существуют (все остальные переменные), для которых выполняется (система полиномиальных уравнений):
Математические байкиИ вот на картинке выше явный пример такого многочлена — которому посвящена статья James P. Jones, Daihachiro Sato, Hideo Wada and Douglas Wiens, "Diophantine Representation of the Set of Prime Numbers", The American Mathematical Monthly, 83 :6 (1976), pp.…
Ну и прежде, чем обсуждать, почему это так, давайте ещё чуть-чуть посмотрим на эту формулу. И заметим, что эта формула для простых чисел... для удобства пользователя разложена на множители!
Потому что перечислимые множества это совершенно не то же самое, что разрешимые (принадлежность которым можно проверить за конечное число операций). И первый пример тут — множество кодов программ, которые когда-нибудь останавливаются, перечислимо (ибо можно запустить симулятор + перебор кодов + параллелизацию), но не разрешимо (ибо теорема Тьюринга и парадокс лжеца).
Математические байкиТеорема, получающаяся из объединения работ Мартина Дэвиса, Юрия Владимировича Матиясевича, Хилари Патнема и Джулии Робинсон, утверждает, что перечислимость — единственное(!) необходимое условие: Теорема [M. Davis, Ю. В. Матиясевич, H. Putnam, J. Robinson]…
Так вот — теорема Дэвиса, Матиясевича, Патнема и Робинсон даёт отрицательное решение проблемы Гильберта — утверждая, что такого алгоритма в принципе существовать не может.
Математические байкиВсё это восходит к десятой проблеме Гильберта: Пусть дано полиномиальное уравнение от нескольких переменных с целыми коэффициентами. Проверить алгоритмически, есть ли у него решения в целых числах. (На картинке выше — соответствующий абзац из книги "Проблемы…
Всё это восходит к десятой проблеме Гильберта: Пусть дано полиномиальное уравнение от нескольких переменных с целыми коэффициентами. Проверить алгоритмически, есть ли у него решения в целых числах.
(На картинке выше — соответствующий абзац из книги "Проблемы Гильберта", издания 1969 года)
Теорема, получающаяся из объединения работ Мартина Дэвиса, Юрия Владимировича Матиясевича, Хилари Патнема и Джулии Робинсон, утверждает, что перечислимость — единственное(!) необходимое условие:
Теорема [M. Davis, Ю. В. Матиясевич, H. Putnam, J. Robinson] Любое перечислимое множество диофантово. Более того, порождающий его многочлен P может быть построен по алгоритму перечисления алгоритмическим образом.
Например, множество составных чисел диофантово, и это совсем просто увидеть: достаточно взять P(a,b)=(a+2)(b+2). Как раз множество положительных значений P на Z_+^2 все составные числа и даст. Но — а будет ли диофантовым, например, множество совершенных чисел? А множество простых делителей чисел вида 2^{2^n}+1 ?
Да — можно смотреть значения многочленов в точках с целыми координатами, а можно в точках с неотрицательными целыми. И хотя для конкретного многочлена это могут быть разные множества — на то, какие множества так вообще получается представить, этот выбор не влияет: если искомое множество X уже представлено как множество положительных значений P на Z^n, то оно же будет множеством положительных значений Q на (Z_+)^n, где Q(a_1,b_1,...,a_n,b_n) = P(a_1-b_1,...,a_n-b_n). И наоборот, если искомое множество X уже представлено как множество положительных значений P на (Z_+)^n, то оно же будет множеством положителных значений Q на Z^4n, где Q(a_1,b_1,c_1,d_1,...,a_n,b_n,c_n,d_n) = P(a_1^2+b_1^2+c_1^2+d_1^2,...,a_n^2+b_n^2+c_n^2+d_n^2). Так что я дальше буду считать, что нас интересуют значения на Z_+^n.
На самом деле — можно задать вопрос, какие вообще множества представляются как множества положительных значений многочленов (от нескольких переменных) с целыми коэффициентами в целых точках. (Такие множества называются диофантовыми .)
Понятно, что для любого многочлена P такое множество перечислимо: есть алгоритм, который рано или поздно напечатает все его элементы (быть может, не по порядку). Потому что мы просто будем обходить всю целочисленную решётку и проверять, положительное ли значение P в этой точке, а если да, то печатать.
И вот на картинке выше явный пример такого многочлена — которому посвящена статья James P. Jones, Daihachiro Sato, Hideo Wada and Douglas Wiens, "Diophantine Representation of the Set of Prime Numbers", The American Mathematical Monthly,83 :6 (1976), pp. 449-464 ; https://www.tandfonline.com/doi/abs/10.1080/00029890.1976.11994142
МА 
