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

Najveći delitelj brojeva

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

Najveći delitelj brojeva

Postod Uroš » Četvrtak, 31. Decembar 2015, 13:11

Pozdrav svima. Potrebno mi je razjanšnjenje rešenja jednog zadatka (ili, pak, druga ideja):

Naći najveći prirodan broj [inlmath]d[/inlmath] koji je delitelj svakog broja oblika [inlmath]n(n+1)(2n+1996)[/inlmath] za svako [inlmath]n\in\mathbb{N}[/inlmath].

Rešenje:

Neka je [inlmath]f(n)=n(n+1)(2n+1996),\;f(1)=2\cdot1998=2^2\cdot3^3\cdot37[/inlmath]. Dakle [inlmath]d=2^x\cdot3^y\cdot37^z[/inlmath] i [inlmath]x\le2,\;y\le3,\;z\le1[/inlmath]. [inlmath]f(2)=12000=2^7\cdot3\cdot5^3[/inlmath], pa je [inlmath]d[/inlmath] deljiv samo prostim brojevima [inlmath]2[/inlmath] i [inlmath]3[/inlmath] tj. [inlmath]d=2^\alpha\cdot3^\beta[/inlmath] i [inlmath]\alpha\le2[/inlmath], [inlmath]\beta\le1[/inlmath]. Lako se dokazuje da je [inlmath]f(n)[/inlmath] deljivo sa [inlmath]4[/inlmath] i [inlmath]3[/inlmath] pa je [inlmath]d=12[/inlmath].

Kako je iz [inlmath]f(1)=2\cdot1998=2^2\cdot3^3\cdot37[/inlmath] zaključeno da je [inlmath]x\le2,\;y\le3,\;z\le1[/inlmath]?
Zašto iz [inlmath]f(2)=12000=2^7\cdot3\cdot5^3[/inlmath] sledi da je [inlmath]d[/inlmath] deljiv samo prostim brojevima [inlmath]2[/inlmath] i [inlmath]3[/inlmath]?
Da li bi se deljivost [inlmath]f(n)[/inlmath] brojevima [inlmath]4[/inlmath] i [inlmath]3[/inlmath] izvela matematičkom indukcijom, ili postoji neki drugi put?

Ako su neka od pitanja suvišna, izvinite, ali elementarna teorija brojeva se nije ni dotakla u školi, pa sa njom imam dosta problema.
Poslednji put menjao Daniel dana Petak, 01. Januar 2016, 19:10, izmenjena samo jedanput
Razlog: Korekcija naziva teme – „Petocifren prirodan broj“ izmenjeno u „Najveći delitelj brojeva“
Uroš  OFFLINE
 
Postovi: 36
Zahvalio se: 39 puta
Pohvaljen: 13 puta

Sharuj ovu temu na:

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

Re: Najveći delitelj brojeva

Postod Daniel » Petak, 01. Januar 2016, 18:47

Uroš je napisao:Kako je iz [inlmath]f(1)=2\cdot1998=2^2\cdot3^3\cdot37[/inlmath] zaključeno da je [inlmath]x\le2,\;y\le3,\;z\le1[/inlmath]?

Uslov je da je [inlmath]d[/inlmath] delitelj svakog broja oblika [inlmath]n\left(n+1\right)\left(2n+1996\right)[/inlmath]. To znači da, i kad uvrstimo [inlmath]n=1[/inlmath], tada [inlmath]d[/inlmath] takođe mora biti delitelj tog broja.
Kako je i napisano, za [inlmath]n=1[/inlmath] dati izraz postaje [inlmath]2^2\cdot3^3\cdot37[/inlmath]. Potrebno je, dakle, da [inlmath]d[/inlmath] bude delitelj tog broja, tj. da broj [inlmath]2^2\cdot3^3\cdot37[/inlmath] mora biti deljiv sa [inlmath]d[/inlmath]. To, opet, znači da [inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{d}[/inlmath] mora biti prirodan broj. To će biti slučaj onda kada su svi činioci broja [inlmath]d[/inlmath] sadržani u brojiocu ovog razlomka, pa će s njima moći da se skrate, pri čemu u imenicu ostaje samo jedinica, tj. vrednost razlomka je tada prirodan broj. (Kontraprimer: ako je jedan od činilaca broja [inlmath]d[/inlmath] npr. [inlmath]5[/inlmath], tada ta petica neće moći nikako da se skrati ni sa jednim od prostih brojeva iz brojioca, tako da u imeniocu u svakom slučaju ostaje vrednost različita od jedinice, što znači da vrednost razlomka neće biti prirodan broj, tj. [inlmath]d[/inlmath] tada nije delitelj vrednosti u brojiocu.)
Takođe, stepeni činilaca broja [inlmath]d[/inlmath] ne smeju biti veći od stepena odgovarajućih činilaca u brojiocu. Ako [inlmath]d[/inlmath] u sebi sadrži [inlmath]3^2[/inlmath], tada se to bez problema skrati sa [inlmath]3^3[/inlmath] u brojiocu, pri čemu u brojiocu ostaje [inlmath]3[/inlmath]. Takođe, ako [inlmath]d[/inlmath] u sebi sadrži [inlmath]3^3[/inlmath], tada se i to bez problema skrati sa [inlmath]3^3[/inlmath] u brojiocu. Međutim, ukoliko [inlmath]d[/inlmath] u sebi sadrži [inlmath]3^4[/inlmath], tada se u brojiocu i imeniocu krati [inlmath]3^3[/inlmath], nakon čega u imeniocu ostaje [inlmath]3[/inlmath], koje više nema s čime u brojiocu da se krati, pa kao vrednost razlomka ne dobijamo prirodan broj.

Zbog toga, da bi vrednost razlomka [inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{d}[/inlmath] bila prirodan broj (i time [inlmath]d[/inlmath] bio delitelj broja [inlmath]2^2\cdot3^3\cdot37[/inlmath]), broj [inlmath]d[/inlmath] mora biti oblika [inlmath]2^x3^y37^z,\;x\le2,\;y\le3,\;z\le1,\;x,y,z\in\mathbb{N}_0[/inlmath].

Primeri:
[inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{2^2\cdot3}[/inlmath] će biti prirodan broj.
[inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{2\cdot3^3\cdot37}[/inlmath] će biti prirodan broj.
[inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{2}[/inlmath] će biti prirodan broj.
[inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{1}[/inlmath] će biti prirodan broj.
[inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{2^3\cdot3^2\cdot37}[/inlmath] neće biti prirodan broj.
[inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{37^2}[/inlmath] neće biti prirodan broj.
[inlmath]\displaystyle\frac{2^2\cdot3^3\cdot37}{2^2\cdot5}[/inlmath] neće biti prirodan broj.
itd...

Uroš je napisao:Zašto iz [inlmath]f(2)=12000=2^{\color{red}7}\cdot3\cdot5^3[/inlmath] sledi da je [inlmath]d[/inlmath] deljiv samo prostim brojevima [inlmath]2[/inlmath] i [inlmath]3[/inlmath]?

Prvo, tu ima greška (obeležih je crveno), treba [inlmath]12000=2^5\cdot3\cdot5^3[/inlmath].
Oni su tu odmah objedinili uslove deljivosti i [inlmath]f\left(1\right)[/inlmath] i [inlmath]f\left(2\right)[/inlmath] brojem [inlmath]d[/inlmath]. Ako bismo išli postupno – samo iz uslova da je broj [inlmath]f\left(2\right)=2^5\cdot3\cdot5^3[/inlmath] deljiv brojem [inlmath]d[/inlmath] sledi da je [inlmath]d[/inlmath] oblika [inlmath]2^x3^y5^t,\;x\le5,\;y\le1,\;t\le3,\;x,y,t\in\mathbb{N}_0[/inlmath]. (Objašnjenje je isto kao i u slučaju za [inlmath]f\left(1\right)[/inlmath] samo obrati pažnju na oznake – [inlmath]x[/inlmath] je u oba slučaja korišćeno kao stepen broja [inlmath]2[/inlmath], [inlmath]y[/inlmath] kao stepen broja [inlmath]3[/inlmath], dok sam ovde kao stepen broja [inlmath]5[/inlmath] koristio oznaku [inlmath]t[/inlmath] kako bi se razlikovala od stepena broja [inlmath]37[/inlmath] koji je bio označen sa [inlmath]z[/inlmath].)

I sad tražimo presek ova dva uslova, pošto je potrebno da [inlmath]d[/inlmath] bude delitelj i [inlmath]f\left(1\right)[/inlmath] i [inlmath]f\left(2\right)[/inlmath]:
[dispmath]x\le2\;\land\;x\le5\;\Rightarrow\;x\le2\\
y\le3\;\land\;y\le1\;\Rightarrow\;y\le1[/dispmath]
[inlmath]37[/inlmath] i [inlmath]5[/inlmath] se ne pojavljuju kao činioci u oba slučaja (već samo u jednom od njih), tako da njih eliminišemo.
Time smo zasad zaključili da [inlmath]d[/inlmath] može najviše imati činioce [inlmath]2^2[/inlmath] i [inlmath]3[/inlmath], tj. da bi [inlmath]d[/inlmath] najviše moglo biti [inlmath]12[/inlmath]. To je već dovoljno „sužen obruč“ da bi se nakon toga jednostavno, pomoću matematičke indukcije, moglo dokazati da je [inlmath]12[/inlmath] delitelj (a time i najveći delitelj) bilo kog broja [inlmath]f\left(n\right),\;n\in\mathbb{N}[/inlmath].

Uroš je napisao:Ako su neka od pitanja suvišna, izvinite, ali elementarna teorija brojeva se nije ni dotakla u školi, pa sa njom imam dosta problema.

Nisu pitanja suvišna, sasvim su na mestu. :)
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: 7942
Lokacija: Beograd
Zahvalio se: 4144 puta
Pohvaljen: 4223 puta

Re: Najveći delitelj brojeva

Postod Uroš » Subota, 02. Januar 2016, 12:09

@Daniel Hvala ti, sada je sasvim jasno. Pošto za [inlmath]f(1)[/inlmath] mora nešto da važi, onda mora da važi i za [inlmath]f(2)[/inlmath], [inlmath]f(3)[/inlmath], ... Kako su u pitanju prirodni brojevi, to je [inlmath]f(1)[/inlmath] "prva" vrednost funkcije koja može da se izračuna, a ujedno i najmanja vrednost funkcije. Odatle je jasno da će da važi i kada se u zagradu ubaci svaki prirodan broj veći od [inlmath]1[/inlmath], a ovi preseci uslova posle su sasvim jasni.
Uroš  OFFLINE
 
Postovi: 36
Zahvalio se: 39 puta
Pohvaljen: 13 puta

Re: Najveći delitelj brojeva

Postod Daniel » Subota, 02. Januar 2016, 12:19

Uf, ovo sad ništa nisam razumeo... :) O čemu govoriš, o matematičkoj indukciji, ili...?
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: 7942
Lokacija: Beograd
Zahvalio se: 4144 puta
Pohvaljen: 4223 puta

Re: Najveći delitelj brojeva

Postod Uroš » Nedelja, 03. Januar 2016, 22:37

Da, da, da, na indukciju sam mislio. Ima trenutaka kad sebi nešto razjasnim u mozgu i bude sasvim jasno, a za druge uopšte nema smisla. Bezveze sam to i pisao. :)
Uroš  OFFLINE
 
Postovi: 36
Zahvalio se: 39 puta
Pohvaljen: 13 puta

Re: Najveći delitelj brojeva

Postod Daniel » Ponedeljak, 04. Januar 2016, 12:50

Uroš je napisao:Kako su u pitanju prirodni brojevi, to je [inlmath]f(1)[/inlmath] "prva" vrednost funkcije koja može da se izračuna, a ujedno i najmanja vrednost funkcije.

U opštem sllučaju [inlmath]f\left(1\right)[/inlmath] ne mora biti najmanja vrednost funkcije.
U ovom konkretnom slučaju, funkcija je monotono rastuća, pa [inlmath]f\left(1\right)[/inlmath] zaista jeste najmanja vrednost funkcije, ali to i nije ovde od neke važnosti – od važnosti je deljivost sa [inlmath]12[/inlmath], što je potrebno proveriti (dokazati) indukcijom.

Uroš je napisao:Odatle je jasno da će da važi i kada se u zagradu ubaci svaki prirodan broj veći od [inlmath]1[/inlmath]

Ne, nije iz [inlmath]f\left(1\right)[/inlmath] jasno, već mora da se pokaže da, ako je [inlmath]n[/inlmath]-ti član deljiv sa [inlmath]12[/inlmath], tada će i [inlmath]\left(n+1\right)[/inlmath]. član biti deljiv sa [inlmath]12[/inlmath]. Na taj način zaključujemo da, pošto deljivost važi za prvi član važiće i za drugi, pa pošto važi za drugi važiće i za treći, pošto važi za treći važiće i za četvrti itd... I, domino-efektom, zaključujemo da važi za sve članove. To je princip matematičke indukcije.

Dakle, baza indukcije ([inlmath]n=1[/inlmath]) ovde je već odrađena, jer smo konstatovali da [inlmath]f\left(1\right)[/inlmath] (pa čak i [inlmath]f\left(2\right)[/inlmath]) jeste deljivo sa [inlmath]12[/inlmath].
Sad sledi indukcijska pretpostavka, da je [inlmath]f\left(n\right)[/inlmath] deljivo sa [inlmath]12[/inlmath], a zatim treba pokazati da, kad važi ta pretpostavka, tada važi i da je [inlmath]f\left(n+1\right)[/inlmath] deljivo sa [inlmath]12[/inlmath] (indukcijski korak). Bi li umeo to da uradiš i treba li ti pomoć?
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: 7942
Lokacija: Beograd
Zahvalio se: 4144 puta
Pohvaljen: 4223 puta

Re: Najveći delitelj brojeva

Postod Uroš » Utorak, 05. Januar 2016, 00:34

@Daniel
Moraću malo sporije da pišem, zaista. Ne treba pomoć za indukciju, snađoh se. Hvala ti. :)
Uroš  OFFLINE
 
Postovi: 36
Zahvalio se: 39 puta
Pohvaljen: 13 puta

Re: Najveći delitelj brojeva

Postod Onomatopeja » Utorak, 12. Januar 2016, 22:08

Samo bih napomenuo da ovde datu deljivost mozemo pokazati i „na ruke“. Naime, da bi broj bio deljiv sa [inlmath]12[/inlmath] dovoljno je (a i potrebno, jer je [inlmath]\text{NZS}\hspace{0.3mm}(3,4)=1[/inlmath]) da je on deljiv sa [inlmath]3[/inlmath] i [inlmath]4[/inlmath]. Da je broj [inlmath]n(n+1)(2n+1996)[/inlmath] deljiv sa [inlmath]3[/inlmath] vidimo na sledeci nacin: ako je [inlmath]n[/inlmath] deljivo sa [inlmath]3[/inlmath] stvar je gotova; ako je [inlmath]n+1[/inlmath] deljivo sa [inlmath]3[/inlmath], isto je gotovo; ako nije ni jedna od te dve situacije, onda [inlmath]n+2[/inlmath] mora biti deljivo sa [inlmath]3[/inlmath] (jer su brojevi [inlmath]n[/inlmath], [inlmath]n+1[/inlmath] i [inlmath]n+2[/inlmath] uzastopni, te jedan mora biti deljiv sa [inlmath]3[/inlmath]). Tada je [inlmath]n+2 = 3k[/inlmath] za neko [inlmath]k \in \mathbb{N}[/inlmath], odnosno [dispmath]n(n+1)(2n+1996)=n(n+1)(2(n+2)+1992) = n(n+1)(6k + 3 \cdot 664) = 3n(n+1)(2k+664),[/dispmath] pa je jasna deljivost ovog broja sa [inlmath]3[/inlmath]. Proverimo sada da je nas broj deljiv i sa [inlmath]4[/inlmath]. Jasno, kako je [inlmath]2n+1996=2(n+998)[/inlmath] onda je dovoljno da je [inlmath]n(n+1)[/inlmath] deljivo sa [inlmath]2[/inlmath], sto je isto jasno (jer je ili [inlmath]n[/inlmath] ili [inlmath]n+1[/inlmath] parno (dva uzastopna broja)). Dakle, nas broj [inlmath]n(n+1)(2n+1996)[/inlmath] je deljiv i sa [inlmath]3[/inlmath] i sa [inlmath]4[/inlmath], a samim tim i sa [inlmath]12[/inlmath].
 
Postovi: 599
Zahvalio se: 15 puta
Pohvaljen: 569 puta


Povratak na TEORIJA BROJEVA

Ko je OnLine

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

cron

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