Тест простоты

[erwins]

Тест простоты

Проверим на делимость на 2,3,5

Если число имеет вид $p \mod 5=+1$ или $p \mod 5=-1$ тогда $r=p-1$
Если число имеет вид $p \mod 5=+2$ или $p \mod 5=-2$ тогда $r=p+1$

$F$- число Фибоначчи
Если $F_r$ mod p=0 и $F_r+1$ mod p=1
или $F_{2r}$ mod p=0 и $F_{2r}+1$ mod p=1
или $F_{4r}$ mod p=0 и $F_{4r}+1$ mod p=1

Число Фибоначчи вычислять через матрицы

Доказательство, если p простое, то r или 2r или 4r - период Пизано
см Википедию

Если p - составное и r период
1. Если составное число включает простые множители в степени более 1, то НОД(p,r)=p_1, но НОД(p,p-1)=1 и НОД(p,p+1)=1 значит все множители могут входить только в первой степени
2. Пусть $p \mod 5=\pm 1$ $h \mod 5=\pm 2$
$p_1p_2p_3p_4...h_1h_2h_3h_4...-1=(p_1-1)(p_2-1)(p_3-1)(p_4-1)...(h_1+1)(h_2+1)(h_3+1)(h_4+1)....$
Число множителей p нечетное

Доказательство
рассмотрим выражение по модулю p_1
в левой части -1 в правой части все параметры не кратны p_1
Возьмем последовательно правую и левую часть по модулю p_1 p_2 .... h_1 h_2
тогда $-1= (-1)^{Число множителей p}$

$(p_1-1)(p_2-1)(p_3-1)(p_4-1)...(h_1+1)(h_2+1)(h_3+1)(h_4+1)....$ взаимнопросты с $p_1 , p_2 ... h_1, h_2$

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы недооформлены $\TeX$ом, несколько обрывочный текст

erwins
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
Тема будет перемещена в дискуссионный раздел, потому дополните текст так, чтобы он не был обрывочным, сформулируйте доказываемые утверждения целиком и явно.

erwins в сообщении #886419 писал(а):

Если $F_r$ mod p=0 и $F_r+1$ mod p=1
или $F_{2r}$ mod p=0 и $F_{2r}+1$ mod p=1
или $F_{4r}$ mod p=0 и $F_{4r}+1$ mod p=1

"Если $X$, то".

erwins в сообщении #886419 писал(а):

см Википедию

Укажите ссылку, это нетрудно.

erwins в сообщении #886419 писал(а):

Если составное число включает простые множители в степени более 1, то НОД(p,r)=p_1, но НОД(p,p-1)=1 и НОД(p,p+1)=1 значит все множители могут входить только в первой степени

О каком составном числе идёт речь? В посылке о нём говорится, а в следствии - нет.

И т.п.

После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.