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

Zadaci sa takmičenja

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

Re: Zadaci sa takmičenja

Postod Daniel » Četvrtak, 16. Mart 2017, 00:07

@mala_mu, to je otprilike to, ali pošto mi se neki delovi postupka ne čine baš dovoljno jasnim i preciznim, dopustićeš mi, nadam se, da pokušam da ih upotpunim ili opišem svojim rečima. :)

mala_mu je napisao:Pošto je u zadatku dato da je [inlmath]n^2+2^n[/inlmath] prost za neki prirodan broj [inlmath]n>1[/inlmath], možemo prvo potražiti koje je to [inlmath]n[/inlmath].

Da ne bude zabune, to neće biti jedno takvo [inlmath]n[/inlmath], već će biti više vrednosti [inlmath]n[/inlmath] ali takvih da zadovoljavaju uslov, kao što je i rečeno u zadatku, da su deljivi sa [inlmath]3[/inlmath], ali ne i sa [inlmath]6[/inlmath].

mala_mu je napisao:Prvo ću pretpostaviti da je [inlmath]n[/inlmath] neparan broj.

Nije potrebno da pretpostavljamo. :) Lako se vidi da [inlmath]n[/inlmath] mora biti neparan broj. Kada bi [inlmath]n[/inlmath] bio paran broj, tada bi zadati izraz [inlmath]n^2+2^n[/inlmath] bio paran broj veći od dvojke, pa ne bi bio prost broj.

mala_mu je napisao:Tada [inlmath]n^2+2^n[/inlmath] mogu zapisati kao [inlmath]n^2-1+2^n+1=(n-1)(n+1)+(2+1)\left(1-2+2^2+\cdots+2^{n-1}\right)=(n-1)(n+1)+3m[/inlmath].
Neka je [inlmath]n>3[/inlmath], to znači da je [inlmath]n\neq3[/inlmath], a jedan od brojeva [inlmath]n-1[/inlmath], [inlmath]n[/inlmath], [inlmath]n+1[/inlmath] djeljiv je sa [inlmath]3[/inlmath] što će reći da je [inlmath]n^2+2^n[/inlmath] djeljiv sa [inlmath]3[/inlmath].

Ja bih to rekao ovako: Pošto smo dobili da je zadati izraz [inlmath]n^2+2^n[/inlmath] jednak izrazu [inlmath](n-1)(n+1)+3m[/inlmath], sledi da nijedan od faktora [inlmath](n-1)[/inlmath] ili [inlmath](n+1)[/inlmath] ne sme biti deljiv sa [inlmath]3[/inlmath], jer bi tada [inlmath](n-1)(n+1)+3m[/inlmath] bio deljiv sa [inlmath]3[/inlmath], pa bi i zadati izraz [inlmath]n^2+2^n[/inlmath] bio deljiv sa [inlmath]3[/inlmath] i bio bi veći od [inlmath]3[/inlmath], što znači da ne bi bio prost broj.
E sad, pošto nijedan od faktora [inlmath](n-1)[/inlmath] ili [inlmath](n+1)[/inlmath] nije deljiv sa [inlmath]3[/inlmath], a znamo da tačno jedan od brojeva [inlmath](n-1)[/inlmath], [inlmath]n[/inlmath] ili [inlmath](n+1)[/inlmath] mora biti deljiv sa [inlmath]3[/inlmath] (jer su to tri uzastopna prirodna broja), sledi da će [inlmath]n[/inlmath] biti taj koji je deljiv sa [inlmath]3[/inlmath].
Pošto smo već konstatovali da [inlmath]n[/inlmath] ne sme biti parno, sledi da [inlmath]n[/inlmath] ne sme biti deljivo sa [inlmath]6[/inlmath].
Time je dokazano ono što je traženo – da je [inlmath]n[/inlmath] deljivo sa [inlmath]3[/inlmath], a da nije deljivo sa [inlmath]6[/inlmath].



Neke od vrednosti [inlmath]n[/inlmath] koje zadovoljavaju uslov da je [inlmath]n^2+2^n[/inlmath] prost broj:
[inlmath]n=3:\quad n^2+2^n=17\\
n=9:\quad n^2+2^n=593\\
n=15:\quad n^2+2^n=32\:993\\
n=21:\quad n^2+2^n=2\:097\:593[/inlmath]
Međutim, za [inlmath]n=27[/inlmath], iako [inlmath]27[/inlmath] zadovoljava uslov da je deljiv sa [inlmath]3[/inlmath] i nije deljiv sa [inlmath]6[/inlmath], dobilo bi se [inlmath]n^2+2^n=134\:218\:457[/inlmath], što nije prost broj (deljiv je sa [inlmath]73[/inlmath], sa [inlmath]521[/inlmath] i sa [inlmath]3\:529[/inlmath]). To je primer koji pokazuje da implikacija (koju je trebalo dokazati) ne važi i u obrnutom smeru.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Zadaci sa takmičenja

Postod Corba248 » Četvrtak, 16. Mart 2017, 01:18

Rešenje koje je dala (pretpostavljam da nije dao :) ) mala_mu je ispravno, ali se rešenje 1. zadatka iz ove teme koje sam objavio može i ovde primeniti.
Prvo, kada ustanovimo da je [inlmath]n[/inlmath] neparno nema potrebe dalje ispitivati deljivost sa [inlmath]6[/inlmath]. Dakle, uzmimo slučaj kada [inlmath]n[/inlmath] nije deljivo sa [inlmath]3[/inlmath], tada je ono oblika [inlmath]n=6k+1[/inlmath] ili [inlmath]n=6k+5[/inlmath], isto kao i [inlmath]q[/inlmath] u rešenju 1. zadatka iz ove teme. Potom slično kao i u tom zadatku zaključimo da: kada je [inlmath]n=6k+1[/inlmath] ili [inlmath]n=6k+5[/inlmath] onda je [inlmath]n^2+2^n[/inlmath] deljivo sa [inlmath]3[/inlmath] i veće od [inlmath]3[/inlmath], te ne može biti prost broj te onda jedino ostaje mogućnost [inlmath]3\vert{n}[/inlmath]. Na kraju krajeva, ovakvo je i zvanično rešenje :) .
Za one koji vole ovu oblast, a vole i da se malo pomuče, ostavljam jedan zadatak, pa ko ga reši svaka mu čast :D :
Kojom cifrom se završava broj [inlmath]1+2+\cdots+n[/inlmath] ako se broj [inlmath]1^3+2^3+\cdots+n^3[/inlmath] završava cifrom [inlmath]1[/inlmath]?
Zaslužni forumaš
 
Postovi: 314
Zahvalio se: 37 puta
Pohvaljen: 352 puta

Re: Zadaci sa takmičenja

Postod Onomatopeja » Četvrtak, 16. Mart 2017, 09:19

Pa ako znamo da je [inlmath]1^3+2^3+\cdots+n^3=(1+2+\cdots+n)^2[/inlmath], kao i sa kojim ciframa se moze/ne moze zavrsavati broj [inlmath]1+2+\cdots+n[/inlmath], sto se da videti iz formule za ovaj zbir, zadatak ne bi trebalo da je problematican.
 
Postovi: 613
Zahvalio se: 15 puta
Pohvaljen: 588 puta

  • +1

Re: Zadaci sa takmičenja

Postod Corba248 » Četvrtak, 16. Mart 2017, 13:15

Tačno :thumbup: , ali da pojasnim malo ako nekome ne bude bilo jasno.
Kako je [inlmath]1^3+2^3+\cdots+n^3[/inlmath] kvadrat broja [inlmath]1+2+\cdots+n[/inlmath] i završava se cifrom [inlmath]1[/inlmath], znači da se broj [inlmath]1+2+\cdots+n[/inlmath] završava ili cifrom [inlmath]1[/inlmath] ili cifrom [inlmath]9[/inlmath]. Taj zbir je jednak:
[dispmath]\frac{n(n+1)}{2}[/dispmath] Da bi se polovina nekog broja završavala cifrom [inlmath]9[/inlmath] taj broj se mora završavati cifrom [inlmath]8[/inlmath], u našem slučaju [inlmath]n(n+1)[/inlmath] se završava cifrom [inlmath]8[/inlmath], što je nemoguće jer se proizvod dva uzastopna prirodna broja može završavati samo ciframa [inlmath]2[/inlmath], [inlmath]6[/inlmath] i [inlmath]0[/inlmath]. Dakle, poslednja cifra broja [inlmath]1+2+\cdots+n[/inlmath] se završava cifrom [inlmath]1[/inlmath] ako se [inlmath]1^3+2^3+\cdots+n^3[/inlmath] završava cifrom [inlmath]1[/inlmath].
Evo još jednog:
Naći sve prirodne brojeve [inlmath]n[/inlmath] za koje proizvod [inlmath]n(n+1)(n+2)(n+3)[/inlmath] sadrži tačno [inlmath]3[/inlmath] prosta delioca.
Zaslužni forumaš
 
