فيرما شبه الأولي

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 32 صور
الموسوعة الحرة

في نظرية الأعداد ، تشكل الأعداد الأولية الزائفة لفيرما أهم فئة من الأعداد الأولية الزائفة التي تأتي من نظرية فيرما الصغيرة .

تعريف

تنص نظرية فيرما الصغيرة على أنه إذاص{\displaystyle p}هو عدد أولي وأ{\displaystyle a}هو عدد أولي نسبيًا لـص{\displaystyle p}، ثمأص-1-1{\displaystyle a^{p-1}-1}يقبل القسمة علىص{\displaystyle p}بالنسبة لعدد صحيح موجبأ{\displaystyle a}، إذا كان عددًا صحيحًا مركبًاx{\displaystyle x}يقسمأx-1-1{\displaystyle a^{x-1}-1}ثمx{\displaystyle x}يُطلق عليه اسم عدد فيرما شبه الأولي للأساسأ{\displaystyle a}[ 1 ] : التعريف 3.32

بمعنى آخر، العدد الصحيح المركب هو عدد أولي زائف من نوع فيرما للأساسأ{\displaystyle a}إذا اجتاز بنجاح اختبار فيرما للأعداد الأولية للأساسأ{\displaystyle a}[ 2 ] يُطلق على البيان الخاطئ القائل بأن جميع الأعداد التي تجتاز اختبار فيرما للأعداد الأولية للأساس 2 هي أعداد أولية اسم الفرضية الصينية .

أصغر عدد أولي زائف لفيرما في النظام الثنائي هو 341. وهو ليس عددًا أوليًا، لأنه يساوي 11 × 31، ولكنه يحقق نظرية فيرما الصغرى:2340≡1(تعديل341){\displaystyle 2^{340}\equiv 1({\bmod {341}})}وبالتالي يجتاز اختبار فيرما للأعداد الأولية للأساس 2.

تُسمى الأعداد الأولية الزائفة ذات الأساس 2 أحيانًا بأعداد ساروس ، نسبة إلى بي إف ساروس الذي اكتشف أن 341 له هذه الخاصية، أو بأعداد بوليه ، نسبة إلى بي بوليه الذي وضع جدولًا لهذه الأعداد، أو بأعداد فيرما (المتتالية A001567 في OEIS ) .

يُطلق على العدد الأولي الزائف لفيرما غالبًا اسم العدد الأولي الزائف ، مع فهم مُعدِّل فيرما بشكل ضمني.

عدد صحيحx{\displaystyle x}هذا عدد أولي زائف لفيرما لجميع قيمأ{\displaystyle a}التي هي أولية فيما بينها لـx{\displaystyle x}يُطلق عليه اسم عدد كارمايكل . [ 2 ] [ 1 ] : التعريف 3.34

ملكيات

توزيع

يوجد عدد لا نهائي من الأعداد الأولية الزائفة لأي أساس معينأ>1{\displaystyle a>1}في عام 1904، أوضح سيبولا كيفية إنتاج عدد لا نهائي من الأعداد الأولية الزائفة للأساسأ>1{\displaystyle a>1}: يتركأ=(أص-1)/(أ-1){\displaystyle A=(a^{p}-1)/(a-1)}ودعب=(أص+1)/(أ+1){\displaystyle B=(a^{p}+1)/(a+1)}، أينص{\displaystyle p}هو عدد أولي لا يقبل القسمةأ(أ2-1){\displaystyle a(a^{2}-1)}. ثمن=أب{\displaystyle n=AB}هو عدد مركب، وهو عدد أولي زائف بالنسبة للأساسأ{\displaystyle a}[ 3 ] [ 4 ] على سبيل المثال، إذاأ=2{\displaystyle a=2}وص=5{\displaystyle p=5}، ثمأ=31{\displaystyle A=31}،ب=11{\displaystyle B=11}، ون=أب=341{\displaystyle n=AB=341}هو عدد أولي زائف بالنسبة للأساس2{\displaystyle 2}.

في الواقع، يوجد عدد لا نهائي من الأعداد شبه الأولية القوية لأي أساس أكبر من 1 (انظر النظرية 1 من [ 5 ] )، وعدد لا نهائي من أعداد كارمايكل [ 6 ] ، لكنها نادرة نسبيًا. يوجد ثلاثة أعداد شبه أولية للأساس 2 أقل من 1000، و245 عددًا أقل من مليون، و21853 عددًا أقل من 25 × 10⁹ . يوجد 4842 عددًا شبه أوليًا قويًا للأساس 2 و2163 عددًا من أعداد كارمايكل أقل من هذا الحد (انظر الجدول 1 من [ 5 ] ).

ابتداءً من 17.257، يكون ناتج أعداد فيرما المتتالية عددًا أوليًا زائفًا أساسه 2، وكذلك جميع مركبات فيرما ومركبات ميرسين .

إن احتمال نجاح عدد مركب n في اختبار فيرما يقترب من الصفر عندمان→∞{\displaystyle n\to \infty }على وجه التحديد، أظهر كيم وبوميرانس ما يلي: احتمال أن يكون عدداً فردياً عشوائياً ن≤x{\displaystyle n\leq x}هو عدد أولي زائف من نوع فيرما لأساس عشوائي1<ب<ن-1{\displaystyle 1<b<n-1}تكون أقل من 2.77 × 10⁻⁸ عندما x = 10¹⁰⁰ ، وتكون على الأكثر (log x) ⁻¹⁹⁷ < 10⁻¹⁰⁰⁰⁰ عندما x ≥ 10¹⁰⁰⁰⁰⁰ . [ 7 ] بالنسبة لأساس ثابت b، فإن نسبة الأعداد الأولية الزائفة حتى x تكون على الأكثر e -log x log log log x/(2 log log x) لقيم x الكبيرة. [ 8 ]

