70^{n+1} - 69n - 70 се дели на 69^2

[justme.h]

1) Да се докаже, че за всяко неотрицателно число n числото [tex]a_n = 70^{n+1} - 69n - 70[/tex] се дели на числото [tex]69^2[/tex]
2) Да се намерят последните две цифри на числото [tex]537^{781} + 327^{181}[/tex]

[nevrodermit]

1)
Индукция по [tex]n[/tex]
- [tex]n=1[/tex], [tex]a_1=70^2-69-70=70.69-69=69.69[/tex]
- нека [tex]69^2|a_n[/tex] за някое [tex]n[/tex]. Тогава [tex]70^{n+1}=69n+70 \pmod{{69^2}}[/tex]
- за [tex]a_{n+1}=70^{n+2}-69(n+1)-70\equiv 70(69n+70)-69(n+1)-70\equiv 70.69(n+1)-69(n+1)=(n+1)69^2[/tex], т.е. пак се дели на [tex]69^2[/tex]
Доказано.

2)
Щом търсим последните 2 цифри, значи търсим остатъка при деление на [tex]100[/tex]
[tex]\varphi(100)=100.\frac{1}{2}\frac{4}{5}=40[/tex]
Значи за [tex]a[/tex] такова, че [tex]d(a,10)=1\Rightarrow[/tex] [tex]a^{40}\equiv 1 \pmod{100}[/tex]

Очевидно [tex]d(537,10)=d(327,10)=1[/tex]
Имаме
[tex]537^{781}\equiv 537^{19.40+21}\equiv (537^{40})^{19}537^{21}\equiv 537^{21}\equiv 37^{21}\equiv 9^3.36^3\equiv 29.56\equiv 24 \pmod{100}[/tex]
С елката смятаме [tex]37^6\equiv 9 \pmod{100}\Rightarrow 37^{21}\equiv (37^6)^3.36^3 \equiv 9^3.56\equiv 24 \pmod{100}[/tex]
За другата степен
[tex]327^{181}\equiv (327^{40})^4.327^{21}\equiv 327^{21}\equiv 27^{21}[/tex]
С елката смятаме [tex]27^5\equiv 7 \pmod{100}[/tex].
[tex]27^{21}\equiv (27^5)^427\equiv 7^427\equiv 27 \pmod{100}[/tex]
Значи отговорът е [tex]24+27=51[/tex]

[justme.h]

Благодаря за бързия отговор!

[Гост]

This reply is not correct. Both numbers are odd so that their sum must be even!

[nevrodermit]

yes,
[tex]37^{21}\equiv 9^3.37^3\equiv 29.53\equiv 37[/tex]

[justme.h]

yes,
[tex]37^{21}\equiv 9^3.37^3\equiv 29.53\equiv 37[/tex]

За кое точно става въпрос?