Касательно простых чисел

[kthxbye]

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

Остаток от деления $\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).

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

[Brukvalub]

kthxbye в сообщении #1208922 писал(а):

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

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

[Andrey A]

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

[Someone]

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$ составное.

[Sonic86]

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$ составное.

последние называются числами Кармайкла и их бесконечно много. Гуглите также "псевдопростые Ферма".

[kthxbye]

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

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;

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

[Yadryara]

kthxbye в сообщении #1208961 писал(а):

Делим на 6 получаем ряд 1,4,10,20,35,56,84,120,165...

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

[kthxbye]

Yadryara, да, как частный случай

kthxbye писал(а):

$\frac{(n+1)!}{(n-k+1)!(k)!}$

или даже просто $\frac{(n)!}{(n-k)!(k)!}$;
Но как это связано с НОД и малой теоремой Ферма?

[Andrey A]

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$. Ну а с исключениями, думаю, разберетесь.

[Andrey A]

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