Полиномы, сохраняющие взаимную простоту

[maxal]

Руст писал(а):

Задача эта из одного конкурса. Срок подачи решений истёк 22 февраля. Подробнее о предистории может сказать maxaл. Там приводятся много вопросов об этой функции, в том числе 2) и 3) не решённые автором.

Эта была серия задач с онлайнового Математического Марафона (он, кстати, продолжается и по сей день, общее количество предложенных задач - более 60). Утверждение о том, что задачи остались нерешенными, не совсем соответствует действительности. Подробности о том, что решено, а что нет можно узнать из разбора решений этих задач.

[Руст]

На самом деле задача полностью решается без ссылки на теорему Котофеича. Просто громоздко здесь излагать.

[Руст]

Раз уж maxal откопал эту замечательную задачу вновь, она заслуживает полного решения.
Ранее установили, что отмечаются числа $m=\frac{s^2+7}{8}\mod n$, где $s$ пробегает нечётные числа. При этом значение $m=f(n)$, которое впервые отмечается дважды, соответствует минимальному значению $s=x+y, \ y=\frac{2n}{x}$, где $x$ нечётный делитель. Это означает, что в интервале $(x,y)$ (или $(y,x)$, если $y<x$) нет нечётных делителей числа $n$.
Если число $m$ отмечается, то $8m-7$ является квадратом по модулю $8n$. В частности, если $f(n)=n$, то $-7$ является квадратом, т.е. нечётный простой делитель $n$ равен или $7$ ( в этом случае он входит как делитель только в первой степени) или простое $p$, для которого $(\frac{-7}{p})=(\frac{p}{7})=1$. Легко показать, что $f(2^k)\not =2^k$. Поэтому каждое такое $n$ имеет некоторый нечётный простой делитель такого вида. Построим для каждого такого $p$, число $n=pk$, для которого $f(n)=n$. Для $p=7$ легко проверить, что работает $n=28$. Пусть $p$ такое простое число, найдётся единственное нечётное $s$, такое, что $2p<s<3p, p|s^2+7$. Возьмём в качестве $n$ число $n=\frac{s^2+7}{8}=pk, p<2k<\frac{9p}{4}.$ Для любого нечётного делителя $n=pk$ в интервале $(p,2k)$ нет других нечётных делителей числа n, что означает, что $f(n)=n$.

И последний пункт доказывается без всякой ссылки на теорему Котофеича. Об этом в другой раз. Он полностью аналогичен. Просто надо выбрать простое число $p>8m-7$ с условием $(\frac{8m-7}{p})=1$ и действовать так же.