מספר פריק

[עריסטו]

הוכיחו ללא עזרת מחשב שהמספר 4^55+55^4 הוא פריק.

 

[Permafrost]

הוכיחו ללא עזרת מחשב שהמספר 4^55+55^4 הוא פריק.

מכיוון שאפשר תמיד לפרק a^2+b^2 למכפלה של (a+bi) ב- (a-bi) אזי חשבתי על הפירוק :

zzz (2^55+(55^2)i)*(2^55-(55^2)i) zzz​

אבל לא נראה לי כי זה נחשב פירוק...או שזה כן יכול להחשב?

 

[עריסטו]

מכיוון שאפשר תמיד לפרק a^2+b^2 למכפלה של (a+bi) ב- (a-bi) אזי חשבתי על הפירוק :

zzz (2^55+(55^2)i)*(2^55-(55^2)i) zzz​

אבל לא נראה לי כי זה נחשב פירוק...או שזה כן יכול להחשב?

זו לא ההגדרה של מספר פריק.

 

[Permafrost]

זו לא ההגדרה של מספר פריק.

OK, אם "פָרִיק" פרושו רק פקטורים טבעיים, אזי אני מרים ידיים.
אני יודע מיהם שני פקטורי המספר הזה, מכיוון שעשיתי שמוש בכלי חישובי...אך אינני מכיר פרוצדורה לפריקוּת שאינה מבוססת על נסיונות רבים...

 

[AnarchistPhilosopher]

הוכיחו ללא עזרת מחשב שהמספר 4^55+55^4 הוא פריק.

נראה לי אפשר להשתמש במשפט אוילר עם פונקציית totient.
אבל אני עוד לא סגור על הפרטים.

Euler's Totient Function and Euler's Theorem

 

[עריסטו]

הנה עוד מספר להוכחת פריקותו ללא מחשב:
zzz (2^58+1)/5

 

[AnarchistPhilosopher]

הנה עוד מספר להוכחת פריקותו ללא מחשב:
zzz (2^58+1)/5

קשור למספרי Mersenne?

Mersenne prime - Wikipedia

en.wikipedia.org

 

[עריסטו]

קשור למספרי Mersenne?

Mersenne prime - Wikipedia

en.wikipedia.org

לא

 

[Permafrost]

הנה עוד מספר להוכחת פריקותו ללא מחשב:
zzz (2^58+1)/5

Miller-Rabin primality procedure ?
אני זקוק לשפה שניתן להריץ על גבי Windows, באמצעותה ניתן לכתוב סקריפט חישובי קצר עם לולאות...רצוי עם תמיכה ברגיסטרים "רחבים"...

 

[עריסטו]

Miller-Rabin primality procedure ?
אני זקוק לשפה שניתן להריץ על גבי Windows, באמצעותה ניתן לכתוב סקריפט חישובי קצר עם לולאות...רצוי עם תמיכה ברגיסטרים "רחבים"...

לא מילר-רבין.

 

[Permafrost]

נו, עריסטו, גלה את הסוד.
מהי הפרוצדורה שלך? Pollard-Brent?
התקנתי לפני זמן רב מחשבון Wolfram Alpha בסלולאר שלי שהוא מיושן למדי ובכל זאת המחשבון הזה מפרק מספרים אסטרונומיים תוך שבריר שניה בלתי מורגש לאחר שאני לוחץ על סמן "=".
הפקטורים הם 107367629 536903681.

גם את הסכום 4^55+55^4 פרק תוך שבריר שניה בלתי מורגש לשניים: 36028782255016913 36028811782917073...

 

[עריסטו]

שני התרגילים נפתרים באותה צורה:
a^2+b^2=(a+b)^2-2ab
אם במקרה 2ab גם הוא ריבוע אז סיימנו.
ממש סוד...

 

[Permafrost]

שני התרגילים נפתרים באותה צורה:
a^2+b^2=(a+b)^2-2ab
אם במקרה 2ab גם הוא ריבוע אז סיימנו.
ממש סוד...

יפה, אכן פשוט !

 

[הפרבולה1]

אחרי שגיליתה את הסוד הנה הפתרון:

zzz 4^55 + 55^4=(2^55)^2 + (55^2)^2 = [(2^55) + (55^2)]^2 - 2*2^55*55^2 = [(2^55) + (55^2)]^2 - 2^56*55^2 = zzz
zzz = [(2^55) + (55^2)]^2 - (2^28*55)^2 = [(2^55) + (55^2) + (2^28*55)] * [(2^55) + (55^2)-(2^28*55)] = zzz
zzz = 36028811782917073 * 36028782255016913 zzz

 

[Permafrost]

אחרי שגיליתה את הסוד הנה הפתרון:

zzz 4^55 + 55^4=(2^55)^2 + (55^2)^2 = [(2^55) + (55^2)]^2 - 2*2^55*55^2 = [(2^55) + (55^2)]^2 - 2^56*55^2 = zzz
zzz = [(2^55) + (55^2)]^2 - (2^28*55)^2 = [(2^55) + (55^2) + (2^28*55)] * [(2^55) + (55^2)-(2^28*55)] = zzz
zzz = 36028811782917073 * 36028782255016913 zzz​

כן, ברור.
במקרה הראשון עוד "הייתי" בסוג של כיוון כלשהו עם המספרים המרוכבים, אך לאחר מכן עשיתי נסיונות לאתר פרוצדורה שעה שהפתרון פשוט היה "מונח מתחת לאף".
אולם בסופו של דבר, בחינת פריקוּת של מספרים שאינם מן הצורה a^2+b^2 עדיין מתרחשת כהרף-עין במחשבון הנ"ל והשאלה מהי הפרוצדורה המוכרת היעילה ביותר?