Задача №6 Shortlist-a ММО 2004(Теория чисел)

[student]

Английская версия:
Given an integer $n > 1$, denote by $P_n$ the product of all positive integers $x$ less than $n$
and such that $n$ divides $x^2-1$. For each n > 1, and the remainder of $P_n$ on division by $n$.
Русская версия:
PS: Надеюсь, кто-то поможет с точным переводом этой задачи.

нг:

Красный цвет на форуме зарезервирован для модераторов. Пожалуйста, не нарушайте правила.

[незваный гость]

student писал(а):

For each n > 1, and the remainder of $P_n$ on division by $n$.

For each n > 1, find the remainder of $P_n$ on division by $n$.

Для данного $n > 1$ обозначим $P_n$ произведение натуральных чисел $x$ меньших $n$, таких что $n$ делит $x^2-1$. Найти остаток от деления $P_n$ на $n$ дпя всех | каждого $n > 1$.

[Gordmit]

По-моему, в условии опечатка, и вместо "and" в последнем предложении надо читать "find". Тогда перевод будет примерно такой:

Для $n>1$ обозначим через $P_n$ произведение всех натуральных чисел $x$, меньших $n$ и таких, что $n$ делит $x^2-1$. Для каждого $n>1$ найти остаток от деления $P_n$ на $n$.

[student]

Gordmit да я ошибся!:oops:
Вот исправленный вариант:
Русская версия:
Для $n>1$ обозначим через $P_n$ произведение всех натуральных чисел $x$, меньших $n$ и таких, что $n$ делит $x^2-1$. Для каждого $n>1$ найти остаток от деления $P_n$ на $n$
Английская версия:
Given an integer $n > 1$, denote by $P_n$ the product of all positive integers $x$ less than $n$
and such that $n$ divides $x^2-1$. For each n > 1, find the remainder of $P_n$ on division by $n$.

[maxal]

Понятно, что если $n$ делит $x^2-1,$ то $x^2\equiv 1\pmod n,$ и, таким образом, нам нужно найти произведение всех корней из 1 по модулю $n.$
Если $x$ является корнем из 1, то и $-x$ является корнем из 1, и их произведение равно $-1$ по модулю $n$. При этом за исключением случая $n=2,$ мы имеем $x\not\equiv -x\pmod n.$
Таким образом, для $n>2$ ответом является $(-1)^{r/2},$ где $r$ - это число корней из $1$ по модулю $n.$ Нетрудно также понять, что если $n=2^k p_1^{d_1}\dots p_m^{d_m}$ - разложение на простые, то $r=2^{m+\min\{2,k-1\}}.$

Итак, если $n=4,$ $n=p^k$ или $n=2 p^k,$ где $p$ - нечетное простое, $k\geq 1,$ то ответом является $n-1,$ во всех остальных случаях ответ $1.$

[maxal]

Решение на MathLinks:
http://www.mathlinks.ro/Forum/resources ... 4&p=258123