Более широкий взгляд на малую теорему Ферма, составные числа

[Ascar]

Малая терема Ферма гласит

Цитата:

Если $p$ — простое число и $a$ — целое число, не делящееся на $p$,
то $a^{p-1}-1$ делится на $p$,
то есть $a^{p-1}\equiv 1{\pmod {p}}$

С простыми числами все понятно

но интересно взглянуть на составные НЕЧЕТНЫЕ числа

Цитата:

для каждого составного числа $p$ вида
$p=2 \cdot i+1$
можно подобрать значение степени $\alpha$ и основание $\beta$, такие что выполнится правило
$\beta^{\alpha}\equiv 1{\pmod {p}}$

Простой способ найти $\alpha$ и $\beta$


имеем составное число
$p=\prod\limits_{i=1}^{n}(x_i)$, где $x_i>1$ и $x_i<p$ и все $x_i$ являются простыми числами

тогда
$\beta=\prod\limits_{i=1}^{n}(\frac{x_i-1}{2})$

$\alpha=3 \cdot p \cdot \beta^{2} \cdot (p \cdot \beta^{2} + 1)$


Пример

Цитата:

$p = 361583 = 23 \cdot 79 \cdot 199$

тогда

$\beta=\prod\limits_{i=1}^{n}(\frac{x_i-1}{2})=\frac{23-1}{2} \cdot \frac{79-1}{2} \cdot \frac{199-1}{2}=42471$

$\alpha=3 \cdot p \cdot \beta^{2} \cdot (p \cdot \beta^{2} + 1)=3 \cdot 361583 \cdot 42471^{2} \cdot (361583 \cdot 42471^{2} + 1) = 1276166115918637854606101742336$

$42471^{1276166115918637854606101742336}\equiv 1{\pmod {361583}}$

ПЫСЫ
- возможно это какойто очевидный бред с моей стороны, но мне это интересно :)
- возможно это изобретение велосипеда, и этот вопрос уже изучен давно, я немного малообразован, сорри, даите плиз ссылок на материалы
- возможно что вместо основания $\beta$ в конечную проверку вида $\beta^{\alpha}\equiv 1{\pmod {p}}$ можно подставить любое простое число $a$ не делящееся на $p$

[Someone]

Ascar в сообщении #1310717 писал(а):

Простой способ найти $\alpha$ и $\beta$

Теорема Эйлера.

[Ascar]

Someone в сообщении #1310718 писал(а):

Ascar в сообщении #1310717 писал(а):

Простой способ найти $\alpha$ и $\beta$

Теорема Эйлера.

функция Эйлера???? понял
мне кажется функцию Эйлера сложнее вычислить чем то что предлагаю я, у меня достаточно знать только делители, или я не прав?

-- Пн май 07, 2018 17:05:58 --

Someone в сообщении #1310718 писал(а):

Ascar в сообщении #1310717 писал(а):

Простой способ найти $\alpha$ и $\beta$

Теорема Эйлера.

о точно
значит мое выражение обладает свойством

$p=\prod\limits_{i=1}^{n}(x_i)$, где $x_i>1$ и $x_i<p$ и все $x_i$ являются простыми числами

$\beta=\prod\limits_{i=1}^{n}(\frac{x_i-1}{2})$

$\alpha=3 \cdot p \cdot \beta^{2} \cdot (p \cdot \beta^{2} + 1)$

Цитата:

$\alpha \bmod \varphi (p) = 0$

где $\varphi (p)$ - функция Эйлера

[iifat]

Ascar в сообщении #1310723 писал(а):

у меня достаточно знать только делители

Ваше «только» очаровательно, имхо.

[Ascar]

iifat в сообщении #1310752 писал(а):

Ascar в сообщении #1310723 писал(а):

у меня достаточно знать только делители

Ваше «только» очаровательно, имхо.

нет ну понятно что задачи факторизации тут не решаются :))) но если известны ВСЕ делители, легче мой метод, чем искать значение функции Эйлера?

например

$733\cdot26357\cdot33679\cdot44917=29226033732433883$

$b=366\cdot13178\cdot16839\cdot22458=1823971142824776$

$6\cdot29226033732433883\cdot1823971142824776^2\cdot(29226033732433883\cdot1823971142824776^2+1)=56723479727851618936294702853099151166133736931829541924166340006447217916101723454321294127232$

$1823971142824776^{56723479727851618936294702853099151166133736931829541924166340006447217916101723454321294127232} \bmod 29226033732433883 = 1$

блин не влазиет значение степени
56723479727851618936294702853099151166133736931829541924166340006447217916101723454321294127232

и это число делится предположительно на значение функции Эйлора для 29226033732433883 нацело

[iifat]

Ascar в сообщении #1310754 писал(а):

если известны ВСЕ делители

... то посчитать степени, как по мне, и не проблема-то вовсе. Хотя могу ошибаться. Не, не проблема-то точно, но время отнять может. Хотя, по сравнению с поиском делителей, что как раз таки проблема, — имхо, немного.

[Someone]

Ascar в сообщении #1310723 писал(а):

мне кажется функцию Эйлера сложнее вычислить чем то что предлагаю я, у меня достаточно знать только делители, или я не прав?

Если Вы знаете все делители, то Вы тем более знаете разложение на простые множители, а уж вычислить значение функции Эйлера, зная разложение — вообще не проблема. Я же ссылку на теорему Эйлера дал, а там есть ссылка на статью о функции Эйлера. А в той статье есть формула для вычисления функции Эйлера. Неужели невозможно было найти?

[Someone]

Ascar в сообщении #1310754 писал(а):

если известны ВСЕ делители, легче мой метод, чем искать значение функции Эйлера?

например

$733\cdot26357\cdot33679\cdot44917=29226033732433883$

Перечисленные множители простые, поэтому

$$\varphi(29\,226\,033\,732\,433\,883)=(733-1)(26\,357-1)(33\,679-1)(44\,917-1)=$$ $$=29\,183\,538\,285\,196\,416.$$

Сравните с вашим результатом, который

Ascar в сообщении #1310754 писал(а):

блин не влазиет значение степени

Ascar в сообщении #1310754 писал(а):

и это число делится предположительно на значение функции Эйлора для 29226033732433883 нацело

Делится, конечно. Частное равно $1\,943\,680\,686\,471\,971\,058\,000\,879\,559\,411\,890\,908\,299\,171\,337\,687\,747\,820\,216\,141\,530\,509\,128\,401\,982\,777$.

[Shadow]

Ascar в сообщении #1310717 писал(а):

можно подобрать значение степени $\alpha$ и основание $\beta$, такие что выполнится правило
$\beta^{\alpha}\equiv 1{\pmod {p}}$

Можно! Предлагаю $\beta=p+1$