פולינום בעל ערכים ראשוניים

בספר בתורת המספרים של טום אפוסטול (Apostol) מסתתרת שאלה שנראית תמימה:

מצא את השלם הקטן ביותר \({ x \ge 0}\) כך ש-\({ f(x) = x^2 + x +41 }\) פריק.

נזכיר שמספר טבעי נקרא “פריק” אם הוא מכפלת מספרים קטנים ממנו (כלומר – “פריק” פירושו “לא ראשוני”). 

בבדיקה מגלים שפולינום זה מקבל ערכים ראשוניים עבור כל \({ x=1,2,\dots,39 }\) , ורק בעבור

\({ x=40}\)  מתקבל ערך פריק. זה לא מפתיע שבערך \({ x=40}\) מתקבל ערך פריק שהרי לכל פולינום מהצורה \({ f(x) = x^2 + x +A }\) מקבלים כי \({ f(A-1) = A^2 }\). מה שמפתיע הוא שכל הערכים לפני הם ראשוניים. האם אתם מכירים עוד פולינומים כאלה מהצורה \({ f(x) = x^2 + x +A }\) שנותנים ערכים ראשוניים לכל המספרים הטבעיים הקטנים מ- \({ A-1 }\) ?

ברור ש-  \({ f(x) = x^2 + x +2 }\) מקיים זאת, וגם הצבה של  \({  3, 5,  11,  17 }\) במקום  \({ A }\) נותנת אותה תכונה. האם יש ערכים נוספים של \({ A }\) שעבורם הדבר נכון? ואם לא מה מיוחד בערכי \({ A }\) הללו?

במאמר הזה אני רוצה לספר, בלי הוכחה, על תשובה מפתיעה שניתנה עוד לפני כמאה שנה: יש רק מספר סופי של ערכי \({ A }\) שעבורם הדבר נכון. התכונה נכונה רק כאשר \({A = \frac{d+1}{4}}\), עבור \({ d = 7,11,19,43,67,163  }\).

לא נסביר את רעיון ההוכחה המקורי. נביא רעיון הוכחה אלמנטרי יותר שעושה שימוש במושג שאריות ריבועיות מודולו מספר ראשוני \({ p }\). כדי להסביר מושג זה נבהיר לדוגמה כי השאריות הריבועיות השונות מאפס מודולו \({ 5 }\) הן \({ 1 }\) ו-\({ 4 }\), משום ש:

\({ 1^2 = 1 }\)

\({ 2^2 = 4 }\)

\({ 3^2 = 4 }\)

\({ 4^2 = 1 }\)

שימו לב שמספיק היה לקחת את החזקות הריבועיות של \({ 1 }\) ו- \({ 2 }\). יש לכך סיבה: בשאריות מ-\({ 5 }\), מתקיים  \({ 3=-2 }\) ו-\({ 4=-1 }\). משום כך\({ 3^2 = (-2)^2 = 2^2 }\)  (בשאריות מ-\({ 5 }\)). מאותה סיבה מספיק לקחת את כל החזקות הריבועיות של \({ 1,2, \dots \frac{p-1}{2} }\) מודולו \({ p }\). כלומר מספר השאריות הריבועיות הוא לכל היותר \({ p/2 }\), ולמעשה הוא בדיוק \({ p/2 }\), משום שכל שארית מתקבלת בדיוק פעמיים, משום שלמשוואה ריבועית מן הסוג \({ x^2 = k }\) מודולו \({ p }\) יש לכל היותר שני פתרונות (כמו למשוואות ריבועיות מעל הממשיים)

נסתכל כעת על \({ p=7 }\). הריבועים הם 

\({ 1^2 = 1 }\)

\({ 2^2 = 4 }\)

\({ 3^2 = 2 }\)

כלומר הריבועים מודולו \({ 7 }\) הם: \({ 1,2,4 }\). 

שימו לב ש-\({ 2 }\) הוא גם ריבוע מודולו \({ 7 }\) והוא עצמו ראשוני. אומרים אז ש- \({ 2 }\) הוא ריבוע ראשוני מודולו \({ 7 }\).

באופן דומה, הריבועים מודולו \({ 11 }\) הם \({ 1,3,4,5,9 }\). שימו לב כי \({ 3 }\) ו-\({ 5 }\) הם ריבועים ראשוניים מודולו \({ 11 }\). אפשר להראות שלכל ראשוני \({ p }\) קיימים “הרבה” ראשוניים שהם ריבועים מודולו \({ p }\). שאלה מעניינת בתורת המספרים היא: בהינתן ראשוני \({ p }\), מהו הריבוע הראשוני הקטן ביותר \({ \ell(p) }\)?

הבעיה הזו פתוחה כבר מראשית המאה הקודמת. ההשערה היא שהמספר מאוד קטן. מה שיודעים בשלב זה להוכיח הוא שעבור \({ p }\) מספיק גדול סדר הגודל של  \({ \ell(p) }\) הוא \({ \sqrt{p}}\). אכן, הרבה פחות מן החסם הפשוט \({ p/2 }\).

כעת, אנחנו יכולים לחבר את הבעיה הזו עם הבעיה שפתחנו בה. מתברר שאפשר להוכיח את המשפט הבא:

\({ E_d(x) =  x^2 + x + \frac{d+1}{4} }\) הוא ראשוני לכל \({ d = 0,1, \dots \frac{d+1}{4}-2 }\)  אם ורק אם \({ d }\) ראשוני ומתקיים \({ \ell(d) = \frac{d+1}{4} }\).

כיוון שיודעים להוכיח שעבור \({ d }\) ראשוני סדר הגודל של \({ \ell(d) }\) הוא \({ \sqrt{d}}\) , של-p גדול הוא הרבה יותר קטן מאשר \({ (p+1)/4 }\), ברור כי יש מספר סופי של פולינומים כאלה. למעשה, נכון דבר מפתיע: אין עוד פולינומים כאלה, נוסף לאלה שצויינו לעיל!

Apostol, Tom M. Introduction to Analytic Number Theory (1976). New York-Heidelberg-Berlin, Springer-Verlag

2 תגובות על פולינום בעל ערכים ראשוניים