PDA

צפה בגרסה המלאה : אריתמטיקה - מציאת שארית



TheZohan
05-04-2014, 16:53
היי
הסתבכתי קצת עם השאלה הבאה, אשמח לעזרה:
מהי שארית החלוקה של 25^25 ל-18?

DeepSpace
05-04-2014, 18:50
הדרך שאני מכיר היא זאת:
נגדיר אופרטור n%m=k שמשמועותו שארית החלוקה של n ב- m היא k.

דוגמאות:

8%3=2

100%2=0

וכו'.

כמו כן חייב להתקיים \frac{n-k}{m}=Z כך ש- Z הוא מספר שלם, ו- 0 \leq k < m.


לכן במקרה שלנו נדרוש:

\frac{25^{25}-k}{18}=Z כך ש- Z יהיה מספר שלם ו- 0 \leq k < 18.


נבדוק את האפשרויות עבור k ונראה שהערך היחיד שמקיים זאת הוא k=7, לכן 25^{25}%{18}=7

TheZohan
05-04-2014, 19:09
הדרך שאני מכיר היא זאת:
נגדיר אופרטור n%m=k שמשמועותו שארית החלוקה של n ב- m היא k.

דוגמאות:

8%3=2

100%2=0

וכו'.

כמו כן חייב להתקיים \frac{n-k}{m}=Z כך ש- Z הוא מספר שלם, ו- 0 \leq k < m.


לכן במקרה שלנו נדרוש:

\frac{25^{25}-k}{18}=Z כך ש- Z יהיה מספר שלם ו- 0 \leq k < 18.


נבדוק את האפשרויות עבור k ונראה שהערך היחיד שמקיים זאת הוא k=7, לכן 25^{25}%{18}=7

לא הבנתי איך הגעת ל- k=7

DeepSpace
05-04-2014, 19:13
לא הבנתי איך הגעת ל- k=7

ע"י זה שעבור ערכי k בין 0 ל- 18 (כולל 0 לא כולל 18) רק k=7 גורם לביטוי \frac{25^{25}-k}{18} להיות מספר שלם.


כיוון אחר שעשוי להוביל לפיתרון בדרך אחרת הוא ש- 25^{25} = 5^{50} כלומר אנו יודעים בוודאות שמדובר במספר שספרתו האחרונה היא 5, ושמספר כלשהו מתחלק ב- 18 (ז"א ששארית החלוקה שלו ב 18 היא 0) אם ורק אם הוא מתחלק גם ב- 2 וגם ב- 9, אבל אני לפחות לא רואה לאן זה מתקדם מכאן...

ShoobyD
06-04-2014, 22:34
מכיוון ש־18 ו־25 זרים זה לזה, נוכל להשתמש במשפט אוילר (https://he.wikipedia.org/wiki/משפט_אוילר).

לפי אוילר: 25^{\phi (18)} \,\equiv\, 1\,\pmod{18}, כאשר \phi היא פונקציית אוילר (https://he.wikipedia.org/wiki/פונקציית_אוילר).


\phi (18) = 18\cdot\frac{1}{2}\cdot\frac{2}{3} = 6
ולכן: 25^6 \,\equiv\, 1\,\pmod{18}


נוכל כעת לצמצם את הביטוי המקורי:


25^{25}\, =\, 25^{24}\cdot 25\, =\, (25^6)^4\cdot25 \,\equiv\, 1^4\cdot 25\,\equiv\, 25\,\equiv\, 7\,\pmod{18}