التحليل إلى عوامل

توجد في الجدول التالي تحليلات الأعداد الستين من Poulet حتى 60787، بما في ذلك 13 عددًا من أعداد Carmichael (بالخط العريض).

(التسلسل A001567 في OEIS )

الدجاج من 1 إلى 15
34111 · 31
5613 · 11 · 17
6453 · 5 · 43
11055 · 13 · 17
138719 · 73
17297 · 13 · 19
19053 · 5 · 127
204723 · 89
24655 · 17 · 29
270137 · 73
28217 · 13 · 31
327729 · 113
403337 · 109
436917 · 257
43713 · 31 · 47
دجاج من 16 إلى 30
468131 · 151
546143 · 127
66017 · 23 · 41
795773 · 109
832153 · 157
84813 · 11 · 257
89117 · 19 · 67
1026131 · 331
105855 · 29 · 73
113055 · 7 · 17 · 19
128013 · 17 · 251
137417 · 13 · 151
1374759 · 233
1398111 · 31 · 41
1449143 · 337
دجاج من 31 إلى 45
1570923 · 683
158417 · 31 · 73
167055 · 13 · 257
187053 · 5 · 29 · 43
1872197 · 193
1995171 · 281
230013 · 11 · 17 · 41
2337797 · 241
257613 · 31 · 277
2934113 · 37 · 61
301217 · 13 · 331
3088917 · 23 · 79
3141789 · 353
3160973 · 433
31621103 · 307
دجاج من 46 إلى 60
331533 · 43 · 257
349455 · 29 · 241
3533389 · 397
398655 · 7 · 17 · 67
410417 · 11 · 13 · 41
416655 · 13 · 641
42799127 · 337
4665713 · 37 · 97
49141157 · 313
49981151 · 331
526337 · 73 · 103
552453 · 5 · 29 · 127
574217 · 13 · 631
60701101 · 601
6078789 · 683

يُطلق على عدد بوليه الذي تقسم جميع قواسمه d العدد 2d - 2 اسم عدد بوليه الفائق . يوجد عدد لا نهائي من أعداد بوليه التي لا تُصنّف كأعداد بوليه فائقة. [ 9 ]

أصغر أعداد فيرما الأولية الزائفة

يُبيّن الجدول التالي أصغر عدد شبه أولي لكل أساس a ≤ 200؛ وتشير الألوان إلى عدد العوامل الأولية. وخلافًا للتعريف الوارد في بداية المقال، فإن الأعداد شبه الأولية التي تقل عن a مستبعدة من الجدول. (للسماح بالأعداد شبه الأولية التي تقل عن a ، انظر (التسلسل A090086 في OEIS ) ).

(التسلسل A007535 في OEIS )

