Задача с остатък при деление.

[madzhara]

Здравейте,
търся помощ за решението на следната задача, за чието
решение не знам нито един метод:

Да се намери остатъка при деление на
[tex]2^{100}[/tex] + [tex]3^{100}[/tex] на 34.

[Гост1]

Идеята в такива задачи е да намериш някакво число [tex]t[/tex], такова че [tex]2^t\equiv r (mod 34)[/tex], където [tex]r[/tex] е някакво малко число - 1,2,-1,-2. Същото и за числото с основа 3. С решението по-нататък ще разбереш защо правим така.
В случая лесно забелязваме, че [tex]2^5\equiv -2(mod 34)[/tex]. Оттук [tex]2^{100}\equiv(2^5)^{20}\equiv(-2)^{20}\equiv2^{20}\equiv(2^5)^4\equiv(-2)^4\equiv16 (mod 34)[/tex]. За 3 е по-трудно да намерим подходящи числа. Най-удачно в случая е да използваме теоремата на Ойлер (особено като имаме НОД(3,34)=1). Тогава (понеже[tex]\phi(34)=16[/tex]) [tex]3^{16}\equiv1 (mod 34)[/tex] и оттук [tex]3^{100}\equiv3^4(3^{16})^6\equiv3^4\equiv81\equiv13 (mod 34)[/tex]. Събираме получените резултати и получаваме [tex]2^{100}+3^{100}\equiv16+13=29 (mod 34)[/tex].

[angelangel13]

2334÷21