Факториалы, делимость, простое число.

[Ubermensch]

Доказать, что если $(m-1)!+1$ делится на $m$, то $m$ - простое число.

В решении то в общем-то получается, что при таких условиях $m$ - простое число(кстати хотелось бы увидеть ваше доказательство).
Но если у нас $m=1$, то получается $0!+1=2$, $2$ делится на $m=1$, но $m=1$ - не простое число.

[gris]

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

[nnosipov]

Ubermensch в сообщении #601177 писал(а):

Но если у нас $m=1$, то получается $0!+1=2$, $2$ делится на $m=1$, но $m=1$ - не простое число.

Это означает, что при $m=1$ утверждение неверно. Но оно верно при любом $m>1$, что очень просто доказывается. Гораздо интереснее доказать обратное утверждение: если $m$ --- простое число, то $(m-1)!+1$ делится на $m$. Но и оно не может быть олимпиадной задачей, поскольку хорошо известно под названием теоремы Вильсона.

[Ubermensch]

Господа, так какой ответ на эту задачу?

Ответ предполагается, что всё-таки $m$ при таких условиях простое число.

Но если $0!$ определили как $1$, то значит и нужно считать $0!=1$.
Да и $1$ считать за просто нельзя.

Значит этот контр пример можно считать решением?

-- 30.07.2012, 19:35 --

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

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

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

[Профессор Снэйп]

А что тут доказывать?

Если $m$ делится на простое $p < m$, то $(m-1)!$ делится на $p$, а $(m-1)!+1$ не делится.

-- Пн июл 30, 2012 23:44:42 --

gris в сообщении #601183 писал(а):

Факториал нуля определён искусственно ради биномиальных коэффициентов

Думаю, что не ради биномиальных коэффициентов. Просто сумма нуля слагаемых равна $0$, а произведение нуля множителей равно $1$, это в $99$ процентах случаев удобно. И довольно естественно, на мой взгляд.

[Sonic86]

Теорема Вильсона
Или школьник такое не осилит?

Ubermensch в сообщении #601186 писал(а):

Значит этот контр пример можно считать решением?

Да зачем он нужен. Считайте сразу, что $m>m_0$.

Профессор Снэйп в сообщении #601188 писал(а):

Если $m$ делится на простое $p < m$, то $(m-1)!$ делится на $p$, а $(m-1)!+1$ не делится.

Дааа, контрапозиция - это хорошо

[gris]

Профессор Снэйп,
Возможно. И скорее всего. Но вот данная задача и показывает то, что факториал нуля стоит всё-таки особняком от других факториалов. Да и гамма-функция в нуле не определена.
Удобно, но не наследственно.

[Профессор Снэйп]

Sonic86 в сообщении #601192 писал(а):

Теорема Вильсона...

Для этой задачи не нужна

[Sonic86]

Профессор Снэйп в сообщении #601197 писал(а):

Для этой задачи не нужна

Да я уже понял просто контрапозиция...

[Профессор Снэйп]

gris в сообщении #601196 писал(а):

Возможно. И скорее всего. Но вот данная задача и показывает то, что факториал нуля стоит всё-таки особняком от других факториалов.

function f(n: integer): integer;
var i,m: integer;
begin
  m := 1;
  for i := 1 to n do m := m*i;
  return m
end;

Такой аргумент убеждает?

[gris]

Ваша функция и для отрицательных целых работает, что может привести к запутону.
А окромя этого в некоторых языках приращение переменной цикла по умолчанию устанавливается в -1 в таких случаях.

[Профессор Снэйп]

Теорему Вильсона можно использовать, чтобы обратить утверждение: если $p$ - нечётное простое, то $(p-1)! + 1$ делится на $p$.

[nnosipov]

Профессор Снэйп в сообщении #601206 писал(а):

если $p$ - нечётное простое, то $(p-1)! + 1$ делится на $p$.

Как-то Вы обошли вниманием чётные простые числа

[Shadow]

Вероятно имелось ввиду показать, что если $m=ab, a,b>1$, то $(m-1)!$ делится на $ab$, следовательно $(m-1)!+1$ не может.
И контрапример неуместен.
А делится потому, что а и в присутвствуют как множители в факториале

[Профессор Снэйп]

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

Как-то Вы обошли вниманием чётные простые числа.

А для них доказательство другое. Перебором