أأصغر صفحةأأصغر صفحةأأصغر صفحةأأصغر صفحة
14 = 2²5165 = 5 × 13101175 = 5² × 7151175 = 5² × 7
2341 = 11 × 315285 = 5 × 17102133 = 7 × 19152153 = 3² × 17
391 = 7 × 135365 = 5 × 13103133 = 7 × 19153209 = 11 × 19
415 = 3 × 55455 = 5 × 11104105 = 3 × 5 × 7154155 = 5 × 31
5124 = 2² × 315563 = 3² × 7105451 = 11 × 41155231 = 3 × 7 × 11
635 = 5 × 75657 = 3 × 19106133 = 7 × 19156217 = 7 × 31
725 = 5²5765 = 5 × 13107133 = 7 × 19157186 = 2 × 3 × 31
89 = 3²58133 = 7 × 19108341 = 11 × 31158159 = 3 × 53
928 = 2² × 75987 = 3 × 29109117 = 3² × 13159247 = 13 × 19
1033 = 3 × 1160341 = 11 × 31110111 = 3 × 37160161 = 7 × 23
1115 = 3 × 56191 = 7 × 13111190 = 2 × 5 × 19161190 = 2 × 5 × 19
1265 = 5 × 136263 = 3² × 7112121 = 11²162481 = 13 × 37
1321 = 3 × 763341 = 11 × 31113133 = 7 × 19163186 = 2 × 3 × 31
1415 = 3 × 56465 = 5 × 13114115 = 5 × 23164165 = 3 × 5 × 11
15341 = 11 × 3165112 = 2⁴ × 7115133 = 7 × 19165172 = 2² × 43
1651 = 3 × 176691 = 7 × 13116117 = 3² × 13166301 = 7 × 43
1745 = 3² × 56785 = 5 × 17117145 = 5 × 29167231 = 3 × 7 × 11
1825 = 5²6869 = 3 × 23118119 = 7 × 17168169 = 13²
1945 = 3² × 56985 = 5 × 17119177 = 3 × 59169231 = 3 × 7 × 11
2021 = 3 × 770169 = 13²120121 = 11²170171 = 3² × 19
2155 = 5 × 1171105 = 3 × 5 × 7121133 = 7 × 19171215 = 5 × 43
2269 = 3 × 237285 = 5 × 17122123 = 3 × 41172247 = 13 × 19
2333 = 3 × 1173111 = 3 × 37123217 = 7 × 31173205 = 5 × 41
2425 = 5²7475 = 3 × 5²124125 = 5³174175 = 5² × 7
2528 = 2² × 77591 = 7 × 13125133 = 7 × 19175319 = 11 × 19
2627 = 3³7677 = 7 × 11126247 = 13 × 19176177 = 3 × 59
2765 = 5 × 1377247 = 13 × 19127153 = 3² × 17177196 = 2² × 7²
2845 = 3² × 578341 = 11 × 31128129 = 3 × 43178247 = 13 × 19
2935 = 5 × 77991 = 7 × 13129217 = 7 × 31179185 = 5 × 37
3049 = 7²8081 = 3⁴130217 = 7 × 31180217 = 7 × 31
3149 = 7²8185 = 5 × 17131143 = 11 × 13181195 = 3 × 5 × 13
3233 = 3 × 118291 = 7 × 13132133 = 7 × 19182183 = 3 × 61
3385 = 5 × 1783105 = 3 × 5 × 7133145 = 5 × 29183221 = 13 × 17
3435 = 5 × 78485 = 5 × 17134135 = 3³ × 5184185 = 5 × 37
3551 = 3 × 1785129 = 3 × 43135221 = 13 × 17185217 = 7 × 31
3691 = 7 × 138687 = 3 × 29136265 = 5 × 53186187 = 11 × 17
3745 = 3² × 58791 = 7 × 13137148 = 2² × 37187217 = 7 × 31
3839 = 3 × 138891 = 7 × 13138259 = 7 × 37188189 = 3³ × 7
3995 = 5 × 198999 = 3² × 11139161 = 7 × 23189235 = 5 × 47
4091 = 7 × 139091 = 7 × 13140141 = 3 × 47190231 = 3 × 7 × 11
41105 = 3 × 5 × 791115 = 5 × 23141355 = 5 × 71191217 = 7 × 31
42205 = 5 × 419293 = 3 × 31142143 = 11 × 13192217 = 7 × 31
4377 = 7 × 1193301 = 7 × 43143213 = 3 × 71193276 = 2² × 3 × 23
4445 = 3² × 59495 = 5 × 19144145 = 5 × 29194195 = 3 × 5 × 13
4576 = 2² × 1995141 = 3 × 47145153 = 3² × 17195259 = 7 × 37
46133 = 7 × 1996133 = 7 × 19146147 = 3 × 7²196205 = 5 × 41
4765 = 5 × 1397105 = 3 × 5 × 7147169 = 13²197231 = 3 × 7 × 11
4849 = 7²9899 = 3² × 11148231 = 3 × 7 × 11198247 = 13 × 19
4966 = 2 × 3 × 1199145 = 5 × 29149175 = 5² × 7199225 = 3² × 5²
5051 = 3 × 17100153 = 3² × 17150169 = 13²200201 = 3 × 67

قائمة الأعداد الأولية الزائفة لفيرما في أساس ثابت n

