Ostatak deljenja

Ostatak deljenja 10.03.2012. u 19:21 · pre 178 meseci #1

Naći ostatak dijeljenja broja 1234^1234 sa 11.
Na kom principu se rade ovi zadatci.. Niti mogu da napišem 1234, kao 11 na neki stepen, niti..

Re: Ostatak deljenja 10.03.2012. u 19:50 · pre 178 meseci #2

Moze ovako - po maloj Fermaovoj teoremi $a^{\phi(n)} \equiv 1 \pmod{n}$ . Posto je 11 prost broj $\phi(11) = 10$ . $1234^{1234} = 1234^{10 \cdot 123 + 4} = 1234^{10 \cdot 123} \cdot 1234^{4}$ . Posto je $1234^{10} \equiv 1 \pmod{11}$ , onda je $1234^{10 \cdot 123} \equiv 1 \pmod{11}$ . Odatle je $1234^{1234} \equiv 1234^{4} \pmod{11}$ , $1234^{4} \equiv 5 \pmod{11}$

Re: Ostatak deljenja 10.03.2012. u 20:31 · pre 178 meseci #3

Moze jos da se iskoristi da je $1234 \equiv 2 \pmod{11}$ pa umesto $1234^4$ imali bi $2^4 = 16 \equiv 5 \pmod{11}$

Re: Ostatak deljenja 10.03.2012. u 21:19 · pre 178 meseci #4

Citat:

Picsel: Moze ovako - po maloj Fermaovoj teoremi $a^{\phi(n)} \equiv 1 \pmod{n}$ .

Samo jedna mala ispravka, ovo je Ojlerova teorema, a posledica Ojlerove tereme je Mala Fermaova teorema za $n\in Prost$ ( $n$ je prost broj).

Inace, funkcija $\phi(n)$ (poznatija i kao Ojlerova funkcija, negde se zapisuje i kao $\varphi$ ) nam govori koliko ima brojeva izmedju (ukljucujuci) $1$ i $n$ koji su uzajamno prosti sa $n$ . Pa se zbog toga moze reci da je $\phi(p)=p-1$ gde je $p$ prost broj. A samim tim se moze reci da je $a^{p-1}\equiv 1\pmod{p}$ (sto i predstavlja Malu Fermaovu teoremu, uz uslov da je i $\hbox{nzd}(a,p)=1$ ).

Takodje (ne skodi malo informacija) Ojlerova funkcija predstavlja red Ojlerove grupe $\Phi$ ( $|\Phi(n)|=\phi(n)$ ), gde je:

$\Phi(n)=\{x\in Z_n|\hbox{nzd}(n,x)=1\}$

Na primer, $\Phi(6)=\{1,5\}, \phi(6)=2$ .

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Ostatak deljenja 10.03.2012. u 21:54 · pre 178 meseci #5

Ajd' i ja da dodam jos nesto malo, "sa druge strane", hocu recu jedan osnovnoskolski rezon... Posto sam i sam zaboravio na ovu teoremu (ako sam je ikad i znao :), krenuo sam ovako:

prvo sam redukovao 1234 na 2 (mod 11). Zatim sam, naoruzan strpljenjem trazio stepene dvojke (mod 11) verujuci da ce negde poceti da se ponavljaju:
2 4 8 5 10 9 7 3 6 1 2 i eto, desilo se posle 10og stepena... E sad zasto je bas 10 i zasto su samim tim svi ostaci razliciti, to je za one koji hoce vise :) a moze dovesti do same navedene teoreme.

Elem, sada jos ostaje da se, koristeci 1234=10*123+4 zakljuci da dati broj ima isti ostatak posle deljenja sa 11 kao i broj 2^4=16. a to je 5.

Forum kao aplikacija na telefonu

Srodne teme