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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

משפט זקנדורף

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

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

סוף סוף הגענו אל האקשן האמיתי. כזכור, עבור $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(n,k\right)=n^{k}$ – "הפונקציה … להמשיך לקרוא

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

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

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

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

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

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

משוואת פל

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

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

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

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

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