Псевдопросте число: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
Вилучено вміст Додано вміст
Створено шляхом перекладу сторінки «Псевдопростое число»
 
Немає опису редагування
Рядок 1: Рядок 1:
'''Псевдопростое число''' — [[Натуральні числа|натуральне число]], що має деякі властивості [[Просте число|простих чисел]], але при цьому є [[Складене число|складеним]]. Залежно від розглянутих властивостей існує кілька типів псевдопростих чисел.
'''Псевдопросте число''' — [[Натуральні числа|натуральне число]], що має деякі властивості [[Просте число|простих чисел]], але при цьому є [[Складене число|складеним]]. Залежно від розглянутих властивостей існує кілька типів псевдопростих чисел.


Існування псевдопростих є перешкодою для [[Тест простоти|перевірок простоти]], які намагаються використовувати ті чи інші властивості простих чисел для визначення простоти даного числа.
Існування псевдопростих є перешкодою для [[Тест простоти|перевірок простоти]], які намагаються використовувати ті чи інші властивості простих чисел для визначення простоти даного числа.
Рядок 8: Рядок 8:
Псевдопрості Ферма за основою 2 утворюють послідовність:
Псевдопрості Ферма за основою 2 утворюють послідовність:


: 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, ... ({{OEIS|A001567}})
: 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, ({{OEIS|A001567}})


а за основою 3 — послідовність:
а за основою 3 — послідовність:


: 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, ... ({{OEIS|A005935}})
: 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, ({{OEIS|A005935}})


Число, що є псевдопрости Ферма за кожною [[Взаємно прості числа|взаємно простою]] з ним основою, називається [[Число Кармайкла|числом Кармайкла]].
Число, що є псевдопрости Ферма за кожною [[Взаємно прості числа|взаємно простою]] з ним основою, називається [[Число Кармайкла|числом Кармайкла]].


== Псевдопрості Ейлера — Якобі ==
== Псевдопрості Ейлера — Якобі ==
Непарне складене число ''n'' називається '''псевдопростим Ейлера — Якобі''' за основою ''a'', якщо воно задовольняє [[Модульна арифметика#Рівність за модулем|порівнянню]]<ref>{{MathWorld|urlname=Euler-JacobiPseudoprime|title=Euler-Jacobi Pseudoprime}}</ref>
Непарне складене число ''n'' називається '''псевдопростим Ейлера&nbsp;— Якобі''' за основою ''a'', якщо воно задовольняє [[Модульна арифметика#Рівність за модулем|порівнянню]]<ref>{{MathWorld|urlname=Euler-JacobiPseudoprime|title=Euler-Jacobi Pseudoprime}}</ref>


: <math>a^{(n-1)/2} \equiv \left( \frac{a}{n} \right) \pmod{n},</math>
: <math>a^{(n-1)/2} \equiv \left( \frac{a}{n} \right) \pmod{n},</math>


де <math>\left( \frac{a}{n} \right)</math> — [[символ Якобі]]. Оскільки з цього порівняння випливає, що <math>a^{n-1} \equiv 1\pmod{n},</math> то будь-яке псевдопросте Ейлера — Якобі також є псевдопростим Ферма (за тією ж основою).
де <math>\left( \frac{a}{n} \right)</math>&nbsp;— [[символ Якобі]]. Оскільки з цього порівняння випливає, що <math>a^{n-1} \equiv 1\pmod{n},</math> то будь-яке псевдопросте Ейлера&nbsp;— Якобі також є псевдопростим Ферма (за тією ж основою).


Псевдопрості Ейлера — Якобі за основою 2 утворюють послідовність:
Псевдопрості Ейлера&nbsp;— Якобі за основою 2 утворюють послідовність:


: 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, ... ({{OEIS|A047713}})
: 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, ({{OEIS|A047713}})


а за основою 3 — послідовність:
а за основою 3&nbsp;— послідовність:


: 121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, ... ({{OEIS|A048950}})
: 121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, ({{OEIS|A048950}})


== Псевдопрості Фібоначчі ==
== Псевдопрості Фібоначчі ==
Рядок 56: Рядок 56:
: <math> (-1)^{\frac{n-1}{2}} \cdot C_{\frac{n-1}{2}} \equiv 2 \pmod n,</math>
: <math> (-1)^{\frac{n-1}{2}} \cdot C_{\frac{n-1}{2}} \equiv 2 \pmod n,</math>


де ''C<sub>m</sub>'' — ''m''-те [[число Каталана]]. Порівняння істинне для будь-якого непарного [[Просте число|простого числа]] ''n''.
де ''C<sub>m</sub>''&nbsp;— ''m''-те [[число Каталана]]. Порівняння істинне для будь-якого непарного [[Просте число|простого числа]] ''n''.


Відомо тільки три псевдопростих числа Каталана: 5907, 1194649, і 12327121 ({{OEIS|A163209}}), причому два останніх з них є квадратами [[Просте число Віфериха|простих чисел Віфериха]]. У загальному випадку, якщо ''p'' — просте число Віфериха, то ''p''<sup>2</sup> — псевдопросте Каталана.
Відомо тільки три псевдопростих числа Каталана: 5907, 1194649, і 12327121 ({{OEIS|A163209}}), причому два останніх з них є квадратами [[Просте число Віфериха|простих чисел Віфериха]]. У загальному випадку, якщо ''p''&nbsp;— просте число Віфериха, то ''p''<sup>2</sup>&nbsp;— псевдопросте Каталана.


== Див. також ==
== Див. також ==

* [[Тест Соловея — Штрассена]]
* [[Тест Соловея — Штрассена]]
* [[Тест простоти Міллера–Рабіна|Тест Міллера — Рабіна]]
* [[Тест простоти Міллера–Рабіна|Тест Міллера&nbsp;— Рабіна]]
* [[Сильне псевдопросте число]]
* [[Сильне псевдопросте число]]
* [[Псевдопрості числа Ферма]]
* [[Псевдопрості числа Ферма]]
Рядок 71: Рядок 70:


== Посилання ==
== Посилання ==

* {{Стаття|title=Catalan numbers, primes and twin primes|видання={{Нп3|Elemente der Mathematik}}|том=63|номер=4|pages=153—164|url=http://gradelle.educanet2.ch/christian.aebi/.ws_gen/9/catalan.pdf|doi=10.4171/EM/103|language=und|author=Aebi, C.; Cairns, G.|date=2008}}
* {{Стаття|title=Catalan numbers, primes and twin primes|видання={{Нп3|Elemente der Mathematik}}|том=63|номер=4|pages=153—164|url=http://gradelle.educanet2.ch/christian.aebi/.ws_gen/9/catalan.pdf|doi=10.4171/EM/103|language=und|author=Aebi, C.; Cairns, G.|date=2008}}
* [http://compmath.wordpress.com/catalan-pseudoprimes/ Catalan pseudoprimes]. Research in Scientific Computing in Undergraduate Education.
* [http://compmath.wordpress.com/catalan-pseudoprimes/ Catalan pseudoprimes]. Research in Scientific Computing in Undergraduate Education.

Версія за 13:24, 10 січня 2021

Псевдопросте число — натуральне число, що має деякі властивості простих чисел, але при цьому є складеним. Залежно від розглянутих властивостей існує кілька типів псевдопростих чисел.

Існування псевдопростих є перешкодою для перевірок простоти, які намагаються використовувати ті чи інші властивості простих чисел для визначення простоти даного числа.

Псевдопрості Ферма

Складене число n називається псевдопростим Ферма за основою a, якщо a та n взаємно прості й .[1]

Псевдопрості Ферма за основою 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]

де  — символ Якобі. Оскільки з цього порівняння випливає, що то будь-яке псевдопросте Ейлера — Якобі також є псевдопростим Ферма (за тією ж основою).

Псевдопрості Ейлера — Якобі за основою 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).[3]

Псевдопрості Каталана

Непарне складене число n, що задовольняє порівнянню

де Cm — m-те число Каталана. Порівняння істинне для будь-якого непарного простого числа n.

Відомо тільки три псевдопростих числа Каталана: 5907, 1194649, і 12327121 (послідовність A163209 з Онлайн енциклопедії послідовностей цілих чисел, OEIS), причому два останніх з них є квадратами простих чисел Віфериха. У загальному випадку, якщо p — просте число Віфериха, то p2 — псевдопросте Каталана.

Див. також

Примітки

  1. Weisstein, Eric W. Fermat Pseudoprime(англ.) на сайті Wolfram MathWorld.
  2. Weisstein, Eric W. Euler-Jacobi Pseudoprime(англ.) на сайті Wolfram MathWorld.
  3. Jon Grantham. Frobenius pseudoprimes // Mathematics of Computation[en] : journal. — 2001. — Vol. 70, no. 234 (28 March). — P. 873—891. — DOI:10.1090/S0025-5718-00-01197-2.

Посилання