הַגדָרָה 1. מספר ראשוניהאם מספר טבעייותר מאחד, שמתחלק רק בעצמו וב-1.

במילים אחרות, מספר הוא ראשוני אם יש לו רק שני מחלקים טבעיים שונים.

הַגדָרָה 2. כל מספר טבעי שבנוסף לעצמו ולאחד יש מחלקים נוספים, נקרא מספר מורכב.

במילים אחרות, מספרים טבעיים שאינם מספרים ראשוניים נקראים מספרים מרוכבים. הגדרה 1 מרמזת שלמספר מורכב יש יותר משני מחלקים טבעיים. המספר 1 אינו פשוט ואינו מורכב. יש רק מחלק אחד 1, וחוץ מזה, משפטים רבים על מספרים ראשוניים אינם מתקיימים לאחדות.

הגדרות 1 ו-2 מרמזות שכל מספר שלם חיובי הגדול מ-1 הוא ראשוני או מורכב.

להלן תוכנית להצגת ראשוניים עד 5000. מלא את התאים, לחץ על כפתור "צור" והמתן מספר שניות.

טבלת מספרים ראשוניים

הַצהָרָה 1. אם עהוא מספר ראשוני ו אכל מספר שלם, אז גם כן אמחולק ב עאוֹ עו אמספרים ראשוניים.

בֶּאֱמֶת. אם עמספר ראשוני, אז הוא מתחלק רק בעצמו וב-1, אם אלא ניתן לחלוקה ב ע, ואז הגדול ביותר מחלק משותף או עשווה ל-1. ואז עו אהֲדָדִית מספרים ראשוניים.

הַצהָרָה 2. אם המכפלה של מספר מספרים היא מספרים א 1 , א 2 , א 3, ... מתחלק במספר ראשוני ע, ואז לפחות אחד מהמספרים א 1 , א 2 , א 3, ... מחולק ל ע.

בֶּאֱמֶת. אם אף אחד מהמספרים לא היה מתחלק ב ע, ואז המספרים א 1 , א 2 , א 3, ... יהיו מספרים ראשוניים ביחס ל ע... אבל מתוצאה 3 () עולה שהמוצר שלהם א 1 , א 2 , א 3, ... הוא גם קופריים ל ע, מה שסותר את תנאי הקביעה. לכן, לפחות אחד מהמספרים מתחלק ב ע.

מִשׁפָּט 1. כל מספר מורכב תמיד יכול להיות מיוצג, ויתרה מכך, הדרך היחידהכמכפלה של מספר סופי של ראשוניים.

הוכחה. תן קמספר מורכב, ולתת א 1 הוא אחד המחלקים שלו מלבד 1 ומעצמו. אם א 1 הוא מורכב, ואז יש לו, בנוסף ל-1 ו א 1 ועוד מחלק א 2. אם א 2 הוא מספר מורכב, ואז יש לו, בנוסף ל-1 ו א 2 ומחלק נוסף א 3. מנמק כך ובהתחשב בכך המספרים א 1 , א 2 , א 3, ... ירידה וסדרה זו מכילה מספר סופי של איברים, נגיע למספר ראשוני כלשהו עאחד . לאחר מכן קיכול להיות מיוצג כ

נניח שיש שני פירוקים של המספר ק:

כי k = p 1 ע 2 ע 3 ... מתחלק במספר ראשוני ש 1, אז לפחות אחד מהגורמים, למשל ע 1 מחולק ל שאחד . אבל ע 1 הוא מספר ראשוני ומתחלק רק ב-1 ובעצמו. לָכֵן ע 1 =ש 1 (מאז ש 1 ≠1)

ואז מ-(2) נוכל להוציא ע 1 ו ש 1:

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

פירוק של מספר מורכב קניתן לכתוב באופן הבא

(3)

איפה ע 1 , ע 2, ... ראשוניים שונים, α, β, γ ... מספרים שלמים חיוביים.

הרחבה (3) נקראת פירוק קנונימספרים.

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

מִשׁפָּט 2. מספר הראשוניים הוא אינסופי.

