- מאפייני מספרים ראשוניים
- כיצד לדעת אם מספר ראשוני
- דרכים למצוא מספר ראשוני
- הנוסחה של אוילר
- המסננת של Eratosthenes
- תרגילים
- - תרגיל 1
- פִּתָרוֹן
- - תרגיל 2
- פתרון ל
- פיתרון ב
- הפניות
המספרים הראשוניים , המכונים גם ממשלה מוחלטת, הם אלה מספרים טבעיים אשר מתחלק רק בעצמם 1. בקטגוריה זו מספרים כמו 2, 3, 5, 7, 11, 13, 17, 19, 23 ו רבים ועוד.
במקום זאת, מספר מורכב מתחלק בעצמו, ב -1 ולפחות מספר אחד אחר. יש לנו, למשל, 12, המתחלק ב -1, 2, 4, 6 ו 12. לפי המוסכמות, 1 לא נכלל ברשימת המספרים הראשוניים או ברשימת התרכובות.
איור 1. מספרים ראשוניים. מקור: Wikimedia Commons.
הכרת המספרים הראשוניים היא עוד מימי קדם; המצרים הקדמונים כבר השתמשו בהם והם בוודאי היו ידועים הרבה לפני כן.
מספרים אלה חשובים מאוד, מכיוון שכל מספר טבעי ניתן לייצג על ידי תוצר של מספרים ראשוניים, ייצוג זה הוא ייחודי, למעט בסדר הגורמים.
עובדה זו מבוססת במלואה במשפט הנקרא משפט יסוד האריתמטיקה, הקובע כי מספרים שאינם ראשוניים מורכבים בהכרח ממוצרים של מספרים שהם.
מאפייני מספרים ראשוניים
להלן המאפיינים העיקריים של מספרים ראשוניים:
-הם אינסופיים, מכיוון שלא משנה כמה מספר ראשוני גדול, אתה תמיד יכול למצוא מספר גדול יותר.
-אם מספר ראשוני p לא בדיוק מחלק מספר אחר a, אז אומרים על p ו- a שהם ראשוניים זה לזה. כאשר זה קורה, המחלק המשותף היחיד שיש לשניהם הוא 1.
זה לא הכרחי ש- תהיה ראשית מוחלטת. לדוגמה, 5 הם ראשוניים, ולמרות ש -12 אינם, שני המספרים הם ראשוניים זה לזה, מכיוון שלשניהם יש 1 כמחלק משותף.
-כאשר מספר ראשוני p מחלק כוח של המספר n, הוא גם מחלק את n. הבה נבחן 100 שזה כוח של 10, ספציפית 10 2 . זה קורה ש -2 מחלק גם 100 וגם 10.
-כל המספרים הראשוניים הם מוזרים פרט ל -2, ולכן הספרה האחרונה שלה היא 1, 3, 7 או 9. 5 לא נכלל, כי למרות שהוא מוזר וראשוני, הוא אף פעם לא הנתון הסופי של מספר ראשוני אחר. למעשה כל המספרים שמסתיימים ב -5 הם כפלים של זה ולכן הם לא ראשוניים.
-אם p הוא פריים ומחלק את המוצר של שני מספרים ab, ואז p מחלק אחד מהם. לדוגמה, המספר הראשוני 3 מחלק את המוצר 9 x 11 = 99, שכן 3 הוא מחלק של 9.
כיצד לדעת אם מספר ראשוני
ראשוניות היא השם שניתן לאיכות היותך ראשוני. ובכן, המתמטיקאי הצרפתי פייר דה פרמט (1601-1665) מצא דרך לאמת את הפורמליות של מספר, במשפט הקטן שנקרא פרמה, האומר:
"בהינתן מספר טבעי ראשוני p וכל מספר טבעי גדול מ- 0, נכון ש- p - a הוא מכפיל של p, כל עוד p הוא פריים".
אנו יכולים לאשש זאת באמצעות מספרים קטנים, לדוגמה נניח ש- p = 4, שאנו יודעים שאיננו ראשוני וכבר = 6:
6 4 - 6 = 1296 - 6 = 1290
המספר 1290 אינו מתחלק בדיוק 4, ולכן 4 אינו מספר ראשוני.
בואו נעשה את הבדיקה עכשיו עם p = 5, שהוא ראשוני ו- y = 6:
6 5 - 6 = 7766 - 6 = 7760
7760 מתחלק ב -5, מכיוון שכל מספר שמסתיים ב 0 או 5 הוא. למעשה 7760/5 = 1554. מכיוון שהמשפט הקטן של פרמה מחזיק, אנו יכולים להבטיח ש -5 הם מספר ראשוני.
ההוכחה באמצעות המשפט אפקטיבית וישירה עם מספרים קטנים, בהם קל לבצע את הפעולה, אך מה לעשות אם נתבקש לברר את הפורמליות של מספר גדול?
במקרה כזה המספר מתחלק ברצף בין כל המספרים הראשוניים הקטנים יותר, עד שנמצא חלוקה מדויקת או שהמניין פחות ממחלק.
אם חלוקה כלשהי היא מדויקת, פירוש הדבר שהמספר מורכב ואם המנה פחותה מהמחלק, פירוש הדבר שהמספר הוא ראשוני. נבצע את זה לפועל בתרגיל 2 שנפתר.
דרכים למצוא מספר ראשוני
יש אין ספור מספרים ראשוניים רבים ואין נוסחה אחת לקבוע אותם. עם זאת, מסתכלים על מספרים ראשוניים כמו אלה:
3, 7, 31, 127 …
נציין כי הם מהצורה 2 n - 1, כאשר n = 2, 3, 5, 7, 9 … אנו דואגים לכך:
2 2 - 1 = 4 - 1 = 3 ; 2 3 - 1 = 8 - 1 = 7 ; 2 5 - 1 = 32 - 1 = 31 ; 2 7 - 1 = 128 - 1 = 127
אך איננו יכולים להבטיח שבאופן כללי 2 n - 1 הוא ראשוני, מכיוון שיש כמה ערכים של n שעבורם זה לא עובד, למשל 4:
2 4 - 1 = 16 - 1 = 15
והמספר 15 אינו ראשוני, מכיוון שהוא מסתיים ב- 5. עם זאת, אחד הראשיים הגדולים הידועים, שנמצאו על ידי חישובי מחשב, הוא מהצורה 2 n - 1 עם:
n = 57,885,161
הנוסחה של מרסן מבטיחה לנו ש- 2 p - 1 הוא תמיד פריים, כל עוד p הוא גם פריים. לדוגמה, 31 הוא פריים, כך שבטוח ש -2 31 - 1 גם הוא ראשוני :
2 31 - 1 = 2,147,483,647
עם זאת, הנוסחה מאפשרת לך לקבוע רק מספרים ראשוניים, לא כולם.
הנוסחה של אוילר
הפולינומה הבאה מאפשרת למצוא מספרים ראשוניים בתנאי ש- n הוא בין 0 ל 39:
P (n) = n 2 + n + 41
בהמשך פרק התרגילים שנפתר יש דוגמא לשימוש בו.
המסננת של Eratosthenes
Eratosthenes היה פיזיקאי ומתמטיקאי מיוון העתיקה שחי במאה השלישית לפני הספירה, הוא תכנן שיטה גרפית למצוא את המספרים הראשוניים שאנחנו יכולים להוציא לפועל עם מספרים קטנים, זה נקרא מסננת Eratosthenes (מסננת היא כמו מסננת).
המספרים ממוקמים בטבלה כמו זה שמוצג בהדמיה.
אז המספרים השווים מחולקים, למעט 2 שאנו יודעים שהוא ראשוני. כל האחרים הם כפל של זה ולכן אינם ראשוניים.
הכפולים של 3, 5, 7 ו 11 מסומנים גם הם, לא כולל את כולם כי אנו יודעים שהם ראשוניים.
הכפולים של 4, 6, 8, 9 ו 10 כבר מסומנים, מכיוון שהם מורכבים ולכן מכפילים של כמה מהשנים הראשונות שצוינו.
בסופו של דבר המספרים שנותרו ללא סימון הם ראשוניים.
איור 2. אנימציה של מסננת Eratosthenes. מקור: Wikimedia Commons.
תרגילים
- תרגיל 1
בעזרת פולינום אוילר למספרים ראשוניים, מצא 3 מספרים הגדולים ממאה.
פִּתָרוֹן
זה הפולינום שהציע אוילר למצוא מספרים ראשוניים, שעובד עבור ערכים של n בין 0 ל 39.
P (n) = n 2 + n + 41
על ידי ניסוי וטעייה אנו בוחרים ערך של n, למשל n = 8:
P (8) = 8 2 + 8 + 41 = 113
מכיוון ש- n = 8 מייצר מספר ראשוני העולה על 100, אז אנו מעריכים את הפולינום עבור n = 9 ו- n = 10:
P (9) = 9 2 + 9 + 41 = 131
P (10) = 10 2 + 10 + 41 = 151
- תרגיל 2
גלה אם המספרים הבאים הם ראשוניים:
א) 13
ב) 191
פתרון ל
ה- 13 הוא די קטן בכדי להשתמש במשפט הקטן של פרמה ובעזרת המחשבון.
אנו משתמשים ב- a = 2 כך שהמספרים לא גדולים מדי, אם כי ניתן להשתמש גם ב- a = 3, 4 או 5:
2 13 - 2 = 8190
8190 ניתן לחלוקה ב -2, מכיוון שהיא אחידה, ולכן 13 היא ראשונה. הקורא יכול לאשר זאת על ידי ביצוע אותה מבחן עם a = 3.
פיתרון ב
191 גדול מכדי להוכיח עם המשפט ומחשבון משותף, אך אנו יכולים למצוא את החלוקה בין כל מספר ראשוני. אנו משמיטים לחלק ב -2 מכיוון ש -191 אינו אחיד והחלוקה לא תהיה מדויקת או שהמניין פחות מ -2.
אנו מנסים לחלק ב -3:
191/3 = 63,666 …
וזה לא נותן מדויק, וגם לא המנה פחותה ממחלק (63,666 … גדול משלוש)
אנו ממשיכים ובכך לנסות לחלק 191 בין ראש השנה 5, 7, 11, 13 ולא מגיעים לחלוקה המדויקת, וגם לא המנה פחותה מהמחלק. עד שזה יחולק ב- 17:
191/17 = 11, 2352 …
מכיוון שהוא לא מדויק ו- 11.2352 … הוא פחות מ 17, המספר 191 הוא ראשוני.
הפניות
- Baldor, A. 1986. חשבון. מהדורות והפצות קודקס.
- פריטו, ג. המספרים הראשוניים. התאושש מ: paginas.matem.unam.mx.
- מאפיינים של מספרים ראשוניים. התאושש מ: mae.ufl.edu.
- סמארטיק. מספרים ראשוניים: כיצד למצוא אותם עם מסננת ארטוסטנס. התאושש מ: smartick.es.
- ויקיפדיה. מספר ראשוני. התאושש מ: es.wikipedia.org.