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

Da li je broj prost

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

Moderator: Corba248

Da li je broj prost

Postod Hmen » Nedelja, 12. Maj 2019, 14:15

Da li je broj
[dispmath]x^2+x+41[/dispmath] prost za svako [inlmath]x[/inlmath] u skupu prirodnih brojeva? Proveravanjem dobijam da za [inlmath]x=40[/inlmath] broj nije prost. Da li ovo može da se dokaže bez proveravanja?
Hmen  OFFLINE
 
Postovi: 1
Zahvalio se: 0 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

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

Re: Da li je broj prost

Postod Jovan111 » Nedelja, 12. Maj 2019, 15:58

Pozdrav! Jedino što mi pada na pamet jeste da ako primetimo
[dispmath]x^2+x+41=x(x+1)+41[/dispmath] lako možemo zaključiti da bi ceo polazni izraz bio deljiv sa [inlmath]41[/inlmath] ako je [inlmath]x=41[/inlmath] ili [inlmath]x=40[/inlmath] (jer je tada [inlmath]x+1=41[/inlmath]). Tada bi, razume se, [inlmath]x^2+x+41[/inlmath] bio složen broj. Takođe, lako se primećuje da bismo, ako bismo direktno proveravali, to uludo radili za prvih [inlmath]39[/inlmath] prirodnih brojeva, jer je za [inlmath]x<40[/inlmath] očigledno izraz prost broj.
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 136
Zahvalio se: 45 puta
Pohvaljen: 157 puta

  • +1

Re: Da li je broj prost

Postod primus » Utorak, 16. Jul 2019, 14:44

Jovan111 je napisao:Takođe, lako se primećuje da bismo, ako bismo direktno proveravali, to uludo radili za prvih [inlmath]39[/inlmath] prirodnih brojeva, jer je za [inlmath]x<40[/inlmath] očigledno izraz prost broj.

Nije mi jasan navedeni deo vašeg rezonovanja. Da li možete malo pojasniti tvrdnju da je za svako [inlmath]x<40[/inlmath] izraz očigledno prost?
Korisnikov avatar
primus  OFFLINE
 
Postovi: 28
Zahvalio se: 2 puta
Pohvaljen: 28 puta

Re: Da li je broj prost

Postod Jovan111 » Utorak, 16. Jul 2019, 18:27

Razlog takvog rezonovanja leži u tome da je izraz
[dispmath]x(x+1)+41[/dispmath] deljiv sa [inlmath]41[/inlmath] akko je i [inlmath]x(x+1)[/inlmath] deljivo sa [inlmath]41[/inlmath] (to jest ako je [inlmath]x=41[/inlmath] ili [inlmath]x=40[/inlmath]). Tada se vidi da ako unesemo bilo koje [inlmath]x<40[/inlmath] da izraz [inlmath]x(x+1)[/inlmath] ne bi mogao da bude deljiv sa [inlmath]41[/inlmath], pa ni [inlmath]x(x+1)+41[/inlmath] ne bi bilo deljivo sa [inlmath]41[/inlmath], tj. [inlmath]x^2+x+41[/inlmath] ne bi bilo deljivo sa [inlmath]41[/inlmath], jer za bilo koje [inlmath]x<40[/inlmath] nijedan od činilaca proizvoda [inlmath]x(x+1)[/inlmath] nije deljiv sa [inlmath]41[/inlmath].
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 136
Zahvalio se: 45 puta
Pohvaljen: 157 puta

  • +1

Re: Da li je broj prost

Postod primus » Utorak, 16. Jul 2019, 19:29

Ali iz toga što [inlmath]x(x+1)+41[/inlmath] nije deljivo sa [inlmath]41[/inlmath] za [inlmath]x<40[/inlmath] ne sledi nužno da je [inlmath]x^2+x+41[/inlmath] prost broj za svako [inlmath]x<40[/inlmath].
Poslednji put menjao Daniel dana Utorak, 16. Jul 2019, 23:28, izmenjena samo jedanput
Razlog: Uklonjen nepotreban citat celog prethodnog posta – tačka 15. Pravilnika
Korisnikov avatar
primus  OFFLINE
 
Postovi: 28
Zahvalio se: 2 puta
Pohvaljen: 28 puta

Re: Da li je broj prost

Postod Jovan111 » Utorak, 16. Jul 2019, 21:31

Dobro, onda mi daj neki kontraprimer ili koji još uslov treba da navedem da bi postigao nužnost u implikaciji koju sam izveo, pošto ja stojim iza onog što sam rekao. Ne znam da li si imao/la u vidu da je u tekstu zadatka rečeno da je [inlmath]x[/inlmath] prirodan broj, a takođe ne znam da li želiš da ukažeš na grešku u mom postupku (koje, po meni, nema) ili ti nije jasno ono što sam ja napisao.



Priložiću i proširenje mog razmišljanja koje će ti približiti moje tvrđenje da je za [inlmath]x<40[/inlmath] izraz [inlmath]x^2+x+41=x(x+1)+41[/inlmath] prost broj. Da bi izraz [inlmath]x(x+1)+41[/inlmath] bio složen oba sabirka moraju biti deljiva istim brojem različitim od [inlmath]1[/inlmath] - pošto je [inlmath]41[/inlmath] prost broj, onda možemo proveriti samo da li je [inlmath]x(x+1)[/inlmath] deljivo sa [inlmath]41[/inlmath].
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 136
Zahvalio se: 45 puta
Pohvaljen: 157 puta

Re: Da li je broj prost

Postod Jovan111 » Utorak, 16. Jul 2019, 21:56

Zanimljivo je ipak i to da ne mora [inlmath]x(x+1)[/inlmath] da bude deljivo sa [inlmath]41[/inlmath] da bi [inlmath]x(x+1)+41[/inlmath] bio složen broj, ali ipak i dalje važi da je za [inlmath]x<40[/inlmath] izraz [inlmath]x(x+1)+41[/inlmath] prost broj. Prost primer toga bi bio broj [inlmath]x=44[/inlmath] za koji je [inlmath]x(x+1)+41=2021[/inlmath], što jeste složen broj jer važi [inlmath]2021=43\cdot47[/inlmath].
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 136
Zahvalio se: 45 puta
Pohvaljen: 157 puta

  • +2

Re: Da li je broj prost

Postod primus » Sreda, 17. Jul 2019, 05:34

Jovan111 je napisao:Dobro, onda mi daj neki kontraprimer ili koji još uslov treba da navedem da bi postigao nužnost u implikaciji koju sam izveo, pošto ja stojim iza onog što sam rekao.

Na osnovu ovoga što si rekao moglo bi se formulisati sledeće uopšteno "pravilo":

Neka je dat polinom [inlmath]x^2+x+p[/inlmath] gde je [inlmath]p\in\mathbb{P}[/inlmath] i [inlmath]x\in\mathbb{N}[/inlmath]. Tada važi da je [inlmath]x^2+x+p[/inlmath] prost broj za svako [inlmath]x<p-1[/inlmath].

Ali uzmimo na primer da je [inlmath]p=19[/inlmath] i [inlmath]x=1[/inlmath], tada je [inlmath]x^2+x+p=21[/inlmath] što je složen broj deljiv sa [inlmath]3[/inlmath] i [inlmath]7[/inlmath]. To bi bio kontraprimer.

Potreban i dovoljan uslov da bi [inlmath]x^2+x+p[/inlmath] bio prost broj jeste da nije deljiv ni sa jednim prostim brojem manjim ili jednakim od [inlmath]\sqrt{x^2+x+p}[/inlmath].



Jovan111 je napisao:Da bi izraz [inlmath]x(x+1)+41[/inlmath] bio složen oba sabirka moraju biti deljiva istim brojem različitim od [inlmath]1[/inlmath].

Ovo je mesto gde grešiš. Da bi neki broj bio deljiv sa nekim drugim brojem njegovi sabirci ne moraju nužno biti deljivi sa tim brojem. Uzmimo npr: [inlmath]2+19=21[/inlmath]. Očigledno u ovom slučaju nijedan od sabiraka nije deljiv sa [inlmath]3[/inlmath], dok je zbir deljiv sa [inlmath]3[/inlmath].
Korisnikov avatar
primus  OFFLINE
 
Postovi: 28
Zahvalio se: 2 puta
Pohvaljen: 28 puta

Re: Da li je broj prost

Postod Onomatopeja » Sreda, 17. Jul 2019, 11:32

Polinom [inlmath]n^2+n+41[/inlmath] (koji je poznat i pod imenom Ojlerov polinom) je poznat primer polinoma koji ima proste vrednosti za sve prirodne brojeve [inlmath]0\leq n<40[/inlmath], a da ne daje proste brojeve za sve vrednosti [inlmath]n\in\mathbb{N}[/inlmath]. To je obicno dobar primer da za matematicku indukciju nije dovoljno proveriti samo pocetne vrednosti, tj. da bi ovde neko mogao da proveri vrednosti od [inlmath]n=0[/inlmath] do [inlmath]n=27[/inlmath] (na primer), te bi odatle naivno pomislio da polinom daje uvek proste brojeve kao svoje vrednosti.

Moze se rucno ili preko nekog programa proveriti da su zaista za sve [inlmath]n<40[/inlmath] vrednosti proste ovog polinoma. Ali to ovde verovatno nije cilj, da racunamo toliko. Sa druge strane, meni nije poznato da postoji elementaran dokaz koji potkrepljuje ovu cinjenicu. Obicno se to ili moze redukovati na ispitivanje odgovarajucih vrednosti Ležandrovog simbola, a ako zelimo jos direktnije (sa manje racuna, a vise teorije), onda se to zasniva na algebru, tj. teoriju prstena i polja.

Na primer, moze se naci da vazi i sledeci zanimljiv rezultat: [inlmath]n^2+n+p[/inlmath] daje proste vrednosti za sve prirodne brojeve [inlmath]n\in[0,p-2][/inlmath] ako i samo ako je [inlmath]4p-1[/inlmath] Heegner-ov broj. Veza broja [inlmath]4p-1[/inlmath] sa prethodnim polinomom je ta sto je diskriminanta tog polinoma jednaka [inlmath]1-4p[/inlmath]. Naravno, ovde se smatra da je [inlmath]p[/inlmath] neki prost broj. Takodje, [inlmath]p=41[/inlmath] je najveci takav broj (medju prostim).
Poslednji put menjao Onomatopeja dana Sreda, 17. Jul 2019, 11:47, izmenjena samo jedanput
 
Postovi: 598
Zahvalio se: 15 puta
Pohvaljen: 565 puta

  • +2

Re: Da li je broj prost

Postod Jovan111 » Sreda, 17. Jul 2019, 11:47

Nakon izvesnog razmišljanja o pitanju koje je postavljeno uvideo sam da sam olako i pogrešno doneo neke zaključke, i zaista primedbe koje je @primus naveo su na mestu, stoga prilažem ispravku svog razmišljanja, koja će, nadam se, otkloniti sve dileme koje su prethodni postovi stvorili i zbog kojih se izvinjavam.



Nakon razmišljanja, istraživanja i konsultacija koje sam sproveo iznosim sledeći zaključak:

izraz [inlmath]x^2+x+p[/inlmath], gde ćemo se držati početnog uslova da je [inlmath]x\in\mathbb{N}[/inlmath], jeste prost broj za svako [inlmath]x<p-1[/inlmath] ako i samo ako je diskriminanta [inlmath]1-4p[/inlmath] jednaka negativnoj vrednosti Hegnerovog broja, gde su Hegnerovi brojevi [inlmath]k\in\{1,2,3,7,11,19,43,67,163\}[/inlmath].

Jedina primedba je da kako mora da važi [inlmath]4p-1=k[/inlmath], brojevi [inlmath]1,2,3[/inlmath] ne ispunjavaju polaznu tvrdnju, te su jedine vrednosti [inlmath]k[/inlmath] koje su primenljive na prethodno tvrđenje [inlmath]k\in\{7,11,19,43,67,163\}[/inlmath] kojima su odgovarajuće vrednosti [inlmath]p=\frac{k+1}{4}\in\{2,3,5,11,17,41\}[/inlmath] (ovo su tzv. Ojlerovi srećni brojevi), što, dakle, daje odgovor i na pitanje vezano za izraz [inlmath]x^2+x+41[/inlmath], gde je [inlmath]p=41[/inlmath], a diskriminanta [inlmath]1-4\cdot41=-163[/inlmath], gde je [inlmath]163[/inlmath] jedan od Hegnerovih brojeva. Ovo tvrđenje dokazao je Rabinovic [inlmath]1913[/inlmath], a njegov dokaz meni je usled složenosti matematičkog aparata koji je koristio nedokučiv.



primus je napisao:Potreban i dovoljan uslov da bi [inlmath]x^2+x+p[/inlmath] bio prost broj jeste da nije deljiv ni sa jednim prostim brojem manjim ili jednakim od [inlmath]\sqrt{x^2+x+p}[/inlmath].

Ja bih rekao sledeće: vrednosti izraza [inlmath]x^2+x+p[/inlmath] za [inlmath]x<p-1[/inlmath] manje su od [inlmath](p-1)^2+p-1+p=p^2[/inlmath]. Da bi [inlmath]x^2+x+p[/inlmath] pod tim uslovima bio prost broj, ne sme biti deljiv sa prostim brojem manjim od [inlmath]\sqrt{p^2}=p[/inlmath]. Moja tvrdnja omogućava da [inlmath]x^2+x+p[/inlmath] može biti deljivo [inlmath]p[/inlmath] i to kada je [inlmath]x=0[/inlmath] (mada mi tu vrednost [inlmath]x[/inlmath] nismo posmatrali u skupu prirodnih brojeva, tako da je ovo samo napomena).

Nadam se da ovoga puta sve rečeno zaista i stoji, ali ukoliko ne stoji, unapred prihvatam sve primebde :)
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 136
Zahvalio se: 45 puta
Pohvaljen: 157 puta


Povratak na TEORIJA BROJEVA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 3 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Petak, 13. Decembar 2019, 12:24 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs