PDA

צפה בגרסה המלאה : העלאה בחזקה מודולרית



dipsy
03-01-2015, 16:28
שלום.
נתקעתי בחישוב של 2 בחזקת 78 מודולו 91.
ידוע לי ש- 91=13*7

חישבתי
2 בחזקת 78 מוד 13 יצא לי 12.
לאחר מכן חישבתי את 2 בחזקת 78 מוד 7 יצא לי 1.

לפי אוקלידס
מינוס 1 כפול 13 ועוד 2 כפול 7 קוגוואנטי ל-1

ולכן עשיתי ש-
2 בחזקת 78 שווה ל-
מינוס 1 (המקדם של 13) כפול 12 (המוד שיצא לי במוד 13) ועוד 2 (המקדם של 7) כפול 1 (המוד שיצא לי במוד 7) כל זה מוד 91
וקיבלתי 81 ...
כשהתשובה היא 64.

מישהו יכול להסביר לי מה הטעות??

OneProphecy
03-01-2015, 21:03
לא הייתי פותר זאת ככה; הייתי משתמש במשפט אוילר, הקובע כי a^phi(n)=1modn, כאשר phi היא פונקציית אוילר; זה נכון לכל a זר ל-n.

אצלך n=91, ואפשר לחשב את (phi(n, ו-2 זר ל-91 אז אפשר להיעזר במשפט אוילר.