Остатъкът при деление на 111 е ?

[Mr.G{}{}Fy]

Да се намери остатъкът от делението на [tex](12 371^{56}+34)^{28}[/tex] с [tex]111[/tex].

[milki]

Samo probvam.... ne znam dali taka se re6ava ....
[tex]111 = 3 * 37[/tex]
[tex]12371/37 = 334 + ostatuk 13[/tex]
[tex]12371^{56}/37 = X + 13^{56}/mod(37)[/tex]
interesuvame se samo ot ostatuka ottuk natatuk na [tex]13^{56}/mod(37)[/tex]
[tex]13^{56} = (13^{2})^{28} => 21^{28} => (21^{2})^14 => (34^{2})^7 => 9^{7} = 3^{14} => (3^{7})^2 =>4^{2} = 16[/tex]
pri delene na 12371^{56}/37 ostatuka e 16
34/ mod(37) = 34
34+16 = 50/mod(37) =13
[tex]13^{28}/mod(37) = 34[/tex]
po su6tiq na4in pri delene na 3 se polu4ava ostatuk 1
sega trqbva da se nameri 4islopo malko ot 111 taka 4e pridelene na 3 ostatuka mu e edno a pri delene na 37 e 33
toest 33 ne stava 33/3 =11
70 OK
114 > 111 toest ve4e ne stava

[mkmarinov]

[tex](12371^{56}+34)^{28} \equiv (50^{56}+34)^{28} \equiv (34^{14}+34)^{28} \equiv 34^{28}(34^{13}+1)^{28} \equiv 7^7(34^{4.3+1}+1)^{28}\equiv \\ \equiv 44.341^{28} \equiv 44.8^{28} \equiv \equiv 44.(-11)^7 \equiv -4.11^8 \equiv -4.10^4 \equiv -40 \equiv 71(mod 111)[/tex]