Postovi: 314
Zahvalio se: 37 puta
Pohvaljen: 352 puta

  • +1

Re: Zadaci sa takmičenja

Postod Corba248 » Petak, 17. Mart 2017, 21:39

Prethodni zadatak koji sam postavio vezan za poslednju cifru broja [inlmath]1+2+\cdots+n[/inlmath] mogao se rešiti bez poznavanja identiteta [inlmath]1^3+2^3+\cdots+n^3=(1+2+\cdots+n)^2[/inlmath]. Do ovog rešenja bi došli, po mom skromnom mišljenju, samo najuporniji:
Označimo sa [inlmath]x_n=1^3+2^3+\cdots+n^3[/inlmath]. Ako ispišemo brojeve od [inlmath]x_1[/inlmath] do [inlmath]x_{22}[/inlmath] uočićemo da se poslednje cifre brojeva [inlmath]x_1[/inlmath] i [inlmath]x_{21}[/inlmath], odnosno [inlmath]x_2[/inlmath] i [inlmath]x_{22}[/inlmath] poklapaju. To nam nagoveštava da se poslednja cifra brojeva iz niza [inlmath]x_n[/inlmath] periodično ponavlja sa periodom [inlmath]20[/inlmath]. Dokažimo ovo. Želimo da dokažemo da je poslednja cifra broja [inlmath]x_n[/inlmath] ista kao i poslednja cifra broja [inlmath]x_{n+20}[/inlmath]. Među brojevima [inlmath]n+1,\;n+2,\;\ldots,\;n+20[/inlmath] postoje tačno po dva broja koja se završavaju jednom te istom cifrom (pošto je to [inlmath]20[/inlmath] uzastopnih prirodnih brojeva). Otuda je:
[dispmath]x_{n+20}=x_n+(n+1)^3+(n+2)^3+\cdots+(n+20)^3\equiv x_n+2\cdot\left(0+1^3+2^3+\cdots+9^3\right)\equiv x_n+2\cdot2025\equiv x_n\pmod{10}[/dispmath] Sada iz prvih [inlmath]20[/inlmath] vrednosti za [inlmath]x_n[/inlmath] uočimo sve one za koje je [inlmath]x_n\equiv1\pmod{10}[/inlmath]. To se dešava samo za [inlmath]n=1[/inlmath], [inlmath]n=6[/inlmath], [inlmath]n=13[/inlmath] i [inlmath]n=18[/inlmath]. Zbog dokazne periodičnosti ovo znači da [inlmath]x_n\equiv1\pmod{10}[/inlmath] važi akko [inlmath]n\equiv1\pmod{20},\quad n\equiv6\pmod{20},\quad n\equiv13\pmod{20}[/inlmath] ili [inlmath]n\equiv18\pmod{20}[/inlmath]. Ostaje samo da od navedena četiri slučaja odredimo poslednju cifru broja [inlmath]1+2+\cdots+n[/inlmath]. Pokažimo to na primeru kada je [inlmath]n=20k+1[/inlmath]. Onda imamo:
[dispmath]1+2+\cdots+n=\frac{n(n+1)}{2}=(20k+1)(10k+1)\equiv1\pmod{10}[/dispmath] te je poslednja cifra broja [inlmath]1+2+\cdots+n[/inlmath], u ovom slučaju jednaka [inlmath]1[/inlmath]. I u ostala tri slučaja se dobija odgovor [inlmath]1[/inlmath].
Ovo, naravno, nisam ja osmislio već samo preneo iz rešenja. I moja ideja je bila korišćenje već pomenutog identiteta. :)
Zaslužni forumaš
 
Postovi: 314
Zahvalio se: 37 puta
Pohvaljen: 352 puta

Prethodna

Povratak na TEORIJA BROJEVA

Ko je OnLine

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


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 16:44 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs