Сравнения, остатъци и т.,н.

[Гост]

Здравейте,
Мъчи ме следната задача:

Да се намери остатъкът на (85⁷⁴+17⁹⁵)¹⁵ и 13.

Знам, че трябва да е нещо просто, но отсъствах от първите 2 лекции и сега нямам идея как се решават такива задачки.

Много ще се радвам, ако някой намери време и се опита да разясни поне малко .

[Добромир Глухаров]

[tex]\(85^{74}+17^{95}\)^{15}\equiv ?(mod\ 13)[/tex]

[tex]85=6.13+7\equiv 7(mod\ 13)[/tex]
[tex]17\equiv 4(mod\ 13)[/tex]

Теорема на Ойлер: [tex]a^{\varphi(n)}\equiv 1(mod\ n)[/tex]

[tex]\varphi(13)=12[/tex]

[tex]74=6.12+2\equiv 2(mod\ 12)[/tex]
[tex]95=7.12+11\equiv 11(mod\ 12)[/tex]

[tex]\(85^{74}+17^{95}\)^{15}\equiv \(7^2+4^{11}\)^{15}(mod\ 13)[/tex]

[tex]7^2+4^{11}=49+2^{22}\equiv-3+2^{12+10}\equiv-3+2^{10}\equiv-3+1024\equiv 1021\equiv78.13+7\equiv 7(mod\ 13)[/tex]

[tex]\(85^{74}+17^{95}\)^{15}\equiv 7^{15}\equiv 7^{12+3}\equiv 7^3=343=26.13+5\equiv 5(mod\ 13)[/tex]

Възможно е да съм допуснал някъде техническа грешка в сметките.

[kmitov]

Да не ти пука!

[Гост]

@Добромир Глухаров - Еха, мерси мисля, че го схванах. Намерих в интернет няколко примерни задачки и ще се опитам сам да ги реша .

@ kmitov - за сажаление не е толкова просто

[TheWorst]

Не е ли по-добре с Ферма,защото делим на просто число?
Тоест по-лесно де

[Добромир Глухаров]

Не е ли по-добре с Ферма,защото делим на просто число?
Тоест по-лесно де

В случая наистина е по-добре да се използва Малката теорема на Ферма.

[Knowledge Greedy]

И аз я смятах точно по стъпките на Добромир и получих същото.