Протоздар теоремасы - Proths theorem - Wikipedia

Жылы сандар теориясы, Прот теоремасы Бұл бастапқы тест үшін Проток сандары.

Онда айтылған^[1][2] егер болса б Бұл Прот нөмірі, форманың к2ⁿ + 1 бірге к тақ және к < 2ⁿжәне егер бар болса бүтін а ол үшін

${ displaystyle a ^ { frac {p-1} {2}} equiv -1 { pmod {p}},}$

содан кейін б болып табылады қарапайым. Бұл жағдайда б а деп аталады Proth prime. Бұл практикалық тест, өйткені егер б ең жақсы, кез келген таңдалған а жұмыс істеу мүмкіндігі шамамен 50 пайызды құрайды.

Егер а Бұл квадраттық емес қалдық модуль б онда керісінше шындық, ал тест қорытынды болып табылады. Мұндай а қайталау арқылы табылуы мүмкін а кішігірім қарапайым және есептеу Якоби символы дейін:

${ displaystyle left ({ frac {a} {p}} right) = - 1.}$

Осылайша, көптеген айырмашылығы Монте-Карло бастапқы тесттер (а-ны қайтара алатын рандомизацияланған алгоритмдер жалған оң ), Proth теоремасына негізделген алғашқы тестілеу алгоритмі a Лас-Вегас алгоритмі, әрқашан дұрыс жауапты қайтарады, бірақ жұмыс уақыты кездейсоқ өзгереді.

Сандық мысалдар

Теореманың мысалдары:

• үшін б = 3 = 1(2¹) + 1, бізде 2 бар^(3-1)/2 + 1 = 3 3-ке бөлінеді, сондықтан 3 жай санға тең.
• үшін б = 5 = 1(2²) + 1, бізде 3 бар^(5-1)/2 + 1 = 10 5-ке бөлінеді, сондықтан 5 жай санға тең.
• үшін б = 13 = 3(2²) + 1, бізде 5 бар^(13-1)/2 + 1 = 15626 13-ке бөлінеді, сондықтан 13 жай.
• үшін б = 9, бұл жай емес, жоқ а осындай а^(9-1)/2 + 1 9-ға бөлінеді.

Бірінші Proth жай сандары: (реттілік) A080076 ішінде OEIS ):

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….

2016 жылғы ең танымал Proth prime^{[жаңарту]} болып табылады ${ displaystyle 10223 cdot 2 ^ {31172165} +1}$, және ұзындығы 9 383 761 цифрдан тұрады.^[3] Оны Питер Саболч тапқан PrimeGrid таратылған есептеу жобасы бұл туралы 2016 жылдың 6 қарашасында жариялады.^[4] Бұл сондай-ақ белгілі ең іріMersenne прайм және ең үлкен Колбер саны.^[5] Прот премьерінің екінші үлкені - бұл ${ displaystyle 19249 cdot 2 ^ {13018586} +1}$, табылған Он жеті немесе бюст.^[6]

Дәлел

Бұл теореманың дәлелі Поклингтон-Леммердің алғашқы сынағы, және дәлелі ұқсас Пепиннің сынағы. Дәлелді Рибенбойм кітабының 52-бетінде сілтемелерден табуға болады.

Тарих

Франсуа Прот (1852–1879) теоремасын 1878 жылы жариялады.^[7][8]

Сондай-ақ қараңыз

• Пепиннің сынағы (ерекше жағдай к = 1, мұнда біреу таңдайды а = 3)
• Sierpinski нөмірі

Әдебиеттер тізімі

Сыртқы сілтемелер

• Вайсштейн, Эрик В. «Прот теоремасы». MathWorld.