Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 11 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 00:48 
Не в сети
Начинающий
Зарегистрирован:
30 янв 2017, 00:41
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Салют всем!

Вот уже неделю бьюсь вот над таким соотношением:[math]\frac{ \left[ \frac{ n }{ 2 } \right]! }{ n }[/math]

Суть вот в чем, при [math]n > 7[/math] получается неправильная дробь, соответственно у нее есть целая и дробная часть. Существует ли формула для вывода дробной части в общем виде? И возможно ли ее вообще вывести?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 07:14 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 2677
Cпасибо сказано: 164
Спасибо получено:
448 раз в 418 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Не уверен, что можно.
Но поправлю: отличная от 0 дробная часть появляется только, если n - простое или равно 9 (для n > 7).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 10:47 
Не в сети
Начинающий
Зарегистрирован:
30 янв 2017, 00:41
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Booker48 писал(а):
Не уверен, что можно.
Но поправлю: отличная от 0 дробная часть появляется только, если n - простое или равно 9 (для n > 7).


Грамотное наблюдение. Собственно для этого это соотношение и нужно.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 12:29 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 6014
Cпасибо сказано: 92
Спасибо получено:
1357 раз в 1236 сообщениях
Очков репутации: 260

Добавить очки репутацииУменьшить очки репутации
Интересно, но здесь действительно есть удивительные факты.

Понятно, что есть школьная теорема Вильсона [math](p-1)! \equiv -1 \pmod{p}[/math]
Но вот дальше начинаются чудеса.
Оказывается, скорее всего, верна и след.теорема:
Если [math]p \equiv 3 \pmod 4[/math], [math]p>10[/math] - простое, то
[math]\left(\frac{p-1}2\right)! \equiv \pm 1 \pmod{p}[/math].
Мне кажется это совершенно нетривиальным фактом (может быть я ошибаюсь - и это можно легко доказать).

Определить критерий, для каких простых [math]\left(\frac{p-1}2\right)! \equiv 1 \pmod{p}[/math], а для каких [math]\left(\frac{p-1}2\right)! \equiv -1 \pmod{p}[/math] мне не удалось. Но их примерно поровну.

Я проверил эти последовательности в OEIS: A055939 и A058302, но дополнительной информации, увы, никакой.

Если сюда заглянет Shadows, возможно он сможет сказать больше.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 14:52 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 6014
Cпасибо сказано: 92
Спасибо получено:
1357 раз в 1236 сообщениях
Очков репутации: 260

Добавить очки репутацииУменьшить очки репутации
И чудеса на этом не заканчиваются.
По всей видимости верна и следующая теорема.

Если [math]p \equiv 1 \pmod 4[/math], [math]p[/math] - простое, то
[math]\left(\left(\frac{p-1}2\right)!\right)^2 \equiv -1 \pmod{p}[/math].

Я, конечно, не очень интересуюсь факториалами, но все же среди олимпиадных задач я подобного не встречал (или забыл). Но само по себе кажется весьма красивым.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 15:42 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 6014
Cпасибо сказано: 92
Спасибо получено:
1357 раз в 1236 сообщениях
Очков репутации: 260

Добавить очки репутацииУменьшить очки репутации
Вот ответ Константина Кнопа с дружественного форума

Пусть x=((p-1)/2)!
Разберемся, как связаны x^2 и (p−1)!(modp). Второй равен произведению x на все множители от (p+1)/2 до (p−1). Последний из этих множителей сравним с −1, предыдущий с −2, и т.д., (p+1)/2≡−(p−1)/2. Таким образом, их произведение сравнимо с x, умноженным на некоторое количество минус единиц.

Это количество равно количеству чисел от (p+1)/2 до (p−1), то есть оно нечётно для p=4k+3 и чётно для p=4k+1. Таким образом, для p=4k+1 получаем x^2≡(p−1)!(modp), а для p=4k+3 получаем x^2≡−(p−1)!(modp). Осталось воспользоваться теоремой Вильсона.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 16:38 
Не в сети
Beautiful Mind
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1193
Cпасибо сказано: 96
Спасибо получено:
478 раз в 379 сообщениях
Очков репутации: 143

Добавить очки репутацииУменьшить очки репутации
Для [math]p=4k+1[/math]

[math](p-1)!\equiv -1 \pmod p[/math] Теорема Вильсона

С одной стороны имеем остатки [math]1,2,3,\cdots 2k[/math] по модулю p

С другой [math]-1,-2,-3, \cdots -2k[/math]

Поскольку число "отрицательных" множителей четное, их произведение положителное, а значит [math]\left((\frac{p-1}{2})!\right)^2\equiv (p-1)! \pmod p[/math]

Для [math]p=4k+3[/math]

Аналогично, только отрицательные там нечетное число. И если обозначим [math](\frac{p-1}{2})!\equiv x \pmod p[/math]По теореме Вильсона имеем [math]-x^2\equiv -1 \pmod p[/math]

[math](1-x)(1+x)\equiv 0 \pmod p[/math]

[math]x\equiv \pm 1 \pmod p[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Shadows "Спасибо" сказали:
swan
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 16:42 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 6014
Cпасибо сказано: 92
Спасибо получено:
1357 раз в 1236 сообщениях
Очков репутации: 260

Добавить очки репутацииУменьшить очки репутации
Shadows, вот я не зря в вас верил :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 18:05 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 2677
Cпасибо сказано: 164
Спасибо получено:
448 раз в 418 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Что-то я недопонял. :((
8! mod 17 = 13

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления факториала
СообщениеДобавлено: 30 янв 2017, 18:13 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 6014
Cпасибо сказано: 92
Спасибо получено:
1357 раз в 1236 сообщениях
Очков репутации: 260

Добавить очки репутацииУменьшить очки репутации
[math]13^2\equiv -1 \pmod {17}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
Booker48
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 11 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Найти остаток от деления и последнюю цифру от деления

в форуме Теория чисел

shurup4ik91

5

2890

09 дек 2010, 23:20

Связь от числа факториала и остатком его деления на x

в форуме Теория чисел

SiFlyer

4

100

17 окт 2020, 00:18

Остаток от деления

в форуме Начала анализа и Другие разделы школьной математики

photographer

9

438

21 июн 2016, 09:40

Остаток деления

в форуме Алгебра

Waickem

2

501

22 авг 2013, 11:29

Остаток от деления

в форуме Теория чисел

Kirill Kolokolcev

1

298

09 июн 2018, 00:44

Найти остаток от деления

в форуме Теория чисел

PiterAnd

15

3316

30 сен 2012, 16:42

Найти остаток от деления

в форуме Теория чисел

Sec

4

768

20 янв 2015, 22:15

Найти остаток от деления

в форуме Теория чисел

Trek

2

643

16 янв 2015, 20:46

Найти остаток от деления

в форуме Алгебра

afraumar

4

2993

12 авг 2013, 15:20

Найти остаток от деления

в форуме Алгебра

afraumar

3

725

15 авг 2013, 13:05


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2020 MathHelpPlanet.com. All rights reserved