نالأعداد الأولية الزائفة القليلة الأولى لفيرما في الأساس nتسلسل OEIS
14، 6، 8، 9، 10، 12، 14، 15، 16، 18، 20، 21، 22، 24، 25، 26، 27، 28، 30، 32، 33، 34، 35، 36، 38، 39، 40، 42، 44، 45، 46، 48، 49، 50، 51، 52، 54، 55، 56، 57، 58، 60، 62، 63، 64، 65، 66، 68، 69، 70، 72، 74، 75، 76، 77، 78، 80، 81، 82، 84، 85، 86 87، 88، 90، 91، 92، 93، 94، 95، 96، 98، 99، 100، ... (جميع المركبات)A002808
2341، 561، 645، 1105، 1387، 1729، 1905، 2047، 2465، 2701، 2821، 3277، 4033، 4369، 4371، 4681، 5461، 6601، 7957، 8321، 8481، 8911، ...A001567
391، 121، 286، 671، 703، 949، 1105، 1541، 1729، 1891، 2465، 2665، 2701، 2821، 3281، 3367، 3751، 4961، 5551، 6601، 7381، 8401، 8911، ...A005935
415، 85، 91، 341، 435، 451، 561، 645، 703، 1105، 1247، 1271، 1387، 1581، 1695، 1729، 1891، 1905، 2047، 2071، 2465، 2701، 2821، 3133، 3277، 3367، 3683، 4033، 4369، 4371، 4681، 4795، 4859، 5461، 5551، 6601، 6643، 7957، 8321، 8481، 8695، 8911، 9061، 9131، 9211، 9605، 9919، ...A020136
54، 124، 217، 561، 781، 1541، 1729، 1891، 2821، 4123، 5461، 5611، 5662، 5731، 6601، 7449، 7813، 8029، 8911، 9881، ...A005936
635، 185، 217، 301، 481، 1105، 1111، 1261، 1333، 1729، 2465، 2701، 2821، 3421، 3565، 3589، 3913، 4123، 4495، 5713، 6533، 6601، 8029، 8365، 8911، 9331، 9881، ...A005937
76، 25، 325، 561، 703، 817، 1105، 1825، 2101، 2353، 2465، 3277، 4525، 4825، 6697، 8321، ...A005938
89، 21، 45، 63، 65، 105، 117، 133، 153، 231، 273، 341، 481، 511، 561، 585، 645، 651، 861، 949، 1001، 1105، 1281، 1365، 1387، 1417، 1541، 1649، 1661، 1729، 1785، 1905، 2047، 2169، 2465، 2501، 2701، 2821، 3145، 3171، 3201، 3277، 3605، 3641، 4005، 4033، 4097، 4369، 4371، 4641، 4681، 4921، 5461، 5565، 5963، 6305، 6533، 6601، 6951، 7107، 7161، 7957، 8321، 8481، 8911، 9265، 9709، 9773، 9881، 9945، ...A020137
94، 8، 28، 52، 91، 121، 205، 286، 364، 511، 532، 616، 671، 697، 703، 946، 949، 1036، 1105، 1288، 1387، 1541، 1729، 1891، 2465، 2501، 2665، 2701، 2806، 2821، 2926، 3052، 3281، 3367، 3751، 4376، 4636، 4961، 5356، 5551، 6364، 6601، 6643، 7081، 7381، 7913، 8401، 8695، 8744، 8866، 8911، ...A020138
109، 33، 91، 99، 259، 451، 481، 561، 657، 703، 909، 1233، 1729، 2409، 2821، 2981، 3333، 3367، 4141، 4187، 4521، 5461، 6533، 6541، 6601، 7107، 7471، 7777، 8149، 8401، 8911، ...A005939
1110، 15، 70، 133، 190، 259، 305، 481، 645، 703، 793، 1105، 1330، 1729، 2047، 2257، 2465، 2821، 4577، 4921، 5041، 5185، 6601، 7869، 8113، 8170، 8695، 8911، 9730، ...A020139
1265، 91، 133، 143، 145، 247، 377، 385، 703، 1045، 1099، 1105، 1649، 1729، 1885، 1891، 2041، 2233، 2465، 2701، 2821، 2983، 3367، 3553، 5005، 5365، 5551، 5785، 6061، 6305، 6601، 8911، 9073، ...A020140
134، 6، 12، 21، 85، 105، 231، 244، 276، 357، 427، 561، 1099، 1785، 1891، 2465، 2806، 3605، 5028، 5149، 5185، 5565، 6601، 7107، 8841، 8911، 9577، 9637، ...A020141
1415، 39، 65، 195، 481، 561، 781، 793، 841، 985، 1105، 1111، 1541، 1891، 2257، 2465، 2561، 2665، 2743، 3277، 5185، 5713، 6501، 6533، 6541، 7107، 7171، 7449، 7543، 7585، 8321، 9073، ...A020142
1514، 341، 742، 946، 1477، 1541، 1687، 1729، 1891، 1921، 2821، 3133، 3277، 4187، 6541، 6601، 7471، 8701، 8911، 9073، ...A020143
1615، 51، 85، 91، 255، 341، 435، 451، 561، 595، 645، 703، 1105، 1247، 1261، 1271، 1285، 1387، 1581، 1687، 1695، 1729، 1891، 1905، 2047، 2071، 2091، 2431، 2465، 2701، 2821، 3133، 3277، 3367، 3655، 3683، 4033، 4369، 4371، 4681، 4795، 4859، 5083 5151، 5461، 5551، 6601، 6643، 7471، 7735، 7957، 8119، 8227، 8245، 8321، 8481، 8695، 8749، 8911، 9061، 9131، 9211، 9605، 9919، ...A020144
174، 8، 9، 16، 45، 91، 145، 261، 781، 1111، 1228، 1305، 1729، 1885، 2149، 2821، 3991، 4005، 4033، 4187، 4912، 5365، 5662، 5833، 6601، 6697، 7171، 8481، 8911، ...A020145
1825، 49، 65، 85، 133، 221، 323، 325، 343، 425، 451، 637، 931، 1105، 1225، 1369، 1387، 1649، 1729، 1921، 2149، 2465، 2701، 2821، 2825، 2977، 3325، 4165، 4577، 4753، 5525، 5725، 5833، 5941، 6305، 6517، 6601، 7345، 8911، 9061، ...A020146
196، 9، 15، 18، 45، 49، 153، 169، 343، 561، 637، 889، 905، 906، 1035، 1105، 1629، 1661، 1849، 1891، 2353، 2465، 2701، 2821، 2955، 3201، 4033، 4681، 5461، 5466، 5713، 6223، 6541، 6601، 6697، 7957، 8145، 8281، 8401، 8869، 9211، 9997، ...A020147
2021، 57، 133، 231، 399، 561، 671، 861، 889، 1281، 1653، 1729، 1891، 2059، 2413، 2501، 2761، 2821، 2947، 3059، 3201، 4047، 5271، 5461، 5473، 5713، 5833، 6601، 6817، 7999، 8421، 8911، ...A020148
214، 10، 20، 55، 65، 85، 221، 703، 793، 1045، 1105، 1852، 2035، 2465، 3781، 4630، 5185، 5473، 5995، 6541، 7363، 8695، 8965، 9061، ...A020149
2221، 69، 91، 105، 161، 169، 345، 483، 485، 645، 805، 1105، 1183، 1247، 1261، 1541، 1649، 1729، 1891، 2037، 2041، 2047، 2413، 2465، 2737، 2821، 3241، 3605، 3801، 5551، 5565، 5963، 6019، 6601، 6693، 7081، 7107، 7267، 7665، 8119، 8365، 8421، 8911، 9453، ...A020150
2322، 33، 91، 154، 165، 169، 265، 341، 385، 451، 481، 553، 561، 638، 946، 1027، 1045، 1065، 1105، 1183، 1271، 1729، 1738، 1749، 2059، 2321، 2465، 2501، 2701، 2821، 2926، 3097، 3445، 4033، 4081، 4345، 4371، 4681، 5005، 5149، 6253، 6369، 6533، 6541، 7189، 7267، 7957، 8321، 8365، 8651، 8745، 8911، 8965، 9805، ...A020151
2425، 115، 175، 325، 553، 575، 805، 949، 1105، 1541، 1729، 1771، 1825، 1975، 2413، 2425، 2465، 2701، 2737، 2821، 2885، 3781، 4207، 4537، 6601، 6931، 6943، 7081، 7189، 7471، 7501، 7813، 8725، 8911، 9085، 9361، 9809، ...A020152
254، 6، 8، 12، 24، 28، 39، 66، 91، 124، 217، 232، 276، 403، 426، 451، 532، 561، 616، 703، 781، 804، 868، 946، 1128، 1288، 1541، 1729، 1891، 2047، 2701، 2806، 2821، 2911، 2926، 3052، 3126، 3367، 3592، 3976، 4069، 4123، 4207، 4564، 4636، 4686، 5321، 5461، 5551، 5611، 5662، 5731، 5963، 6601، 7449، 7588، 7813، 8029، 8646، 8911، 9881، 9976، ...A020153
269، 15، 25، 27، 45، 75، 133، 135، 153، 175، 217، 225، 259، 425، 475، 561، 589، 675، 703، 775، 925، 1035، 1065، 1147، 2465، 3145، 3325، 3385، 3565، 3825، 4123، 4525، 4741، 4921، 5041، 5425، 6093، 6475، 6525، 6601، 6697، 8029، 8695، 8911، 9073، ...A020154
2726، 65، 91، 121، 133، 247، 259، 286، 341، 365، 481، 671، 703، 949، 1001، 1105، 1541، 1649، 1729، 1891، 2071، 2465، 2665، 2701، 2821، 2981، 2993، 3146، 3281، 3367، 3605، 3751، 4033، 4745، 4921، 4961، 5299، 5461، 5551، 5611، 5621، 6305، 6533، 6601، 7381، 7585، 7957، 8227، 8321، 8401، 8911، 9139، 9709، 9809، 9841، 9881، 9919، ...A020155
289، 27، 45، 87، 145، 261، 361، 529، 561، 703، 783، 785، 1105، 1305، 1413، 1431، 1885، 2041، 2413، 2465، 2871، 3201، 3277، 4553، 4699، 5149، 5181، 5365، 7065، 8149، 8321، 8401، 9841، ...A020156
294، 14، 15، 21، 28، 35، 52، 91، 105، 231، 268، 341، 364، 469، 481، 561، 651، 793، 871، 1105، 1729، 1876، 1897، 2105، 2257، 2821، 3484، 3523، 4069، 4371، 4411، 5149، 5185، 5356، 5473، 5565، 5611، 6097، 6601، 7161، 7294، 8321، 8401، 8421، 8841، 8911، ...A020157
3049، 91، 133، 217، 247، 341، 403، 469، 493، 589، 637، 703، 871، 899، 901، 931، 1273، 1519، 1537، 1729، 2059، 2077، 2821، 3097، 3277، 3283، 3367، 3577، 4081، 4097، 4123، 5729، 6031، 6061، 6097، 6409، 6601، 6817، 7657، 8023، 8029، 8401، 8911، 9881، ...A020158

