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

тип чисел у математиці
[перевірена версія][перевірена версія]
(Створено шляхом перекладу сторінки «Псевдопростое число»)
 
 
(Не показано одну проміжну версію цього користувача)
Рядок 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:28, 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 (23 June). — P. 873—891. — DOI:10.1090/S0025-5718-00-01197-2.

ПосиланняРедагувати