תורת המספרים החישובית עוסקת בחקר אלגוריתמים הרלוונטיים לתורת המספרים. לאלגוריתמים לבדיקה מהירה האם מספר נתון הוא מספר ראשוני ולפירוק לגורמים חשיבות גדולה בקריפטוגרפיה, תחום שהפך את תורת המספרים מענף עיוני לענף שימושי ביותר.
תורת המספרים האדיטיבית - תורה העוסקת בשאלות ובעיות בתורת המספרים המבקשות להציג מספר כסכום של מספרים מקבוצה נתונה. (למשל מספרים מקבוצת ה[ראשוניים] בהשערת גולדבך ומספרים מקבוצת החזקות בבעיית ווארינג)
תורת המספרים ההסתברותית מיישמת שיטות של הסתברות לתורת המספרים, בעיקר לגבי מספר הגורמים הראשוניים של מספר. ממייסדי תורה זו היה פאול ארדש.
היסטוריה.
המספרים הטבעיים מלווים את האדם משחר התרבות. לא ידוע מתי בדיוק נולד העניין בשאלות "מופשטות" הקשורות במספרים, שאלות שאינן קשורות ישירות בספירת עצמים. טבלאות בבליות קדומות, מהתקופה שבין 1900 ל-1600 לפנה"ס, דנות בשלשות פיתגוראיות, דהיינו מספרים שלמים המקיימים את התנאי formula_5. טבלה מפורסמת בשם פלימפטון 322 שנחשבה בתחילה כמכילה רישום עסקאות מסחריות, היא למעשה רשימה מסודרת ומדויקת למדי של שלשות כאלה, אם כי אין זה ודאי שלכך הבבלים כיוונו.
תורת המספרים זכתה לפריחה ביוון הקדומה, במיוחד בעבודותיהם של פיתגורס, אוקלידס ודיופנטוס.
תורמים בולטים לפיתוחו של ענף זה בעת החדשה הם פרמה, אוילר וגאוס.
קרל פרידריך גאוס
יוהאן קרל פרידריך גאוס (בגרמנית: Johann Carl Friedrich Gauß , 30 באפריל 1777 – 23 בפברואר 1855) היה מתמטיקאי, פיזיקאי ואסטרונום גרמני, מגדולי המתמטיקאים של כל הזמנים. גאוס תרם רבות בתחומי האלגברה, תורת המספרים, אנליזה מתמטית, סטטיסטיקה, גאומטריה דיפרנציאלית, גאודזיה, תורת הכבידה, תורת החשמל והמגנטיות, אסטרונומיה, אופטיקה ועוד. המגנום אופוס שלו, "מחקרים אריתמטיים" (Disquisitiones Arithmeticae), נחשב ליצירה המכוננת של תורת המספרים המודרנית, ונודעה לה השפעה כבירה על התפתחות הדיסציפלינות המתמטיות הטהורות בשתי המאות שחלפו מאז פרסומה.
גאוס מכונה לעיתים קרובות בספרות המתמטית "נסיך המתמטיקאים" ו"גדול המתמטיקאים מאז ימי קדם", זאת בשל השפעתו יוצאת הדופן בתחומים רבים של המתמטיקה והמדע.
ביוגרפיה.
גאוס נולד בבראונשווייג שבסקסוניה התחתונה כבן יחיד למשפחת פועלים ענייה. אמו מעולם לא תיעדה את תאריך הלידה שלו, אולם זכרה שהוא נולד ביום רביעי, שמונה ימים לפני חג העלייה, שהוא עצמו מתרחש 39 ימים לפני חג הפסחא. גאוס פתר מאוחר יותר את חידת תאריך לידתו בקונטקסט של מציאת תאריך חג הפסחא, ופיתח שיטות לחשב את מועדי החג בעבר ובעתיד.
גאוס היה ילד פלא. גאוס עצמו סיפר כי עמד על סוד הפעולות האריתמטיות עוד בטרם ידע לדבר. קיימים סיפורים רבים על גאונותו כילד, רובם נחשבים לאגדות. אחד מהם, המובא בספרו של אריק טמפל בל, Men of Mathematics, מספר כי עוד בטרם מלאו לו שלוש שנים, נתגלה להוריו כישרונו המתמטי הייחודי: אביו עסק בהכנת גיליון השכר השבועי של הפועלים שבהשגחתו וביצע במשך מספר דקות את החישובים המסובכים. כאשר סיים את החישוב, אמר לו בנו שנפלה טעות בחישוב, ונקב בתוצאה שחישב בראשו. סיפור מפורסם מבית הספר היסודי מספר כי מורהו של גאוס ביקש להעסיק את תלמידי הכיתה בתרגיל שלפתרונו הייתה דרושה שעה ארוכה. התרגיל היה לחבר את המספרים מ-1 עד 100, ולאחר מספר שניות וגאוס, באותה עת בן 7 בלבד, הניח את לוח-היד שהיה נהוג באותם ימים, קרא "!Lieget se" ("הנה זה מונח", בניב המקומי) ונקב בתוצאה: 5,050. בדיעבד התברר כי הוא גילה את הטור החשבוני בלי להיות מודע לכך: הוא הבחין שסכום האיבר הראשון והאחרון זהה לסכום האיבר השני והלפני האחרון וכן הלאה (1 + 100, 2 + 99, ..., 50 + 51). כלומר כדי למצוא את הפתרון לתרגיל יש להכפיל 101 במספר הזוגות (שהוא מחצית מספר האיברים), וכך מתקבל הפתרון (5,050=101X50).
אביו של גאוס, שהיה חסר השכלה ואב קשוח, רצה כי בנו ימשיך בדרכו ויהיה לבנאי, ולכן התנגד להמשך לימודיו של בנו. אך אמו הכירה בגאונותו של בנה ותמכה בהמשך לימודיו. מורהו, ביטנר, הכיר אף הוא בגאונותו של גאוס והסב אל גאוס את תשומת לבו של הדוכס מבראונשווייג, קרל וילהלם פרדיננד. הדוכס אכן נתן את תמיכתו וחסותו בהמשך לימודיו התיכוניים והאוניברסיטאיים של גאוס.
תחילת דרכו.
גאוס קיבל מלגה מהדוכס, ובשנים 1792 עד 1795 למד ב-Collegium Carolinum (לימים האוניברסיטה הטכנית בבראונשווייג). משם המשיך ללימודים גבוהים באוניברסיטת גטינגן, שם למד עד 1798. בעודו באוניברסיטה, גילה מחדש באופן בלתי תלוי מספר מושגים ומשפטים חשובים: משפט הבינום המוכלל, הממוצע האריתמטי-גאומטרי, ומשפט ההדדיות הריבועית. הפריצה שלו התרחשה ב-1796, כאשר הראה באמצעות הרעיון של הרחבת שדות שכל מצולע משוכלל שמספר צלעותיו הוא מספר פרמה (ועקב כך כל מכפלה של מספר פרמה בחזקה של 2), ניתן לבנייה בסרגל ובמחוגה. תגלית זו הייתה ההתקדמות המשמעותית הראשונה בנושא בניות בסרגל ובמחוגה מזה למעלה מ-2,000 שנה: בעיות בנייה העסיקו מתמטיקאים עוד מימי יוון העתיקה, והייתה להן חשיבות רבה בהתפתחות האלגברה; בזכות האנליזה המעמיקה של פולינומים ציקלוטומיים, הן פתחו שערים לתאוריות מתמטיות עמוקות כמו תורת גלואה. תגלית זו היוותה נקודת מפנה בחייו של גאוס, מכיוון שהניעה אותו לבחור במתמטיקה כקריירה ולא בבלשנות שבה התעניין באותה עת. כחובב בלשנות נלהב שלט גאוס בשפות רבות: גרמנית, יוונית, לטינית, צרפתית, אנגלית ודנית.
1796 הייתה השנה הפרודוקטיבית ביותר עבור גאוס ותורת המספרים. ב-30 במרץ הוא גילה כי מצולע משוכלל בן 17 צלעות ניתן לבנייה בסרגל ומחוגה. גאוס היה גאה מאוד בתגליתו, ואף ביקש שייחרט על מצבתו מצולע משוכלל בן 17 צלעות. הוא פיתח את האריתמטיקה המודולרית, כלי בעל יכולת הפשטה ניכרת בתיאור מניפולציות בתורת המספרים. ב-8 באפריל 1796 היה הראשון שהוכיח את משפט ההדדיות הריבועית, משפט עמוק וכללי המאפשר למתמטיקאים לקבוע קיום פתירות של כל משוואה ריבועית באריתמטיקה מודולרית. גאוס כינה אותו בשם "משפט הזהב", ועדות לחיבה שרחש לו היא שפרסם שש הוכחות שונות שלו במהלך חייו (שתיים נוספות פרי עטו פורסמו לאחר מותו). משפט המספרים הראשוניים, אשר שוער ב-31 במאי, נותן הבנה טובה כיצד מתפלגים המספרים הראשוניים בין המספרים הטבעיים. ב-10 ביולי גאוס גילה שכל מספר טבעי ניתן להצגה כסכום של שלושה מספרים משולשים לכל היותר, ותיעד את התגלית בהערה מפורסמת ביומנו: "אאורקה! ∆ + ∆ + ∆ = num". ב-1 באוקטובר הוא גילה תוצאה על מספר הפתרונות של פולינום בעל מקדמים השייכים לשדה סופי, שהובילה להשערות וייל 150 שנה מאוחר יותר.
שנות הביניים.
בעבודת הדוקטורט שלו משנת 1799, "הוכחה חדשה לכך שכל פולינום במשתנה אחד ניתן לפרק כמכפלה של גורמים ממשיים מן המעלה הראשונה והשנייה", סיפק גאוס הוכחה מבריקה של המשפט היסודי של האלגברה, משפט חשוב ממנו נובע כי לכל פולינום ממעלה n יש בדיוק n שורשים מרוכבים. עבודת הדוקטורט שלו הכילה ביקורת וסקירה מקיפה של ניסיונות הוכחה קודמים של המשפט, שנעשו על ידי אוילר, לגראנז' וד'אלמבר, והיא הייתה העבודה הראשונה שהצביעה על הפגם הבסיסי בהוכחות קודמות אלו של המשפט. ההוכחה שלו הכילה טיעון מקורי, טופולוגי במהותו, והגישה הכללית בה נקט בהוכחה הייתה מקורית. באופן אירוני, גם ההוכחה של גאוס לא הייתה שלמה והיה בה פער לוגי, בשל שימוש "מובלע" במשפט העקום של ז'ורדן, ולפיכך אינה קבילה בסטנדרטים מודרניים. גאוס זיהה את החלל בהוכחתו, ובמרוצת חייו סיפק עוד שלוש הוכחות שונות של תוצאה זו; שתיים נוספות ב-1816 (האחת אלגברית באופיה והשנייה אנליטית), והאחרונה שבהן, ב-1849, נחשבת לדקדקנית ביותר מביניהן לפי הסטנדרטים של היום. מאמציו להוכיח את המשפט היסודי הסירו לחלוטין את הספקות לגבי תקפותם של המספרים המרוכבים.
ב-1801 פרסם גאוס את יצירת המופת הגדולה ביותר שלו: "מחקרים אריתמטיים" (Disquisitiones Arithmeticae) שאת כתיבתה השלים עוד ב-1798, אך החליט לפרסמה רק שלוש שנים מאוחר יותר. ביצירה זו הציג גאוס לראשונה כלי חדש לתיאור בעיות בתורת המספרים - אריתמטיקה מודולרית, הוכיח לראשונה את משפט ההדדיות הריבועית, יצר את תורת התבניות הריבועיות, ויצר תאוריה של בנייה בסרגל ובמחוגה (שעל פיה הוכיח כי המצולע המשוכלל בן 17 צלעות ניתן לבנייה). הניתוח שגאוס נתן בספרו לתורת התבניות הריבועיות היה מעמיק במיוחד, ומלא ברעיונות ובמושגים חדשים. האופן שבו ניתח גאוס בעיות והקונספציה החדשה שהציג בספר, היוו מקור השראה למתמטיקאים במשך דורות רבים אחרי פרסומו. כך למשל, ניתוחו של גאוס את בעיית הבנייה בסרגל ומחוגה הכיל חלק מהאלמנטים הרעיוניים של תורת גלואה, וספר זה היווה מקור השראה לגלואה.
באותה שנה גילה האסטרונום האיטלקי ג'וזפה פיאצי את האסטרואיד קרס. אולם פיאזי היה יכול לעקוב אחריו רק למשך מספר חודשים בלבד, וחלק מסלולו שבו הצליח לצפות היווה רק 3 מעלות בשמי הלילה. לאחר מכן נעלם קרס באופן זמני מאחורי ההילה של השמש. מספר חודשים מאוחר יותר, כשקרס היה אמור להופיע שוב, לא היה מסוגל פיאזי לאתר אותו מחדש: הכלים המתמטיים של התקופה לא היו מסוגלים לבצע חיזוי של מיקום האסטרואיד על פי מידע כל-כך זעום, שכן 3 מעלות מהווים פחות מ-1% ממסלולו של האסטרואיד.