Reszta z dzielenia wyrazenia z potega ( p nie pierwsze )

[M4ksiu]

Zadanie z dzielenia polega na znalezieniu reszty ( coz za niespodzianka ) z \(\displaystyle{ ( 102^{70} + 1 )^{35} \mod 111}\). Wiadomo, mozna to zrobic na piechote a mozna uzyc twierdzen. Eulera tutaj nie specjalnie zadziala ze wzgledu na wartosc funkcji dla 111 ( 3 * 37 ). Natomiast nie bardzo wiem jak uzyc malego twierdzenia Fermata dla tego wyrazenia, poniewaz wymaga ono, by p ( tu 111 ) bylo liczba pierwsza. Zakladam zatem, ze nalezy rozdzielic wyrazenie na to dla 3 i na to dla 37, natomiast takiego przykladu nie robilem a takze nie widzialem ( badz nie pamietam abym widzial ). Wynik ma byc rowny 90. Probowalem zrobic to "po najmniejszej linii oporu", ale to nie mialo chyba duzego sensu ( rozpisac to wyrazenie dla 3 i 37, obliczyc reszty i kombinowac jak je polaczyc, czyli "bezsens" ). Jesli ktos bylby tak mily i wytlumaczyl chociaz przejscie do danego porzadku ( czyli to "pseudo-rozdzielenie" przypadkow i ich polaczenie ), to bylbym bardzo wdzieczny.

Z gory dziekuje za pomoc.


Z powazaniem, M4ksiu.

[Fingon]

Było niedawno.
post760843.htm#p760843

[SaxoN]

Przy czym od matematycznej strony warto patrzeć tylko na post maxa

[M4ksiu]

Dzieki. Nie zauwazylem tego tematu szukajac podobnego problemu. Przyjrze sie, przemysle i wroce z watpliwosciami, jesli takowe sie znajda.


Z powazaniem, M4ksiu.

-- 29 sie 2010, o 20:48 --

Hmm, sprobowalem rozwiazac ten uklad, natomiast nie wychodzi mi 91.

Doszedlem do ukladu:
\(\displaystyle{ x \equiv 1 ( \ mod \ 3 )}\)
\(\displaystyle{ x \equiv 17^{-1} ( \ mod \ 37 )}\)

Postanowilem zamienic niewygodne \(\displaystyle{ 17^{-1}}\). Wykonalem wiec zabieg ( RAE ):
\(\displaystyle{ NWD( 17, 37 ) = 1, \\
17 / 37 = 0 + 17 \\
37 / 17 = 2 + 3 \\
17 / 3 = 5 + 2 \\
3 / 2 = 1 + 1 \\
2 / 1 = 2 + 0}\)
Z czego wynika:
\(\displaystyle{ 1 = 3 - 2 = 3 - ( 17 - 5 * 3 ) = 6 * 3 - 17 = 6( 37 - 2 * 17 ) - 17 = 6 * 37 - 13 * 17}\)
i mamy \(\displaystyle{ x = - 13}\). W zestawieniu z mod jest to \(\displaystyle{ x = -13 \ mod \ 37 \to x = 24 \ mod \ 37}\).

\(\displaystyle{ N = 3 * 37 = 111}\)
\(\displaystyle{ x \equiv 1 ( \ mod \ 3 )}\) - \(\displaystyle{ n_1 = N / 3 = 37}\)
\(\displaystyle{ x \equiv 24 ( \ mod \ 37 )}\) - \(\displaystyle{ n_2 = N / 37 = 3}\)

Dla \(\displaystyle{ n_1}\) wyliczamy:
\(\displaystyle{ NWD( 3, 37 ) = 1, \\
3 / 37 = 0 + 3 \\
37 / 3 = 12 + 1 \\
3 / 1 = 3 + 0 \to 1 = 37 - 12 * 3}\)

Dla \(\displaystyle{ n_2}\) jest identycznie tyle, ze pierwsze przeksztalcenie nie jest potrzebne. Dla \(\displaystyle{ n_1 \ x_1 = 1}\), natomiast dla \(\displaystyle{ n_2 \ x_2 = -12}\). Zatem podstawiamy do wzoru na \(\displaystyle{ x}\):
\(\displaystyle{ x = 1 * 1 * 37 + 24 * ( -12 ) * 3 = 37 - 36 * 24 = -827 \ mod \ 111}\), co nie jest rowne 91. =X


Z powazaniem, M4ksiu.

[max]

Czyli wyszło Ci \(\displaystyle{ 61}\), mi też i mojemu komputerowi też.

[M4ksiu]

Dziwne, mialem chyba zacmienie i z dziwnego powodu zalozylem, ze widzialem w "wolfim" 91 a nie 61. oO

Przepraszam za pomylke, dodatkowy spam i stracony czas. >_>

Temat do zamkniecia.


Z powazaniem, M4ksiu.