Связь двух тестов простоты малой теоремы Ферма и Теста Агравала — Каяла — Саксены следствие - Алгебра - Ответ 17330193

Связь двух тестов простоты: Ма́лой теоре́мы Ферма́ и Теста Аграва́ла — Кая́ла — Саксе́ны

Связь двух тестов простоты...

Тест Аграва́ла — Кая́ла — Саксе́ны (тест AKS) — единственный известный на данный момент универсальный (то есть применимый ко всем числам) полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.

Малая теорема Ферма́ — теорема теории чисел, которая утверждает, что
Если P — простое число и a — целое число, не делящееся на P, то a^(P-1)-1 делится на P.

Для удобства работы с AKS-тестом, используем Бином Ньютона.

Пере формулировка теста простоты (истинного), при помощи
формулы бинома Ньютона
Бином Ньютона

(x+a)^p=∑_(k=0)^p▒〖(p¦k) x^k a^(p-k) 〗=∑_(k=0)^p▒P!/K!(P-K)!
Исходя из того, что, каждый биномиальный коэффициент, за исключением стоящих при наивысших степенях равных P, делится без остатка на P. Делаем вывод, что и сумма таковых делится на P без остатка.

∑_(K=1)^P▒〖(P!/K!(P-K)!〗) Mod (P)=0

Найдем сумму коэффициентов
(1+1)^p=∑_(k=0)^p▒〖(p¦k) 1^k 1^(p-k) 〗=∑_(k=0)^p▒〖P!/K!(P-K)!=2^P 〗
Поскольку биномиальные коэффициенты дублируются, имеет смысл рассматривать лишь уникальные их значения. Исходя из этого, определим их количество.

(P-1)/2 – Количество уникальных биномиальных коэффициентов(не учитывая коэффициент стоящий при наивысшей степени равной P ).
∑_(K=0)^((p-1)/2)▒〖(P!/K!(P-K)!〗) =2^(P-1)

Вычитаем коэффициент, стоящий при наивысшей степени равной P.
∑_(K=1)^((p-1)/2)▒〖(P!/K!(P-K)!)〗=2^((P-1))-1

Вывод. Сумма уникальных биномиальных коэффициентов (исключение коэффициент стоящий при наивысшей степени равной P ) (АКС теста) равна частному случаю МТФ, когда основание а = 2.

∑_(K=1)^((p-1)/2)▒〖(P!/K!(P-K)!)〗=2^((P-1))-1 mod p=0

Примеры.
P=7
∑_(K=1)^((p-1)/2)▒〖(P!/K!(P-K)!)〗=2^((P-1))-1

∑_(K=1)^((7-1)/2)▒(7!/K!(7-K)!) =

〖(7!/1!(7-1)!)+(7!/2!(7-2)!)+(7!/3!(7-3)!)=7+21+35=2〗^((7-1))-1=63
 
P=13
∑_(K=1)^((13-1)/2)▒(13!/K!(13-K)!) =

(13!/1!(13-1)!)+(13!/2!(13-2)!)+(13!/3!(13-3)!)+(13!/4!(13-4)!)+(13!/5!(13-5)!)+(13!/6!(13-6)!)=
13+78+286+715+1287+1716 =〖 2〗^((13-1))-1= 4095
Следствие:
Сумма уникальных биномиальных коэффициентов (степени простого числа) сравнима по модулю (p) с единицей.

∑_(K=0)^((p-1)/2)▒〖(P!/K!(P-K)!〗)=2^((P-1))= 1 mod p

Сумма биномиальных коэффициентов (степени простого числа) сравнима по модулю (p) с двойкой.

∑_(K=0)^p▒〖(P!/K!(P-K)!〗)=2^((P))= 2 mod p

Исходя из то, что сумма уникальных биномиальных коэффициентов (степени простого числа) сравнима по модулю (p) с единицей. Следует:
 
1) что все уникальные биномиальные коэффициенты (степени простого числа), за исключением одного, коэффициента стоящего при наивысшей степени , сравнимы по модулю (p) с нулем.

Пример

1) (P!/0!(P-0)!)= 1 mod p

(P!/K!(P-K)!)=0 mod p (при K≠0)

2) что некоторые (от двух до всех) уникальные биномиальные коэффициенты (степени псевдопростого числа, по основанию 2), после деления на псевдопростое число, имеют дробную часть, сумма которых сравнима по модулю (p) с единицей.
Пример

2) (P!/K!(P-K)!)/ P =x.33333

(P!/0!(P-0)!)/ P + (P!/5!(P-5)!)/ P ...+(P!/K!(P-K)!)/ P=1 mod p

Вернуться к обсуждению:

Связь двух тестов простоты малой теоремы Ферма и Теста Агравала — Каяла — Саксены следствие Алгебра