للمزيد من المعلومات (من الأساس 31 إلى 100)، انظر (التسلسل A020159 في OEIS ) إلى (التسلسل A020228 في OEIS ) ، ولجميع الأساسات حتى 150، انظر جدول الأعداد الأولية الزائفة لفيرما (النص باللغة الألمانية) . لا تُعرّف هذه الصفحة ما إذا كان n عددًا أوليًا زائفًا لأساس مطابق لـ 1 أو -1 (mod n ).

القواعد b التي يكون فيها n عددًا أوليًا زائفًا من نوع فيرما

إذا كان مركباًن{\displaystyle n}إذا كان زوجيًا، فإذنن{\displaystyle n}هو عدد أولي زائف من نوع فيرما بالنسبة للأساس التافهب≡1(تعديلن){\displaystyle b\equiv 1{\pmod {n}}}إذا كان مركباًن{\displaystyle n}إذا كان الأمر غريباً، فإذنن{\displaystyle n}هو عدد أولي زائف من نوع فيرما بالنسبة للقواعد التافهةب≡±1(تعديلن){\displaystyle b\equiv \pm 1{\pmod {n}}}.

لأي مركبن{\displaystyle n}عدد القواعد المختلفةب{\displaystyle b}moduloن{\displaystyle n}، والتي من أجلهان{\displaystyle n}هو أساس فيرما شبه الأوليب{\displaystyle b}، هو [ 10 ] : نظرية 1، ص 1392

∏أنا=1كالقاسم المشترك الأكبر(صأنا-1،ن-1){\displaystyle \prod _{i=1}^{k}\gcd(p_{i}-1,n-1)}

أينص1،...،صك{\displaystyle p_{1},\dots ,p_{k}}هي العوامل الأولية المتميزة لـن{\displaystyle n}وهذا يشمل القواعد التافهة.

على سبيل المثال، لـ ن=341=11⋅31{\displaystyle n=341=11\cdot 31}هذا المنتجالقاسم المشترك الأكبر(10،340)⋅القاسم المشترك الأكبر(30،340)=100{\displaystyle \gcd(10,340)\cdot \gcd(30,340)=100}. لن=341{\displaystyle n=341}أصغر قاعدة غير تافهة من هذا القبيل هيب=2{\displaystyle b=2}.

كل مركب غريبن{\displaystyle n}هو عدد أولي زائف من نوع فيرما بالنسبة إلى قاعدتين غير تافهتين على الأقل moduloن{\displaystyle n}إلا إذان{\displaystyle n}هو قوة للعدد 3. [ 10 ] : كورنثوس الأولى، ص 1393

بالنسبة للأعداد المركبة n < 200، يوجد فيما يلي جدول بجميع القواعد b < n التي يكون فيها n عددًا أوليًا زائفًا وفقًا لنظرية فيرما. إذا لم يكن العدد المركب n موجودًا في الجدول (أو كان n موجودًا في المتتالية A209211 )، فإن n يكون عددًا أوليًا زائفًا فقط بالنسبة للأساس التافه 1 بتردد n .

نالأساسات 0 < b < n حيث n عدد أولي زائف لفيرماعدد قواعد OEIS : A063994 
91، 82
151، 4، 11، 144
211، 8، 13، 204
251، 7، 18، 244
271,262
281، 9، 253
331، 10، 23، 324
351، 6، 29، 344
391، 14، 25، 384
451، 8، 17، 19، 26، 28، 37، 448
491، 18، 19، 30، 31، 486
511، 16، 35، 504
521، 9، 293
551، 21، 34، 544
571، 20، 37، 564
631، 8، 55، 624
651، 8، 12، 14، 18، 21، 27، 31، 34، 38، 44، 47، 51، 53، 57، 6416
661، 25، 31، 37، 495
691، 22، 47، 684
701، 11، 513
751، 26، 49، 744
761، 45، 493
771، 34، 43، 764
811,802
851، 4، 13، 16، 18، 21، 33، 38، 47، 52، 64، 67، 69، 72، 81، 8416
871، 28، 59، 864
911، 3، 4، 9، 10، 12، 16، 17، 22، 23، 25، 27، 29، 30، 36، 38، 40، 43، 48، 51، 53، 55، 61، 62، 64، 66، 68، 69، 74، 75، 79، 81، 82، 87، 88، 9036
931، 32، 61، 924
951، 39، 56، 944
991، 10، 89، 984
1051، 8، 13، 22، 29، 34، 41، 43، 62، 64، 71، 76، 83، 92، 97، 10416
1111، 38، 73، 1104
1121، 65، 813
1151، 24، 91، 1144
1171، 8، 44، 53، 64، 73، 109، 1168
1191، 50، 69، 1184
1211، 3، 9، 27، 40، 81، 94، 112، 118، 12010
1231، 40، 83، 1224
1241، 5، 253
1251، 57، 68، 1244
1291، 44، 85، 1284
1301، 61، 813
1331، 8، 11، 12، 18، 20، 26، 27، 30، 31، 37، 39، 45، 46، 50، 58، 64، 65، 68، 69، 75، 83، 87، 88، 94، 96، 102، 103، 106، 107، 113، 115، 121، 122، 125، 13236
1351، 26، 109، 1344
1411، 46، 95، 1404
1431، 12، 131، 1424
1451، 12، 17، 28، 41، 46، 57، 59، 86، 88، 99، 104، 117، 128، 133، 14416
1471، 50، 97، 1464
1481، 121، 1373
1531، 8، 19، 26، 35، 53، 55، 64، 89، 98، 100، 118، 127، 134، 145، 15216
1541، 23، 673
1551، 61، 94، 1544
1591، 52، 107، 1584
1611، 22، 139، 1604
1651، 23، 32، 34، 43، 56، 67، 76، 89، 98، 109، 122، 131، 133، 142، 16416
1691، 19، 22، 23، 70، 80، 89، 99، 146، 147، 150، 16812
1711، 37، 134، 1704
1721,49,1653
1751، 24، 26، 51، 74، 76، 99، 101، 124، 149، 151، 17412
1761، 49، 81، 97، 1135
1771، 58، 119، 1764
1831، 62، 121، 1824
1851، 6، 31، 36، 38، 43، 68، 73، 112، 117، 142، 147، 149، 154، 179، 18416
1861، 97، 109، 157، 1635
1871، 67، 120، 1864
1891، 55، 134، 1884
1901، 11، 61، 81، 101، 111، 121، 131، 1619
1951، 14، 64، 79، 116، 131، 181، 1948
1961، 165، 1773

لمزيد من المعلومات ( من n = 201 إلى 5000)، انظر b:de:Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) (جدول الأعداد الأولية الزائفة 16-4999). على عكس القائمة أعلاه، تستثني هذه الصفحة الأساسين 1 و n − 1. عندما يكون p عددًا أوليًا، يكون p² عددًا أوليًا زائفًا لفيرما في الأساس b إذا وفقط إذا كان p عددًا أوليًا لويفريش في الأساس b . على سبيل المثال، 1093² = 1194649 هو عدد أولي زائف لفيرما في الأساس 2، و11² = 121 هو عدد أولي زائف لفيرما في الأساس 3.

عدد قيم b لـ n هو (بالنسبة لـ n عدد أولي، يجب أن يكون عدد قيم b هو n − 1، لأن جميع قيم b تحقق نظرية فيرما الصغرى ).

1، 1، 2، 1، 4، 1، 6، 1، 2، 1، 10، 1، 12، 1، 4، 1، 16، 1، 18، 1، 4، 1، 22، 1، 4، 1، 2، 3، 28، 1، 30، 1، 4، 1، 4، 1، 36، 1، 4، 1، 40، 1، 42، 1، 8، 1، 46، 1، 6، 1، ... (التسلسل A063994 في OEIS )

أصغر عدد أساسه b > 1 يكون فيه n عددًا شبه أولي بالنسبة للأساس b (أو عددًا أوليًا) هو

2، 3، 2، 5، 2، 7، 2، 9، 8، 11، 2، 13، 2، 15، 4، 17، 2، 19، 2، 21، 8، 23، 2، 25، 7، 27، 26، 9، 2، 31، 2، 33، 10، 35، 6، 37، 2، 39، 14، 41، 2، 43، 2، 45، 8، 47، 2، 49، 18، 51، ... (التسلسل A105222 في OEIS )

يجب أن يقسم عدد قيم b لقيمة n معينةφ{\displaystyle \varphi }( ن )، أو A000010 ( ن ) = 1، 1، 2، 2، 4، 2، 6، 4، 6، 4، 10، 4، 12، 6، 8، 8، 16، 6، 18، 8، 12، 10، 22، 8، 20، 12، 18، 12، 28، 8، 30، 16، 20، 16، 24، 12، 36، 18، 24، 16، 40، 12، 42، 20، 24، 22، 46، 16، 42، 20، ... يمكن أن يكون ناتج القسمة أي عدد طبيعي، ويكون ناتج القسمة = 1 إذا وفقط إذا كان ن عددًا أوليًا أو عددًا من أعداد كارمايكل (561، 1105، ...). 1729، 2465، 2821، 6601، 8911، 10585، 15841، ... A002997 ) يكون ناتج القسمة = 2 إذا وفقط إذا كان n ضمن المتتالية: 4، 6، 15، 91، 703، 1891، 2701، 11305، 12403، 13981، 18721، ... A191311 .)

أصغر الأعداد التي هي أعداد شبه أولية بالنسبة لقيم k من b هي (أو 0 إذا لم يكن هناك مثل هذا العدد)

1، 3، 28، 5، 66، 7، 232، 45، 190، 11، 276، 13، 1106، 0، 286، 17، 1854، 19، 3820، 891، 2752، 23، 1128، 595، 2046، 0، 532، 29، 1770، 31، 9952، 425، 1288، 0، 2486، 37، 8474، 0، 742، 41، 3486، 43، 7612، 5589، 2356، 47، 13584، 325، 9850، 0، ... (متسلسلة) A064234 في OEIS ) ( إذا وفقط إذا كان k زوجيًا وليس ظرف العدد الخالي من المربعات ، فإن الحد k من هذه المتتالية هو 0.)

الأعداد الأولية الزائفة الضعيفة

عدد مركب n يحققبن≡ب(تعديلن){\displaystyle b^{n}\equiv b{\pmod {n}}}يُطلق عليه اسم عدد أولي ضعيف للأساس b . بالنسبة لأي أساس b مُعطى ، فإن جميع الأعداد الأولية الضعيفة لفيرما هي أعداد أولية ضعيفة، وجميع الأعداد الأولية الضعيفة التي هي أولية نسبية مع b هي أعداد أولية ضعيفة لفيرما. ومع ذلك، يسمح هذا التعريف أيضًا ببعض الأعداد الأولية التي ليست أولية نسبية مع b . [ 11 ] على سبيل المثال، أصغر عدد أولي ضعيف زوجي للأساس 2 هو 161038 (انظر (المتتالية A006935 في OEIS ) ).

أقل الأعداد الأولية الزائفة الضعيفة للقواعد b = 1، 2، ... هي:

4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ... OEIS : A000790 

أعداد كارمايكل هي أعداد شبه أولية ضعيفة لجميع القواعد، لذا فإن جميع الحدود في هذه القائمة أصغر من أو تساوي أصغر عدد كارمايكل، وهو 561. باستثناء 561 = 3 × 11 × 17، لا يمكن أن تظهر في المتتالية أعلاه إلا أعداد شبه أولية. لا تظهر جميع الأعداد شبه الأولية الأقل من 561؛ يظهر عدد شبه أولي pq ( حيث p ≤ q ) أقل من 561 في المتتاليات أعلاه إذا وفقط إذا كان p − 1 يقسم q − 1 (انظر المتتالية A108574 في OEIS ) . عادةً ما يكون أصغر عدد شبه أولي لفيرما للقاعدة b (والذي لا يتجاوز b بالضرورة ) ( انظر المتتالية A090086 في OEIS ) عددًا شبه أولي، ولكن ليس دائمًا؛ أول مثال مضاد هو A090086 (648) = 385 = 5 × 7 × 11.

إذا اشترطنا أن يكون n > b ، فإن أصغر الأعداد الأولية الزائفة الضعيفة (لـ b = 1، 2، ...) هي:

4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51,... أويس : A239293 

أعداد أويلر الأولية الزائفة