הוכחה. נניח שיש הרבה ראשוניים סופיים ותן לראשוני הגדול ביותר להיות ע... שקול את כל המספרים גדולים מ ע... בהנחה של ההצהרה, מספרים אלו חייבים להיות מורכבים וחייבים להיות מתחלקים לפחות באחד מהמספרים הראשוניים. בוא נבחר מספר שהוא המכפלה של כל הראשוניים האלה פלוס 1:

מספר זיותר עכי 2 עמ'כבר יותר ע. עאינו מתחלק באף אחד מהמספרים הראשוניים הללו, שכן חלוקה בכל אחד מהם נותן שארית של 1. כך, אנו מגיעים לסתירה. לפיכך, ישנם אינספור ראשוניים.

משפט זה הוא מקרה מיוחד של משפט כללי יותר:

מִשׁפָּט 3. תן התקדמות אריתמטית

ואז כל מספר ראשוני שנכלל ב נ, צריך להיכלל גם ב M, אז ב נגורמים ראשוניים אחרים שאינם כלולים ב Mויתרה מכך, הגורמים העיקריים הללו ב ננכללים לא יותר ממספר פעמים מאשר M.

גם ההיפך נכון. אם כל גורם ראשוני של המספר ננכלל לפחות אותו מספר פעמים M, לאחר מכן Mמחולק ב נ.

הַצהָרָה 3. תן א 1 ,א 2 ,א 3, ... ראשוניים שונים הכלולים ב Mלכן

איפה אני=0,1,...α , י=0,1,...,β , k = 0,1, ..., γ ... שים לב ש α iלוקח α ערכי 1+, β j לוקח β ערכי 1+, γ k לוקח γ ערכי 1+, ....

כל המספרים הטבעיים, למעט אחד, מחולקים לראשוני ולמרוכב. מספר ראשוני הוא מספר טבעי שיש לו רק שני מחלקים: אחד ואת עצמו... כל השאר נקראים מורכבים. חקר תכונות המספרים הראשוניים עוסק בענף מיוחד במתמטיקה - תורת המספרים. בתורת הטבעות, ראשוניים קשורים ליסודות בלתי ניתנים לצמצום.

הנה רצף ראשוניים שמתחיל ב-2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, ... וכו'.

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

ייצוג כזה של מספר טבעי נקרא פירוק מספר ראשוני או פירוק מספרים.

אחת הדרכים הוותיקות והיעילות ביותר לחישוב מספרים ראשוניים היא מסננת Erastofen.

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

אגב, יש מבחני פשטות יעילים מיוחדים עבור כמה מחלקות של מספרים. לדוגמה, מבחן Luc-Lemaire משמש לבדיקת פשטות מספרי מרסן, ומבחן פפין משמש לבדיקת פשטות מספרי פרמה.

כולנו יודעים שיש אינסוף מספרים. נשאלת השאלה: כמה ראשוניים יש אם כך? יש גם מספר אינסופי של ראשוניים. ההוכחה העתיקה ביותר להצעה זו היא ההוכחה של אוקלידס, המופיעה ב"אלמנטים". ההוכחה של אוקלידס היא כדלקמן:

בואו נדמיין שמספר הראשוניים הוא סופי. בוא נכפיל אותם ונוסיף אחד. לא ניתן לחלק את המספר המתקבל באף אחד מהקבוצה הסופית של ראשוניים, כי שאר החלוקה בכל אחד מהם נותן אחד. לפיכך, המספר חייב להיות מתחלק במספר ראשוני כלשהו שאינו כלול בקבוצה זו.

משפט המספרים הראשוניים קובע שמספר הראשוניים הקטן מ-n, המסומנים ב-π (n), גדל כ-n / ln (n).

במהלך אלפי שנות מחקר על ראשוניים, נמצא שהמספר הראשוני הידוע הגדול ביותר הוא 243112609 - 1. מספר זה כולל 12,978,189 ספרות עשרוניות והוא ראשוני מרסן (M43112609). תגלית זו התגלתה ב-23 באוגוסט 2008 במחלקה למתמטיקה של אוניברסיטת uCLA כחלק מהחיפוש המבוזר של GIMPS אחר ראשוני מרסן.

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

עם זאת, עד היום, שאלות רבות על ראשוניים לא קיבלו תשובות מדויקות. בקונגרס הבינלאומי החמישי למתמטיקה אדמונד לנדאו ניסח את הבעיות העיקריות בתחום הראשוניים:

הבעיה של גולדבך או הבעיה הראשונה של לנדאו היא שיש צורך להוכיח או להפריך שכל מספר זוגי גדול משניים יכול להיות מיוצג כסכום של שני ראשוניים, וכל מספר אי זוגי גדול מ-5 יכול להיות מיוצג כסכום שלוש פשוטותמספרים.
הבעיה השנייה של לנדאו מחייבת למצוא תשובה לשאלה: האם יש קבוצה אינסופית של "תאומים פשוטים" - ראשוניים, שההבדל ביניהם שווה ל-2?
ההשערה של לג'נדר או הבעיה השלישית של לנדאו היא זו: האם זה נכון שתמיד יש ראשוני בין n2 ל-(n+1)2?
הבעיה הרביעית של לנדאו: האם יש קבוצה אינסופית של ראשוניים בצורה n2 + 1?
בנוסף לבעיות הנ"ל, ישנה בעיה של הגדרת מספר אינסופי של ראשוניים ברצפים שלמים רבים כמו מספר פיבונאצ'י, מספר פרמה וכו'.

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

אילו מספרים הם ראשוניים

איך מגדירים מספר ראשוני? מספרים רבים מתחלקים במספרים אחרים ללא שארית. המספר שמחלק מספר שלם הוא מה שאנו מכנים מחלק.

במקרה זה, אנו מדברים על חלוקה ללא שארית. לדוגמה, ניתן לחלק את המספר 36 ב-1, 2, 3, 4, 6, 9, 12, 18 ובעצמו, כלומר ב-36. אז ל-36 יש 9 מחלקים. המספר 23 מתחלק רק בעצמו וב-1, כלומר למספר הזה יש 2 מחלקים - המספר הזה הוא ראשוני.

מספרים שיש להם רק שני מחלקים נקראים מספרים ראשוניים. כלומר, מספר שמתחלק רק בעצמו ובאחד נקרא ראשוני.

עבור מתמטיקאים, גילוי תבניות בסדרה של מספרים שניתן להשתמש בהם ליצירת השערות היא חוויה נעימה מאוד. אבל מספרים ראשוניים מסרבים לציית לכל דפוס. אבל יש דרך להגדיר מספרים ראשוניים. שיטה זו נמצאה על ידי Eratosthenes, היא נקראת "המסננת של Eratosthenes". הבה נבחן גרסה של "מסננת" כזו המוצגת בצורה של טבלה של מספרים עד 48 ונבין כיצד היא מורכבת.

בטבלה זו, כל ראשוני הקטן מ-48 מסומנים תפוז... הם נמצאו כך:

• 1 - בעל מחלק בודד ולכן אינו מספר ראשוני;
• 2 הוא המספר הראשוני הקטן ביותר והזוגי היחיד, מכיוון שכל שאר המספרים הזוגיים מתחלקים ב-2, כלומר יש להם לפחות 3 מחלקים, המספרים הללו מצטמצמים ל עמוד סגול;
• 3 הוא מספר ראשוני, בעל שני מחלקים, כל שאר המספרים המתחלקים ב-3 אינם נכללים - המספרים הללו מוצגים בעמודה הצהובה. העמודה המסומנת גם בסגול וגם בצהוב מכילה מספרים המתחלקים ב-2 וגם ב-3;
• 5 הוא מספר ראשוני, כל המספרים המתחלקים ב-5 אינם נכללים - המספרים הללו מוקפים בסגלגל ירוק;
• 7 הוא מספר ראשוני, כל המספרים המתחלקים ב-7 מוקפים בסגלגל אדום - הם אינם ראשוניים;

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

מספר ראשוני הוא מספר טבעי המתחלק רק בעצמו ובאחד.

