Псевдопросте число — натуральне число, що має деякі властивості простих чисел, але при цьому є складеним. Залежно від розглянутих властивостей існує кілька типів псевдопростих чисел.
Існування псевдопростих є перешкодою для перевірок простоти, які намагаються використовувати ті чи інші властивості простих чисел для визначення простоти даного числа.
Псевдопрості Ферма
Складене число n називається псевдопростим Ферма за основою a, якщо a та n взаємно прості й .
Псевдопрості Ферма за основою 2 утворюють послідовність:
- 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, … (послідовність A001567 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)
а за основою 3 — послідовність:
- 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, … (послідовність A005935 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)
Число, що є псевдопрости Ферма за кожною взаємно простою з ним основою, називається числом Кармайкла.
Псевдопрості Ейлера — Якобі
Непарне складене число n називається псевдопростим Ейлера — Якобі за основою a, якщо воно задовольняє (порівнянню)
де — символ Якобі. Оскільки з цього порівняння випливає, що то будь-яке псевдопросте Ейлера — Якобі також є псевдопростим Ферма (за тією ж основою).
Псевдопрості Ейлера — Якобі за основою 2 утворюють послідовність:
- 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, … (послідовність A047713 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)
а за основою 3 — послідовність:
- 121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, … (послідовність A048950 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)
Псевдопрості Фібоначчі
Псевдопрості Люка
Псевдопрості Перрена
Складене число q називається псевдопростим Перрена, якщо воно ділить q-е число Перрена P(q), що задається рекуррентним співвідношенням:
- P(0) = 3, P(1) = 0, P(2) = 2,
і
- P(n) = P(n − 2) + P(n − 3) для n > 2.
Псевдопрості Фробеніуса
Псевдопросте число, що пройшло трикроковий тест належності до ймовірно простих чисел, розроблений 1996 року (Jon Grantham).
Псевдопрості Каталана
Непарне складене число n, що задовольняє порівнянню
де Cm — m-те число Каталана. Порівняння істинне для будь-якого непарного простого числа n.
Відомо тільки три псевдопростих числа Каталана: 5907, 1194649, і 12327121 (послідовність A163209 з Онлайн енциклопедії послідовностей цілих чисел, OEIS), причому два останніх з них є квадратами . У загальному випадку, якщо p — просте число Віфериха, то p2 — псевдопросте Каталана.
Див. також
Примітки
Посилання
- Aebi, C.; Cairns, G. Catalan numbers, primes and twin primes // [en]. — 2008. — Т. 63, № 4 (4 July). — С. 153—164. — DOI: .
- Catalan pseudoprimes. Research in Scientific Computing in Undergraduate Education.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Psevdoproste chislo naturalne chislo sho maye deyaki vlastivosti prostih chisel ale pri comu ye skladenim Zalezhno vid rozglyanutih vlastivostej isnuye kilka tipiv psevdoprostih chisel Isnuvannya psevdoprostih ye pereshkodoyu dlya perevirok prostoti yaki namagayutsya vikoristovuvati ti chi inshi vlastivosti prostih chisel dlya viznachennya prostoti danogo chisla Psevdoprosti FermaSkladene chislo n nazivayetsya psevdoprostim Ferma za osnovoyu a yaksho a ta n vzayemno prosti j an 1 1 modn displaystyle a n 1 equiv 1 pmod n Psevdoprosti Ferma za osnovoyu 2 utvoryuyut poslidovnist 341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 poslidovnist A001567 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS a za osnovoyu 3 poslidovnist 91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 poslidovnist A005935 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Chislo sho ye psevdoprosti Ferma za kozhnoyu vzayemno prostoyu z nim osnovoyu nazivayetsya chislom Karmajkla Psevdoprosti Ejlera YakobiNeparne skladene chislo n nazivayetsya psevdoprostim Ejlera Yakobi za osnovoyu a yaksho vono zadovolnyaye porivnyannyu a n 1 2 an modn displaystyle a n 1 2 equiv left frac a n right pmod n de an displaystyle left frac a n right simvol Yakobi Oskilki z cogo porivnyannya viplivaye sho an 1 1 modn displaystyle a n 1 equiv 1 pmod n to bud yake psevdoproste Ejlera Yakobi takozh ye psevdoprostim Ferma za tiyeyu zh osnovoyu Psevdoprosti Ejlera Yakobi za osnovoyu 2 utvoryuyut poslidovnist 561 1105 1729 1905 2047 2465 3277 4033 4681 6601 8321 8481 10585 poslidovnist A047713 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS a za osnovoyu 3 poslidovnist 121 703 1729 1891 2821 3281 7381 8401 8911 10585 12403 15457 15841 poslidovnist A048950 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Psevdoprosti FibonachchiDokladnishe Psevdoprosti LyukaDokladnishe Psevdoprosti PerrenaSkladene chislo q nazivayetsya psevdoprostim Perrena yaksho vono dilit q e chislo Perrena P q sho zadayetsya rekurrentnim spivvidnoshennyam P 0 3 P 1 0 P 2 2 i P n P n 2 P n 3 dlya n gt 2 Psevdoprosti FrobeniusaPsevdoproste chislo sho projshlo trikrokovij test nalezhnosti do jmovirno prostih chisel rozroblenij 1996 roku Jon Grantham Psevdoprosti KatalanaNeparne skladene chislo n sho zadovolnyaye porivnyannyu 1 n 12 Cn 12 2 modn displaystyle 1 frac n 1 2 cdot C frac n 1 2 equiv 2 pmod n de Cm m te chislo Katalana Porivnyannya istinne dlya bud yakogo neparnogo prostogo chisla n Vidomo tilki tri psevdoprostih chisla Katalana 5907 1194649 i 12327121 poslidovnist A163209 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS prichomu dva ostannih z nih ye kvadratami U zagalnomu vipadku yaksho p proste chislo Viferiha to p2 psevdoproste Katalana Div takozhTest Soloveya Shtrassena Test Millera Rabina Silne psevdoproste chisloPrimitkiWeisstein Eric W Fermat Pseudoprime angl na sajti Wolfram MathWorld Weisstein Eric W Euler Jacobi Pseudoprime angl na sajti Wolfram MathWorld Jon Grantham Frobenius pseudoprimes en journal 2001 Vol 70 no 234 4 July P 873 891 DOI 10 1090 S0025 5718 00 01197 2 PosilannyaAebi C Cairns G Catalan numbers primes and twin primes en 2008 T 63 4 4 July S 153 164 DOI 10 4171 EM 103 Catalan pseudoprimes Research in Scientific Computing in Undergraduate Education