Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI TEORIJA BROJEVA

Mala Fermaova teorema

[inlmath]a^p\equiv a\pmod p,\;a\in\mathbb{Z},\;p\in\mathbb{P}[/inlmath]

Mala Fermaova teorema

Postod Gamma » Utorak, 13. Januar 2015, 21:16

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.
Poslednji put menjao ubavic dana Utorak, 13. Januar 2015, 22:54, izmenjena 2 puta
Razlog: Uređivanje Latex koda.
Gamma  OFFLINE
 
Postovi: 1009
Zahvalio se: 183 puta
Pohvaljen: 239 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +2

Re: Mala Fermaova teorema

Postod ubavic » Utorak, 13. Januar 2015, 23:21

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.
Korisnikov avatar
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 543
Lokacija: Zrenjanin
Zahvalio se: 350 puta
Pohvaljen: 532 puta

Re: Mala Fermaova teorema

Postod Gamma » Sreda, 14. Januar 2015, 03:24

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]
Gamma  OFFLINE
 
Postovi: 1009
Zahvalio se: 183 puta
Pohvaljen: 239 puta

Re: Mala Fermaova teorema

Postod ubavic » Sreda, 14. Januar 2015, 11:07

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
Korisnikov avatar
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 543
Lokacija: Zrenjanin
Zahvalio se: 350 puta
Pohvaljen: 532 puta

Re: Mala Fermaova teorema

Postod Gamma » Sreda, 14. Januar 2015, 16:51

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 ?
Gamma  OFFLINE
 
Postovi: 1009
Zahvalio se: 183 puta
Pohvaljen: 239 puta

Re: Mala Fermaova teorema

Postod Gamma » Sreda, 14. Januar 2015, 18:21

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].
Gamma  OFFLINE
 
Postovi: 1009
Zahvalio se: 183 puta
Pohvaljen: 239 puta

  • +1

Re: Mala Fermaova teorema

Postod ubavic » Četvrtak, 15. Januar 2015, 21:14

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]
Korisnikov avatar
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 543
Lokacija: Zrenjanin
Zahvalio se: 350 puta
Pohvaljen: 532 puta

Re: Mala Fermaova teorema

Postod Gamma » Petak, 16. Januar 2015, 01:11

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.
Gamma  OFFLINE
 
Postovi: 1009
Zahvalio se: 183 puta
Pohvaljen: 239 puta


Povratak na TEORIJA BROJEVA

Ko je OnLine

Korisnici koji su trenutno na forumu: Google [Bot] i 7 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Ponedeljak, 06. April 2020, 17:13 • Sva vremena su u UTC + 1 sat [ DST ]
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs