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

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

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

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

בואו נוכיח שיש אינסוף ראשוניים!

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

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

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

משפט ארבעת הריבועים של לגראנז'

אני רוצה לדבר על אחת מהתוצאות הנחמדות ביותר (לטעמי) בתורת המספרים האלמנטרית – משפט ארבעת הריבועים של לגראנז'. בפשטות, המשפט אומר שאפשר להציג כל מספר טבעי בתור סכום של ארבעה ריבועים של מספרים טבעיים (כש-0 נחשב למספר טבעי). הנה דוגמאות עבור המספרים הטבעיים מ-1 עד 7: $latex 1=1^{2}+0^{2}+0^{2}+0^{2}$ $latex 2=1^{2}+1^{2}+0^{2}+0^{2}$ $latex 3=1^{2}+1^{2}+1^{2}+0^{2}$ $latex 4=2^{2}+0^{2}+0^{2}+0^{2}$ $latex …

אז מה זה חשבון מודולרי?

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

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

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

הבעיה העשירית של הילברט – לכל דבר טוב (חסום) יש סוף

בשעה טובה הגענו אל המכשול האחרון שעומד בינינו ובין סיום ההוכחה שהבעיה העשירית של הילברט אינה כריעה – כמת אוניברסלי חסום. אם נצליח להראות שבהינתן ביטוי דיופנטי $latex P$ אפשר להוכיח שגם הביטוי $latex \forall x<n\left(P\right)$ הוא דיופנטי, נסיים. כאן אמורה להיכנס לתמונה העובדה שהוכחנו (בדם יזע ודמעות) שהפונקציה האקספוננציאלית היא דיופנטית. בואו נתחיל בלראות …

למה לא רציונלי לדבר על לא רציונליים (באינסוף)

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

הבעיה העשירית של הילברט – נקמתן של הפונקציות הרקורסיביות והדיופנטיות

בפוסטים הקודמים בסדרה עבדנו קשה כדי להוכיח שהפונקציה האקספוננציאלית היא דיופנטית. הצלחנו בזה סוף סוף ועכשיו אפשר לשכוח מהעניין לבינתיים ולנסות להיזכר מה בעצם אנחנו מנסים להוכיח, ומה האסטרטגיה הכללית שלנו. כזכור, פונקציה דיופנטית היא פונקציה $latex f\left(x_{1},\dots,x_{n}\right)$ כך שקיימת מערכת משוואות דיופנטיות עם המשתנים $latex x_{1},\dots,x_{n},y,z_{1},\dots,z_{n}$ בעלת התכונה הבאה: אם אנו מציבים ערכים $latex …

ראשוני מחוץ לחוק

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

משפט זקנדורף

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

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

סוף סוף הגענו אל האקשן האמיתי. כזכור, עבור $latex a>1$ הגדרנו את משוואת פל $latex x^{2}-dy^{2}=1$ כאשר $latex d=a^{2}-1$, וסימנו בתור $latex x_{n}\left(a\right)$ את סדרת ערכי ה-$latex x$-ים של פתרונות של המשוואה (כשכולם מוצגים בתור "חזקות" של הפתרון היסודי). המטרה שלנו כרגע היא להראות שהפונקציה $latex f\left(a,k\right)=x_{k}\left(a\right)$ היא דיופנטית; לשם כך נציג מערכת משוואות שבה …

הבעיה העשירית של הילברט – איך משוואת פל קשורה לכל העניין?

בואו נחזור לדבר על הבעיה העשירית של הילברט שעזבתי בשיא המתח – בדיוק לפני החלק הטכני ביותר, שנתחיל לטפל בו הפעם. תזכורת קטנה למי שאין לו כוח לקרוא את הפוסטים הקודמים: המטרה שלנו היא להוכיח שהפונקציה $latex f\left(n,k\right)=n^{k}$ – "הפונקציה האקספוננציאלית" – היא דיופנטית. כלומר, שקיימת מערכת של משוואות פולינומיות בשלמים עם המון משתנים ששלושה …

הבעיה העשירית של הילברט – איך מקודדים דיופנטית את כל הסדרות הסופיות?

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

משפט השאריות הסיני

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

הבעיה העשירית של הילברט – פונקציות דיופנטיות וחיות אחרות (רקורסיביות)

אנו ממשיכים בדרך שלנו אל ההוכחה שלא קיים אלגוריתם שפותר את הבעיה העשירית של הילברט. אני מניח שקראתם את פוסט המבוא ולכן קופץ ישר לעניינים הפעם. המושג המרכזי בפוסט הקודם היה קבוצה דיופנטית. זוהי קבוצה $latex S=\left\{ \left(a_{1},\dots,a_{n}\right)\right\} $ של $latex n$-יות של מספרים טבעיים חיוביים, כך שקיים פולינום $latex p\left(x_{1},\dots,x_{n},y_{1},\dots,y_{m}\right)$ בעל התכונה הבאה: למשוואה …

משוואת פל

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

הבעיה העשירית של הילברט – מבוא

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

מספרי ברנולי – ההוכחות

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