שאר המספרים נקראים מספרים מרוכבים.

מספרים טבעיים ראשוניים

אבל לא כל המספרים הטבעיים הם מספרים ראשוניים.

מספרים טבעיים ראשוניים הם רק אלה שמתחלקים רק בעצמם ובאחד.

דוגמאות לראשוניים:

2; 3; 5; 7; 11; 13;...

מספרים שלמים פשוטים

מכאן נובע שרק מספרים טבעיים הם מספרים ראשוניים.

זה אומר שהראשונים הם בהכרח טבעיים.

אבל כל המספרים הטבעיים הם מספרים שלמים בו-זמנית.

לפיכך, כל הראשוניים הם מספרים שלמים.

דוגמאות לראשוניים:

2; 3; 5; 7; 11; 13; 17; 19; 23;...

אפילו ראשוניים

יש רק מספר ראשוני זוגי אחד, שהוא המספר שתיים.

כל שאר הראשוניים הם מוזרים.

מדוע מספר זוגי לא יכול להיות יותר משני ראשוניים?

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

תשובתו של איליה נכונה, אך לא מפורטת במיוחד. במאה ה-18, אגב, היחידה עדיין נחשבה למספר ראשוני. למשל, מתמטיקאים גדולים כמו אוילר וגולדבך. גולדבך הוא המחבר של אחת משבע הבעיות של המילניום - השערת גולדבך. הניסוח המקורי קובע שכל מספר זוגי יכול להיות מיוצג כסכום של שני ראשוניים. יתרה מכך, בתחילה 1 נלקח בחשבון כמספר ראשוני, ואנו רואים זאת: 2 = 1 + 1. זֶה הדוגמה הקטנה ביותרמספק את הניסוח המקורי של ההשערה. מאוחר יותר זה תוקן, והנוסח נרכש מראה מודרני: "כל מספר זוגי, החל מ-4, יכול להיות מיוצג כסכום של שני ראשוניים."

בואו נזכור את ההגדרה. ראשוני הוא מספר טבעי p, שיש לו רק 2 מחלקים טבעיים שונים: p עצמו ו-1. מסקנה מההגדרה: למספר ראשוני p יש רק מחלק ראשוני אחד - p עצמו.

עכשיו נניח ש-1 הוא מספר ראשוני. בהגדרה, לראשוני יש רק מחלק ראשוני אחד - הוא עצמו. ואז מתברר שכל מספר ראשוני גדול מ-1 מתחלק במספר ראשוני אחר (ב-1). אבל שני מספרים ראשוניים שונים אינם ניתנים לחלוקה זה בזה, כי אחרת, הם אינם מספרים ראשוניים, אלא מספרים מורכבים, וזה סותר את ההגדרה. בגישה זו, מתברר שיש רק מספר ראשוני 1 - היחידה עצמה. אבל זה אבסורד. לכן, 1 אינו מספר ראשוני.

1, כמו גם 0, יוצרים מחלקה נוספת של מספרים - המחלקה של אלמנטים ניטרליים ביחס לפעולות n-ארי בתת-קבוצה כלשהי של שדה אלגברי. יתרה מכך, ביחס לפעולת החיבור, 1 הוא גם אלמנט מחולל לטבעת המספרים השלמים.

עם שיקול זה, לא קשה למצוא אנלוגים של ראשוניים במבנים אלגבריים אחרים. נניח שיש לנו קבוצת כפל שנוצרה מחזקות של 2, החל מ-1: 2, 4, 8, 16, ... וכו'. 2 פועל כאן כאלמנט מחולל. מספר ראשוני בקבוצה זו הוא מספר גדול מהיסוד הקטן ביותר ומתחלק רק בעצמו וביסוד הקטן ביותר. בקבוצה שלנו, רק ל-4 יש נכסים כאלה. הכל. אין יותר מספרים ראשוניים בקבוצה שלנו.

אם 2 היה גם מספר ראשוני בקבוצה שלנו, אז ראה את הפסקה הראשונה - שוב, היה מסתבר שרק 2 הוא מספר ראשוני.