Задача по ТЧ

[Shadow]

Здравствуйте,
Придумал задачу (конечно на основе другой, которая оказалась в последствии слишком простой) - нетрудная, но должны же быть задачи разного уровня сложности. И наверное кто-то придумал до меня и лучше сформулировал, но все таки:

Для каких натуральных $n>2$, среди чисел $1,2, \ldots n-1$ существует такое, которое равно произведению всех остальных по модулю $n$?

[nnosipov]

Shadow в сообщении #1714951 писал(а):

на основе другой

Кажется, я догадываюсь, на основе какой.

Есть очевидные значения $n$, которые годятся --- это все простые числа, которые $\equiv 1 \pmod{4}$. Видимо, вся интрига в том, есть ли другие решения.

[Shadow]

nnosipov в сообщении #1714954 писал(а):

Есть очевидные значения $n$,

Ну, как сказать...теорема Вильсона, квадратичные вычеты...для непрофильных школах можно сказать убойная. Но для dxdy, конечно..

nnosipov в сообщении #1714954 писал(а):

Видимо, вся интрига в том, есть ли другие решения.

так себе интрига, но да.

[nnosipov]

У меня в ближайший понедельник экзамен по теории чисел, попробую предложить своим студентам.

[wrest]

nnosipov в сообщении #1714954 писал(а):

Видимо, вся интрига в том, есть ли другие решения.

Есть ещё два, $n=8$ и $n=9$

[wrest]

Из разрозненных идей (до теоремы Вильсона). Для составных чисел $n>4$ имеем:
Пусть $n=ab$ составное, тогда оба $a<n$ и $b<n$ и поэтому $(n-1)!$ делится на $n$
Пусть $n=a^2$ но тогда как $a<n$ так и $2a<n$ и опять $(n-1)!$ делится на $n$
Тогда, для удовлетворения условий задачи, должно найтись такое $1\le k \le n-1$ что $k^2$ делится на $n$.
Вот тут и выходит, что таких $n$ только два $n=8$ (соотв. ему $k=4$) и $n=9$ (соотв. ему $k=3$)

[Shadow]

wrest в сообщении #1714973 писал(а):

Тогда, для удовлетворения условий задачи, должно найтись такое $1\le k \le n-1$ что $k^2$ делится на $n$.

Таких $n,k$ бесконечно много, напр. $n=uv^2,k=uv, v>1$

wrest в сообщении #1714973 писал(а):

Пусть $n=a^2$

А $n=2p$ для простого $p$ рассматривали?

[wrest]

Shadow в сообщении #1714979 писал(а):

Таких $n,k$ бесконечно много, напр. $n=uv^2,k=uv, v>1$

Да, фигня у меня получилась.

[ex-math]

Достаточно проверить, что для составного $n\neq4,8,9$ будет $\frac{(n-1)!}{k}\equiv0(\bmod n)$ для всех $k=1,\dots,n-1$. Подозреваю, что это так, поскольку кратности вхождения простых в факториал быстро растут по сравнению с кратностью вхождения в $n$ и $k$, но как-то изящно обосновать не получается.

[nnosipov]

ex-math в сообщении #1714996 писал(а):

поскольку кратности вхождения простых в факториал быстро растут по сравнению с кратностью вхождения в $n$ и $k$

Да, у меня тоже такая идея возникла. В принципе, формула Лежандра должна помочь, но пока не проверил.

[ex-math]

Видимо не зря была подсказка про $n=2p$, потому что при $k=p$, естественно $\frac{(n-1)!}{k}$ не делится на $n$.