Mala Fermaova teorema

PostPoslato: Utorak, 13. Januar 2015, 20:16
od Gamma
Naći ostatak dijeljenja broja [inlmath]1234^{4321}[/inlmath] sa [inlmath]11[/inlmath].
Ovaj zadatak se radi preko male Fermaove teoreme. Iskreno slabo mi je to jasno. Sve na internetu što sam tražio za tu teoremu našao sam ali nešto osnovno tipa ovo. Kada kažem nešto osnovno mislim na stvari za šta ona služi ko ju je prvi dokazo šta podrazumjeva ... Uglavnom znam da ona potvrđuje djelivost broja a sada kakve to veze ima sa ostatkom kod dijeljenja stvarno ne znam. Uglavnom imam i rješenje zadatka samo mi treba neko da ga rastumači.

Rješenje:
[inlmath]\mathrm{NZD}(1234,11)=1[/inlmath] pa prema maloj Fermaovoj teoremi slijedi [inlmath]1234^{10}\equiv1\pmod{11}[/inlmath]. Iz toga slijedi [inlmath]1234^{4320}=\left(1234^{10}\right)^{432}\equiv1\pmod{11}[/inlmath]
[inlmath]1234^{4321}=1234^{4320}\times1234\equiv2\pmod{11}[/inlmath], tj. ostatak dijeljenja broja [inlmath]1234^{4321}[/inlmath] sa [inlmath]11[/inlmath] je [inlmath]2[/inlmath].

Rješenje je dosta kratko. Od početka mi ništa nije jasno. Mislim na ono [inlmath]\mathrm{NZD}[/inlmath]. Zapravo šta to znači? Možda bih mogo razumjeti kada bi to razumio. Sada ne znam da li je greška u trećem redu po mome umjesto one tačke treba stavti znak puta. Ali tako su oni napisali.

Re: Mala Fermaova teorema

PostPoslato: Utorak, 13. Januar 2015, 22:21
od ubavic
Idemo redom: [inlmath]\mathrm{NZD}[/inlmath] označava najveći zajednički delilac brojeva. Kada dva broja imaju [inlmath]\mathrm{NZD}=1[/inlmath] za njih kažemo da su uzajamno prosti, što znači da ne možemo podeliti jedan sa drugim bez ostatka.
Mala Fermaova teorema tvrdi da, ako je [inlmath]p[/inlmath] prost broj, za svaki ceo broj [inlmath]a[/inlmath] važi:
[dispmath]a^p\equiv a\pmod{p}[/dispmath]
Ako su brojevi [inlmath]a[/inlmath] i [inlmath]p[/inlmath] uzajamno prosti, teorema se može svesti na oblik [inlmath]a^{p-1}\equiv 1\pmod{p}[/inlmath], koji je i iskorišćen u ovom zadatku. Dakle, pošto važi [inlmath]\mathrm{NZD}\:(1234,11)=1[/inlmath], možemo pisati [inlmath]1234^{11-1}=1234^{10}\equiv1\pmod{11}[/inlmath]. Po pravilu [inlmath]a\equiv b\pmod{m}\;\Rightarrow\;a^e\equiv b^e\pmod{m}[/inlmath], možemo pisati [inlmath]1234^{4320}=\left(1234^{10}\right)^{432}\equiv 1^{432}=1\pmod{11}[/inlmath]. U poslednjem koraku je iskorišćeno pravilo [inlmath]a\equiv b\pmod{m}\;\land\;c\equiv d\pmod{m}\;\Rightarrow\;ac\equiv bd\pmod{m}[/inlmath], tj. [inlmath]1234^{4320}\equiv1\pmod{11}\;\land\;1234\equiv2\pmod{11}\;\Rightarrow\;1234^{4320}\times 1234\equiv1\times 2\pmod{11}[/inlmath].

Gamma je napisao: Sada ne znam da li je greška u trećem redu po mome umjesto one tačke treba stavti znak puta. Ali tako su oni napisali.

Treba da stoji znak množenja. Ispravio sam to.

Re: Mala Fermaova teorema

PostPoslato: Sreda, 14. Januar 2015, 02:24
od Gamma
Evo sve sam ovo pregledo ostalo mi je par nejasnoća.Jeste da ima veoma malo literature za ovo na našem jeziku.A i to što ima reko sam sve je to nešto uopšteno.Zanima me da li postoje dokazi za ovu teoremu i pravila ? Možda malo i komplikujem ali interesuje me to.Ja mislim da imaju ali naravno nisam ih mogao naći. Predpostavljam da je to nešto komplikovano dok tamo kaže da je Ferma objavio teoremu bez ikakvih dokaza.

ubavic je napisao:[inlmath]\mathrm{NZD}\:(1234,11)=11[/inlmath]

valjda ovde treba [inlmath]1[/inlmath] a ne [inlmath]11[/inlmath]

ubavic je napisao:[inlmath]1234\equiv2\pmod{11}[/inlmath]

Jedino ovaj dio mi nije jasan nikako a ovo ostalo jasno mi je poprilično.Ako se došlo preko formule [inlmath]a^p\equiv a\pmod p[/inlmath] uzimajući [inlmath]11[/inlmath] za [inlmath]p[/inlmath] i [inlmath]2[/inlmath] za [inlmath]a[/inlmath] [inlmath]2^{11}\ne1234[/inlmath]

Re: Mala Fermaova teorema

PostPoslato: Sreda, 14. Januar 2015, 10:07
od ubavic
Dokaz, naravno, postoji. Zapravo, postoji mnogo načina da se dokaže ova teorema (Postoji jednostavan dokaz, ali sam ga ja zaboravio. Ako ga neko zna neka ga napiše molim :zubo: ).
Ferma je mnogo teorema objavio bez dokaza, koje su drugi matematičari kasnije dokazali. Da bi neki stav bio teorema, mora se prvo dokazati.

