Задача по ТЧ

[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$.

[nnosipov]

В целом, аккуратная реализация идеи

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

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

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

[bot]

df Уже сказано, что годятся $8,9$ и простые $4m+1$ - это все.

Действительно пусть $p^k$ собственный делитель
$n$, тогда $ p ^ k!< n $ следовательно показатель $p$, с которым он входит в разложение $(n-1)!$ не меньше $2^k-1\geq2k-1 $ Поэтому число $x$, должное быть сравнимым с произведением остальных по модулю $n$ делится на $p^k$.
Следовательно, из составных годными могут быть только $p^m$.
Рассмотрим $n=p^k, k>1$. Вычисляем показатель $p$ в числе $(p^k-1)!$. Он равен $- k +\frac{p^k-1}{p-1}$. Этот показатель больше, либо равен $2k$ при $p>3, k>1$,
а также при $p=2, k>3$ и при $p=3, k>2$.

[Shadow]

bot, все так, да.

bot в сообщении #1716963 писал(а):

Следовательно, из составных годными могут быть только $p^m$.

Добавим и $2p$, которое во второй части задачи даст противоречие/несуществование по модулю $2$. (и по модулю $p$ тоже).
Первую часть можно ограничить заметив, что если $n$ можно представить в виде произведения двух взаимнопростых чисел, каждое больше $2$, то про любом выборе будет делимость на $n$. А значит $n$ либо степень простого, либо удвоенная степень нечетного простого.

[ex-math]

А разве случай $2p$ не покрывается первой частью рассуждения?