מספר פריק

From האנציקלופדיה היהודית
Jump to: navigation, search

מספר פָּרִיק הוא מספר שלם חיובי שאפשר לכתוב אותו כמכפלה של שני שלמים גדולים מ-1. מספרים אלה נקראים 'גורמים' של המספר הנתון. כל מספר שלם גדול מ-1 הוא ראשוני או פריק. לדוגמה, המספר 14 הוא פריק מכיוון שאפשר לפרק אותו כמכפלה של 2 ו-7, ולכן 2 ו- 7 הם הגורמים של 14.

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

מספר הוא פריק אם ורק אם (לשם השוואה, משפט וילסון: אם n ראשוני אז ).

בדיקת פריקות ומציאת גורמים[edit | edit source]

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

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

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

הכללות[edit | edit source]

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

קישורים חיצוניים[edit | edit source]

ערך זה מוגש באדיבות ויקיפדיה העברית. (הדף המקורי, רשימת התורמים)
הערך בוויקיפדיה גדול מערך זה ב +74 תווים

לעדכון מוויקיפדיה, לחץ כאן.

NivdakVeushar.png