2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Касательно простых чисел
Сообщение12.04.2017, 08:25 
Аватара пользователя


22/11/13
496
Всем привет. Выводил формулы для посредственных целей и обнаружил одну интересную закономерность.

Остаток от деления $\frac{n^m-n}{m}$ при любом целом $n>0$ :
1) всегда равен нулю, если m - простое;
2) всегда больше нуля, если m - составное и нечетное;

НОД результатов деления d, если m - простые, в большинстве случаев (за исключением одной или ряда первых, малочисленных величин) равен $6\frac{(n+1)!}{(n-k+1)!(k)!}$, где k - констанста ($k=3$). Также при делении d на различные целые числа номера целых результатов опять-таки практически полностью совпадают для различных n (при фиксированном ряде m).

Чем это обусловлено?

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение12.04.2017, 09:09 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
kthxbye в сообщении #1208922 писал(а):
Остаток от деления $\frac{n^m-n}{m}$ при любом целом $n>0$ :
1) всегда равен нулю, если m - простое;
2) всегда больше нуля, если m - составное и нечетное;

1) - это малая т. Ферма, а 2) - неверно, например, при $ n=1$.

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение12.04.2017, 09:12 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Зашлите в Гугл "малая теорема Ферма", "теорема Вильсона" и далее по ссылкам, будет интересно. Первое Ваше наблюдение и есть МТФ, а дальше не очень внятно - НОД чего? Или просто почитайте Бухштаба.

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение12.04.2017, 09:23 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
kthxbye в сообщении #1208922 писал(а):
2) всегда больше нуля, если m - составное и нечетное;
Это неверно не только для $n=1$. Например, $2^{341}-2$ делится на $341$, хотя $341=11\cdot 31$ составное. Есть гораздо более сильные примеры. Например, $n^{561}-n$ делится на $561$ при любом целом $n$, хотя число $561=3\cdot 11\cdot 17$ составное.

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение12.04.2017, 11:40 
Заслуженный участник


08/04/08
8556
kthxbye в сообщении #1208922 писал(а):
2) всегда больше нуля, если m - составное и нечетное;
неверно:
Someone в сообщении #1208927 писал(а):
Это неверно не только для $n=1$. Например, $2^{341}-2$ делится на $341$, хотя $341=11\cdot 31$ составное. Есть гораздо более сильные примеры. Например, $n^{561}-n$ делится на $561$ при любом целом $n$, хотя число $561=3\cdot 11\cdot 17$ составное.
последние называются числами Кармайкла и их бесконечно много. Гуглите также "псевдопростые Ферма".

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение12.04.2017, 12:27 
Аватара пользователя


22/11/13
496
Благодарю, все просмотрю. Касательно НОДа:

1. Берем например первые 20 простых чисел: 2,3,5...71
2. При $n=2$ результат деления d=1, 2, 6, 18, 186, 630, 7710, 27594, 364722...
НОД=6, для всех кроме 1 и 2.
3. $n=3$, d=3, 8, 48, 312, 16104, 122640, 7596480, 61171656, 4093181688...
НОД=24, кроме 3 и 8.
4. $n=4$, d=6, 20, 204, 2340, 381300, 5162220, 1010580540, 14467258260...
НОД=60 (кроме 6,20,204).
5. $n=5$, d=10, 40, 624, 11160, 4438920, 93900240...
НОД=120, (кроме 10,40,624).
6. $n=6$, НОД=210 (кроме 15, 70, 1554, 39990).

Имеем последовательность НОД: 6,24,60,120,210,336,503,720,990...
Делим на 6 получаем ряд 1,4,10,20,35,56,84,120,165...

Теперь возьмем 40 первых простых чисел и будем последовательно делить d на 2,3..20, записывая номера d, которые делятся без остатка:

а) $n=2$;
2 - все, кроме 1
3 - все, кроме 1,2
4 - не делятся
5 - 6,7,10,12,13,16,18,21,24,25,26,29,30,33,35,37,40 (назовем A)
6 - все, кроме 1,2
7 - 6,8,11,12,14,18,19,21,22,25,27,29,31,34,36,37,38 (B)
8 - не делятся
9 - 4 и далее B
10 - A
11 - 11,13,18,20,26,32,36 (C)
12 - не делятся
13 - 12,18,21,25,29,37 (D)
14 - B
15 - A
16 - не делятся
17 - 13,21,24,25,30,33 (E)
18 - 4 и далее B
19 - 12,21,29,31,38 (F)
20 - не делятся

б) $n=3$;
2 - все, кроме 1
3 - все, кроме 2
4 - все, кроме 1
5 - A
6 - все, кроме 1,2
7 - B
8 - все, кроме 1
9 - не делятся
10 - A
11 - 5 и далее C
12 - все, кроме 1,2
13 - 4 и далее B (кроме 6)
14 - B
15 - A
16 - 3 и далее A
17 - 25,30
18 - не делятся
19 - F
20 - A

в) $n=4$;
1. В большинстве делятся на 2,3,4,5,6,10,12,15,20;
2. Не делятся на 8, 16;
3. 7 - B, 9 - B, 11 - C, 13 - B, 14 - B, 17 - A, 18 - B, 19 - F;

При желании можно продолжить, если конечно этот вопрос уже не рассмотрен кем-то досконально.

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение12.04.2017, 13:23 
Аватара пользователя


29/04/13
7126
Богородский
kthxbye в сообщении #1208961 писал(а):
Делим на 6 получаем ряд 1,4,10,20,35,56,84,120,165...

Ну то бишь всем известные тетраэдральные числа A000292.

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение12.04.2017, 13:52 
Аватара пользователя


22/11/13
496
Yadryara, да, как частный случай
kthxbye писал(а):
$\frac{(n+1)!}{(n-k+1)!(k)!}$
или даже просто $\frac{(n)!}{(n-k)!(k)!}$;
Но как это связано с НОД и малой теоремой Ферма?

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение12.04.2017, 20:03 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
kthxbye в сообщении #1208961 писал(а):
... если конечно этот вопрос уже не рассмотрен кем-то досконально.

Вы тут несколько вопросов смешали, отсюда исключения, догадки и т.д. Формула суммы степенного ряда известна:
$n^0+n^1+n^2+...+n^{k-1}=\dfrac{n^k-1}{n-1}.$ Обозначим эту функцию для краткости как $f^k_n$. Справедливо утверждение: если $a\mid b$, то $f^a_n\mid f^b_n$.
Выражение $6\cdot \dfrac{(n+1)!}{(n+1-3)!\cdot 3!}$ легче записать так: $n(n-1)(n+1).$ Почему оно делит указанное целое число при простом $m$, видно из следующих преобразований: $$\dfrac{n^m-n}{m}=n\cdot \dfrac{n^{m-1}-1}{m}=\dfrac{n(n-1)}{m}\cdot \dfrac{n^{m-1}-1}{n-1}=\dfrac{n(n-1)f^{m-1}_n}{m}$$ Все три множителя числителя числа целые, значит $\dfrac{n^m-n}{m}$ кратно $n(n-1)$ (при условии вз. простоты с $m$), под вопросом остается $(n+1)$. Тут возвращаемся к началу: $m-1$ четное, т.е. $2\mid m-1$, значит $f^2_n\mid f^{m-1}_n$, но $f^2_n=\dfrac{n^2-1}{n-1}=n+1$. МТФ касается только делимости на $m$. Ну а с исключениями, думаю, разберетесь.

 Профиль  
                  
 
 Re: Касательно простых чисел
Сообщение13.04.2017, 05:22 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
P.S.
Проще так: если $2\mid m-1$, то $n^2-1\mid n^{m-1}-1$. Значит $n(n-1)(n+1)=n(n^2-1)\mid \dfrac{n^m-n}{m}$ при условии вз. простоты $n(n^2-1)$ и простого $m$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group