הצגת המקור של הדף "מספר פסאודו-ראשוני"

ב[[תורת המספרים]], '''מספר פסאודו-ראשוני''' הוא [[מספר פריק]] החולק תכונה כלשהי עם כל ה[[מספר ראשוני|מספרים הראשוניים]].

עיסוק מרכזי בתורת המספרים, בעל השלכות רבות ל[[קריפטוגרפיה]], הוא חקר [[מבחן ראשוניות|מבחני ראשוניות]] הבודקים האם מספר נתון הוא ראשוני או פריק. מבחני ראשוניות רבים בוחנים תכונה המתקיימת בכל הראשוניים, אך ייתכן גם שהיא מתקיימת במספרים פריקים מסוימים. אם מספר כלשהו לא מקיים תכונה שכזו, הוא בהכרח פריק, אך אם מתגלה שמספר מסוים מקיים את התכונה, אין ודאות אם הוא ראשוני או פסאודו-ראשוני ביחס לתכונה. מבחן ראשוניות יעיל הוא מבחן ששכיחות המספרים הפסאודו-ראשוניים ביחס אליו נמוכה.

ישנם מבחני ראשוניות, כגון [[מבחן AKS]], שמזהים ראשוני בוודאות מוחלטת ואין מספר פסאודו-ראשוניים ביחס אליהם. עם זאת, לצרכים מעשיים מעדיפים את השימוש במבחנים מהירים יותר, כגון [[אלגוריתם מילר-רבין]], שיש סיכוי שיזהו כראשוני מספר שהוא פסאודו-ראשוני, אך ניתן להקטין את הסיכוי הזה באופן בלתי מוגבל.

==פסאודו-ראשוני פרמה==
הסוג המוכר ביותר של מספרים פסאודו-ראשוניים הם המספרים הפריקים המקיימים את [[המשפט הקטן של פרמה]]. מספר פריק <math>n</math> נקרא '''פסאודו-ראשוני פרמה בבסיס a''' אם מתקיים <math>n \mid a^n - a</math> (n [[מחלק]] את a<sup>n</sup>-a). מספר שהוא פסאודו-ראשוני פרמה בכל בסיס נקרא '''פסאודו-ראשוני פרמה מוחלט''' או '''[[מספר קרמייקל]]'''. הדוגמה הקטנה ביותר למספר כזה היא 561.

===פסאודו-ראשוני פרמה בבסיס 2===
כבר ב[[המאה ה-6 לפנה"ס|מאה ה-6 לפנה"ס]] שיערו [[מתמטיקאי]]ם [[סין (אזור)|סינים]] ש-<math>n</math> ראשוני אם ורק אם <math>n \mid 2^n-2</math>. ב-[[1819]] נתגלתה ה[[דוגמה נגדית|דוגמה הנגדית]] הקטנה ביותר: <math>341 \mid 2^{341}-2</math>, על אף ש-<math>11\cdot 31 = 341</math> הוא מספר פריק.

אם <math>p</math> ראשוני, ו[[מספר מרסן]] <math>M_p = 2^p-1</math> פריק, אז <math>M_p</math> הוא פסאודו-ראשוני בבסיס 2. כמו כן כל [[מספר פרמה]] פריק הוא גם כן פסאודו-ראשוני בבסיס 2.

לא קשה לבנות [[סדרה (מתמטיקה)|סדרה אינסופית]] עולה של פסאודו-ראשוניים בבסיס 2. אם <math>n</math> מספר פסאודו-ראשוני בבסיס 2, אז גם <math>M_n</math> כזה. כדי לראות זאת נשתמש בתכונה בסיסית של מספרי מרסן, שאם <math>k \mid n</math>, אז <math>M_k \mid M_n</math>. <math>n</math> פריק ולכן קיים <math>k \mid n</math> לא טריוויאלי. מכאן ש-<math>M_k \mid M_n</math> ו-<math>M_n</math> פריק. כמו כן מכך ש-<math> n</math> פסאודו-ראשוני נובע שקיים <math>r</math> כך ש-<math>rn = 2^n-2</math>, ולכן <math>2^{M_n}-2 = 2^{rn+1}-2 = 2M_{rn}</math>. כלומר <math>M_n \mid 2M_{rn} = 2^{M_n}-2</math> כנדרש.

==קישורים חיצוניים==
* {{MathWorld}}
* {{בריטניקה}}

{{קצרמר|מתמטיקה}}
[[קטגוריה:מספרים ראשוניים]]
[[קטגוריה:מבחני ראשוניות]]
[[קטגוריה:סדרות של שלמים]]
[[קטגוריה:השערות מתמטיות שהופרכו]]
[[nl:Kleine stelling van Fermat#Pseudo-priemgetallen]]