Veoma sam detaljno objasnio poslednji korak u kome je korišćeno pravilo [inlmath]a\equiv b\pmod{m}\;\land\;c\equiv d\pmod{m}\;\Rightarrow\;ac\equiv bd\pmod{m}[/inlmath] i činjenice da je [inlmath]1234^{4320}\equiv1\pmod{11}[/inlmath], [inlmath]1234\equiv2\pmod{11}[/inlmath] i [inlmath]1234^{4320}\times 1234=1234^{4321}[/inlmath].

Gamma je napisao:
ubavic je napisao:[inlmath]\mathrm{NZD}\:(1234,11)=11[/inlmath]

valjda ovde treba [inlmath]1[/inlmath] a ne [inlmath]11[/inlmath]

Pardon, greška. Ispravljeno

Re: Mala Fermaova teorema

PostPoslato: Sreda, 14. Januar 2015, 15:51
od Gamma
Sada ne znam koliko sam bio precizan. Ne zbunjuje me to pravilo. Već ta druga činjenica kako se došlo do toga ? [inlmath]1234\equiv2\pmod{11}[/inlmath] Nije valjda da se [inlmath]c[/inlmath] i [inlmath]d[/inlmath] mogu proizvoljno odabrati ?

Re: Mala Fermaova teorema

PostPoslato: Sreda, 14. Januar 2015, 17:21
od Gamma
Evo pregledo sam sve ovo još jednom. I došao sam do nekoga svoga zaključka.
Pitanje je da li [inlmath]1234\equiv2\pmod{11}[/inlmath] imam ikakve veze sa Fermaovom teoremom?Zapravo da li se on dobio preko nje?Mislio sam da se znak [inlmath]\equiv[/inlmath] upotrebljava isključivo u ovoj teoremi. A koliko vidim poenta izraza [inlmath]1234\equiv2\pmod{11}[/inlmath] je za daje ostatak [inlmath]2[/inlmath] pri djeljenju broja [inlmath]1234[/inlmath] sa brojem [inlmath]11[/inlmath]. Koliko sam skontao to je poenta čitave priče. Kada smo već kod ove priče s znakom [inlmath]\equiv[/inlmath]. Zanima me gdje se on koristi i za šta služi? Ja nisam imao priliku da se susrećem često s njim. Mislio sam da je identičan kao znak [inlmath]=[/inlmath].

Re: Mala Fermaova teorema

PostPoslato: Četvrtak, 15. Januar 2015, 20:14
od ubavic
Znak [inlmath]\equiv[/inlmath] u teoriji brojeva (a ne samo u Fermaovoj teoremi) predstavlja kongruenciju po modulu. Kongruencija po modulu je, kao i jednakost [inlmath]=[/inlmath], relacija ekvivalenicije, pa i ima osobine simetričnosti, refleksivnosti i tranzitivnosti. Kongruenciju po modulu definišemo na sledeći način:
[dispmath]a\equiv b\pmod{m}\;\Leftrightarrow\;m\:|\:a-b[/dispmath]
Vertikalna crta označava da broj [inlmath]m[/inlmath] deli razliku brojeva [inlmath]a[/inlmath] i [inlmath]b[/inlmath], što se može napisati kao [inlmath]a=km+b\;(k\in\mathbb{Z})[/inlmath]. Ako je [inlmath]b<m[/inlmath], onda kongruenciju po modulu možemo shvatiti onako kako si ti opisao: da je [inlmath]b[/inlmath] ostatak prilikom deljenja [inlmath]a[/inlmath] sa [inlmath]m[/inlmath]. Međutim, [inlmath]b[/inlmath] može biti veće od [inlmath]m[/inlmath] i biti i dalje kongruentno sa [inlmath]a[/inlmath] po modulu [inlmath]m[/inlmath]. Zbog toga imamo binarnu operaciju [inlmath]\bmod\:n[/inlmath] koja označava ostatak prilikom deljenja sa brojem. Npr:
[dispmath]6\equiv16\equiv26\equiv\cdots\pmod{10}\\
(26\bmod10)=6\quad\text{ pošto je }26=2\times10+6[/dispmath]
Obrati pažnju na to da sam u prvom izrazu koristio relaciju kongruencije po modulu, dok sam u drugom izrazu koristo znak jednakosti i operaciju [inlmath]\bmod[/inlmath]. Zapravo, odnos između ova dva pojma (relacije i operacije) može se ovako iskazati:
[dispmath]a\equiv b\pmod{m}\;\Leftrightarrow\;(a\bmod m)=(b\bmod m)[/dispmath]

Što se tiče pravila, mislim da su ti najbitnija ova:
Za brojeve [inlmath]a,b,c,d\in\mathbb{Z}\quad m\in\mathbb{N}[/inlmath] takve da [inlmath]a\equiv b\pmod{m}[/inlmath] i [inlmath]c\equiv d\pmod{m}[/inlmath], važi:
1. [inlmath]a+c\equiv b+d\pmod{m}[/inlmath]
2. [inlmath]a-c\equiv b-d\pmod{m}[/inlmath]
3. [inlmath]ac\equiv bd\pmod{m}[/inlmath]
4. [inlmath]a^e\equiv b^e\pmod{m}[/inlmath]

Re: Mala Fermaova teorema

PostPoslato: Petak, 16. Januar 2015, 00:11
od Gamma
Moraću malo detaljnije da proučim tu teoriju brojeva.Mislim ono sve od početka.Predpostavljam da se to radi na fakultetu. Jer nju tokom čitavog školovanja nismo takli.Mada najbitnije je da sam shvatio kako se radi ovaj zadatak.