סדרות לוקאס ומבחני ראשוניות

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

שני דברים מתפלגים אחיד: ראשוניים וטעויות בעיתונים (ואני לא בטוח בקשר לראשוניים)

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

מה הקשר בין מספרים ראשוניים וקריפטוגרפיה?

לפני חודש ומשהו נתגלה המספר הראשוני הגדול ביותר שנתגלה אי פעם (זה קורה אחת לכל כמה שנים), וגילוי שכזה תמיד מעורר שאלות מתבקשות של "בשביל מה זה טוב?". אם ניכנס לטוקבקים במאמר על התגלית ב-Ynet נגלה שבציבור הרחב, התחום שאליו מספרים ראשוניים מתקשרים ישירות הוא קריפטוגרפיה: "למספר יש חשיבות גדולה בהצפנה" אומר אחד. זה לא …

אז איך באמת בודקים ראשוניות (בעזרת אלגוריתם מילר-רבין)?

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

משפט דיריכילה על סדרות חשבוניות

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

הוכחת אוילר לקיום אינסוף ראשוניים

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