الأعداد الأولية الزائفة لأويلر هي مجموعة فرعية من الأعداد الأولية الزائفة لفيرما لأي أساس معينأ{\displaystyle a}. يوجد أيضًا أعداد أويلر الأولية المطلقة، وهي مجموعة فرعية من أعداد كارمايكل ، وهي نظير أعداد كارمايكل لأعداد أويلر الأولية.

أعداد أويلر-جاكوبي الأولية الزائفة

ثمة نهج آخر يتمثل في استخدام مفاهيم أكثر دقة للأعداد شبه الأولية، مثل الأعداد شبه الأولية القوية أو أعداد أويلر-جاكوبي شبه الأولية ، والتي لا يوجد لها نظائر في أعداد كارمايكل . يؤدي هذا إلى خوارزميات احتمالية مثل اختبار سولوفاي-ستراسن للأعداد الأولية ، واختبار بايلي-PSW للأعداد الأولية ، واختبار ميلر-رابين للأعداد الأولية ، والتي تُنتج ما يُعرف بالأعداد الأولية الصناعية . الأعداد الأولية الصناعية هي أعداد صحيحة لم يتم "التحقق" من أوليتها (أي إثباتها بدقة)، ولكنها خضعت لاختبار مثل اختبار ميلر-رابين الذي يتميز باحتمالية فشل غير صفرية، ولكنها منخفضة للغاية.

التطبيقات

لندرة هذه الأعداد شبه الأولية آثار عملية هامة. على سبيل المثال، تتطلب خوارزميات التشفير بالمفتاح العام، مثل RSA، القدرة على إيجاد أعداد أولية كبيرة بسرعة. الخوارزمية المعتادة لتوليد الأعداد الأولية هي توليد أعداد فردية عشوائية واختبارها للتأكد من كونها أولية. مع ذلك، فإن اختبارات الأولية الحتمية بطيئة. إذا كان المستخدم على استعداد لتقبّل احتمال ضئيل للغاية بأن يكون العدد المُكتشف ليس عددًا أوليًا بل عددًا شبه أولي، فمن الممكن استخدام اختبار فيرما للأولية، وهو أسرع وأبسط بكثير .

مراجع

  1. 1 2 صموئيل س. واغستاف الابن (2013). متعة التحليل إلى عوامل . بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية. ISBN 978-1-4704-1048-3.
  2. 1 2 ديسميدت، إيفو (2010). "مخططات التشفير" . في: عطا الله، ميخائيل ج .؛ بلانتون، مارينا (محرران). دليل الخوارزميات ونظرية الحوسبة: مواضيع وتقنيات خاصة . مطبعة سي آر سي. ص 10-23 . ISBN  978-1-58488-820-8.
  3. ↑ باولو ريبنبوم (1996). الكتاب الجديد لسجلات الأعداد الأولية . نيويورك: سبرينغر-فيرلاغ . ص 108. ISBN  0-387-94457-5.
  4. ^ هامهاتا، يوشينوري. كوكوبون، ي. (2007). "سيبولا الزائفة" (PDF) . مجلة تسلسلات صحيحة . 10 (8).
  5. 1 2 بوميرانس، كارل ؛ سيلفريدج، جون ل .؛ واغستاف، صموئيل س. الابن (يوليو 1980). "الأعداد الأولية الزائفة حتى 25 × 10⁹ " ( ملف PDF) . رياضيات الحساب . 35 (151): 1003-1026 . doi : 10.1090/S0025-5718-1980-0572872-7 . مؤرشف (ملف PDF) من الأصل في 4 مارس 2005.
  6. ↑ ألفورد، دبليو آر ؛ جرانفيل، أندرو ؛ بوميرانس، كارل (1994). "يوجد عدد لا نهائي من أعداد كارمايكل" ​​( ملف PDF) . حوليات الرياضيات . 140 (3): 703-722 . doi : 10.2307/2118576 . JSTOR 2118576. مؤرشف (ملف PDF) من الأصل بتاريخ 4 مارس 2005. 
  7. ↑ كيم، سو هي؛ بوميرانس، كارل (1989). "احتمالية أن يكون عدد أولي عشوائي محتمل عددًا مركبًا" . رياضيات الحساب . 53 (188): 721-741 . doi : 10.2307/2008733 . JSTOR 2008733 . 
  8. ↑ بوميرانس[81] كما ورد في، القسم 2.1.
  9. ↑ سيربينسكي، و. (15-02-1988)، "الفصل الخامس، 7"، في تحرير أ. شينزل، النظرية الأولية للأعداد ، مكتبة شمال هولندا الرياضية ( الطبعة الثانية الفرعية)، أمستردام: شمال هولندا، ص 232، ISBN   9780444866622
  10. ١ ٢ روبرت بيلي؛ صموئيل س. واغستاف الابن (أكتوبر ١٩٨٠). "أعداد لوكاس الأولية الزائفة" ( ملف PDF) . رياضيات الحساب . ٣٥ (١٥٢): ١٣٩١-١٤١٧ . doi : 10.1090/S0025-5718-1980-0583518-6 . MR 0583518. مؤرشف (ملف PDF) من الأصل في ٢٠٠٦-٠٩-٠٦. 
  11. ↑ ميشون، جيرار ب. (19 نوفمبر 2003). "الأعداد الأولية الزائفة، الأعداد الأولية الزائفة الضعيفة، الأعداد الأولية الزائفة القوية، أولية الأعداد" . نوميريكانا . تم الاطلاع عليه بتاريخ 21 أبريل 2018 .