שארית חלוקה % ב-10

[white shadow 3]

שארית חלוקה % ב-10

הי.
שאלה קצת מוזרה שנתקעתי בה,. איך אני מוצא (/מוכיח שהתשובה היא 3) מה תוצאת הביטוי:
zz (-3^199)mod10 zz
?

תודה!

 

[הפרבולה]

ככה

3^0 = 1
3^1 = 3
3^2 = 9
3^3 = 27

3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187

3^8 = 6561
......

3^n mod 10 = 3^(n mod 4 ) mod 10
3^199 mod 10 =3^(199 mod 4) mod 10 = 3^3 mod 10 = 7
-3^199 mod 10 = -7 mod 10 = 3

 

[אורי769]

פתרון

נשים לב ש-
QQ 3^4 ≡ 1 mod 10
נשים לב גם ש-196 מתחלק ב-4. לכן
QQ 3^199 ≡ 3^196 * 3^3 ≡ 1 * 3^3 mod 10
לכן
QQ 3^199 ≡ 7 mod 10
ולכן
QQ (-3)^199 ≡ -7 mod 10 ≡ 3 mod 10

 

[white shadow 3]

תודה רבה לשניכם!