Djeljivost prirodnih brojeva

PostPoslato: Nedelja, 03. Maj 2015, 00:21
od Gamma
Mislim da niko još nije otvarao ovakvu temu. Što se tiče djeljivosti prirodnih brojeva sa [inlmath]1,2,3,4,5,6,8,9,10[/inlmath], večina toga je očigledna. Mislim nema se tu šta puno ni dokazivati. Jeste da kod djeljivosti sa [inlmath]3[/inlmath] i [inlmath]9[/inlmath] dokaz se svodi u tri reda. Ali uglavnom jednostavno je. Uvijek mi je predstavljala problem djeljivost sa brojem [inlmath]7[/inlmath].
Pravilo glasi: broj je djeljiv sa sedam ako od broja kojeme odbijemo tu zadnju cifru jedinica oduzmemo dvostruku cifru jedinica važi da je djeljiv sa sedam (neka moja verzija definicije ali skontaćete je :ghh: ) Morao sam improvizovati jer je nisam mogao naći na našem jeziku.
Problem je kako ovo dokazati. Ima na interentu tona tih dokaza ali sve je to nešto nepotpuno i nerazjašnjeno do kraja.

Re: Djeljivost prirodnih brojeva

PostPoslato: Nedelja, 03. Maj 2015, 12:49
od desideri
Ja mislim da sam ovo pravilo razumeo, ovo što je @Gamma napisao. Bilo kako bilo, [inlmath]7[/inlmath] je stvarno najnezgodniji po pitanju deljivosti, i tu je @Gamma u pravu.
@ubavic je sigurno najkompetentniji da odgovori na ovo tvoje pitanje, ali čovek trenutno nije tu.

Evo ja sam čuo i za ovo pravilo (no treba proveriti, uzmite s rezervom):
Ako su cifre jedinica, desetica, stotina itd. nekog broja u dekadnom sistemu: [inlmath]a_0,a_1,a_2,\ldots[/inlmath] tada je taj broj deljiv brojem [inlmath]7[/inlmath] ako je zbir:
[dispmath]a_0\cdot3^0+a_1\cdot3^1+a_2\cdot3^2+\cdots[/dispmath]
deljiv brojem [inlmath]7[/inlmath].
Ova formula se lako pamti (zato sam je i zapamtio :D ) samo još da je tačna :think1:
Ja mislim da bi u eventualnom postupku dokazivanja trebalo uzeti u obzir to da je ostatak pri deljenju broja [inlmath]10[/inlmath] brojem [inlmath]7[/inlmath] zapravo broj [inlmath]3[/inlmath]. Ali što da dokazujemo nešto za šta nismo zapravo ni sigurni da je tačno?

Ja sam danas pokušavao da nađem kontraprimer za ovo, ali nisam uspeo. Ako iko uspe da nađe kontraprimer, biće to @Daniel :thumbup:
A primera da je formula ok, koliko god hoćete. Evo jednog. Broj [inlmath]2107[/inlmath] ima četiri cifre, pa bi ona formula glasila:
[dispmath]7\cdot3^0+0\cdot3^1+1\cdot3^2+2\cdot3^3=70[/dispmath]
A [inlmath]70[/inlmath] je deljivo sa [inlmath]7[/inlmath] pa samim tim i [inlmath]2107[/inlmath].

Re: Djeljivost prirodnih brojeva

PostPoslato: Nedelja, 03. Maj 2015, 18:35
od Gamma
Ja nisam znao za to pravilo koje si ti iznio. Ali pričekaćemo za još koji post. Znači nemam blage veze na šta se svodi dokaz sa ovu djeljivost. Djeluje mi veoma kompleksno. Sve sam na netu prešao par puta, jedino sam pronašao ovo gdje ima priče o dokazivanju. Mada to ne razumijem.

Re: Djeljivost prirodnih brojeva

PostPoslato: Nedelja, 03. Maj 2015, 18:53
od desideri
Ovo sam letimično pogledao. Ali zar nije bolje, @Gamma, da matematičke probleme rešavamo kod svoje kuće, nego da idemo u komšiluk, makar to bili ne- znam- kakvi sajtovi :)
A za ovo što ja rekoh, 99% sam siguran da je ok. :thumbup:

Re: Djeljivost prirodnih brojeva

PostPoslato: Nedelja, 03. Maj 2015, 19:02
od Gamma
Mislio sam da ga prebacimo iz komšiluka u našu kuću :) Ako ima koristi od njega.

Re: Djeljivost prirodnih brojeva

PostPoslato: Nedelja, 03. Maj 2015, 19:43
od desideri
Pa kako da ih prebacujemo kod nas kada su slabiji od nas? Evo ja nastavljam da proveravam, nemam još dokaz, ali sam 99,99% ubeđen da je ona formula za deljivost (koju sam naveo) brojem [inlmath]7[/inlmath] tačna :D

Re: Djeljivost prirodnih brojeva

PostPoslato: Ponedeljak, 04. Maj 2015, 00:19
od Daniel
Slobodno možeš dodati i taj 0,01% – formula jeste tačna, :) a sa'ću to i dokazati.

Znači, imamo [inlmath]n[/inlmath]-tocifren broj oblika [inlmath]\overline{a_{n-1}\cdots a_2a_1a_0}[/inlmath], gde [inlmath]a_i[/inlmath] predstavljaju njegove dekadne cifre (cifra [inlmath]a_0[/inlmath] je cifra jedinica, cifra [inlmath]a_1[/inlmath] cifra desetica itd.)
Vrednost tog broja iznosi, naravno,
[dispmath]10^{n-1}a_{n-1}+\cdots+10^2a_2+10^1a_1+10^0a_0[/dispmath]
Treba, dakle, dokazati tvrđenje da, ako je [inlmath]3^{n-1}a_{n-1}+\cdots+3^2a_2+3^1a_1+3^0a_0[/inlmath] deljivo sa [inlmath]7[/inlmath], tada je i vrednost samog posmatranog broja, [inlmath]10^{n-1}a_{n-1}+\cdots+10^2a_2+10^1a_1+10^0a_0[/inlmath], deljiva sa [inlmath]7[/inlmath].

Deljivost izraza [inlmath]3^{n-1}a_{n-1}+\cdots+3^2a_2+3^1a_1+3^0a_0[/inlmath] brojem [inlmath]7[/inlmath] pišemo na sledeći način:
[dispmath]3^{n-1}a_{n-1}+\cdots+3^2a_2+3^1a_1+3^0a_0=7k\quad\left(k\in\mathbb{Z}\right)[/dispmath]
Vrednost posmatranog broja, [inlmath]10^{n-1}a_{n-1}+\cdots+10^2a_2+10^1a_1+10^0a_0[/inlmath], možemo napisati kao
[dispmath]\left(3+7\right)^{n-1}a_{n-1}+\cdots+\left(3+7\right)^2a_2+\left(3+7\right)^1a_1+\left(3+7\right)^0a_0[/dispmath]
pri čemu svaki od izraza [inlmath]\left(3+7\right)^i[/inlmath] možemo napisati kao
[dispmath]\left(3+7\right)^i=\sum_{j=0}^i{i\choose j}3^{i-j}7^j={i\choose0}3^i+{i\choose1}3^{i-1}7^1+{i\choose2}3^{i-2}7^2+\cdots+{i\choose i}7^i=\\
={i\choose0}3^i+7\underbrace{\left[{i\choose1}3^{i-1}+{i\choose2}3^{i-2}7^1+\cdots+{i\choose i}7^{i-1}\right]}_{k_i}=3^i+7k_i\quad\left(k_i\in\mathbb{Z}\right)[/dispmath]
Prema tome, vrednost posmatranog broja biće
[dispmath]\left(3^{n-1}+7k_{n-1}\right)a_{n-1}+\cdots+\left(3^2+7k_2\right)a_2+\left(3^1+7k_1\right)a_1+\left(3^0+7k_0\right)a_0=\\
=\underbrace{3^{n-1}a_{n-1}+\cdots+3^2a_2+3^1a_1+3^0a_0}_{7k}+7k_{n-1}a_{n-1}+\cdots+7k_2a_2+7k_1a_1+7k_0a_0=\\
=7k+7k_{n-1}a_{n-1}+\cdots+7k_2a_2+7k_1a_1+7k_0a_0=\\
=7\underbrace{\left(k+k_{n-1}a_{n-1}+\cdots+k_2a_2+k_1a_1+k_0a_0\right)}_{\mbox{ceo broj}}[/dispmath]
čime je dokazano da iz deljivosti izraza [inlmath]3^{n-1}a_{n-1}+\cdots+3^2a_2+3^1a_1+3^0a_0[/inlmath] brojem [inlmath]7[/inlmath] sledi i deljivost izraza [inlmath]10^{n-1}a_{n-1}+\cdots+10^2a_2+10^1a_1+10^0a_0[/inlmath] brojem [inlmath]7[/inlmath].



A što se tiče Gamminog pitanja, treba dokazati da je broj predstavljen ciframa [inlmath]\overline{a_{n-1}\cdots a_2a_1a_0}[/inlmath] deljiv sa [inlmath]7[/inlmath] ako je broj [inlmath]\overline{a_{n-1}\cdots a_2a_1}[/inlmath] (bez cifre jedinica) umanjen za [inlmath]2a_0[/inlmath] deljiv sa [inlmath]7[/inlmath]. Tako dobijeni broj može se predstaviti kao
[dispmath]10^{n-2}a_{n-1}+\cdots+10^1a_2+10^0a_1-2a_0=7k\quad\left(k\in\mathbb{Z}\right)[/dispmath]
Vrednost posmatranog broja [inlmath]\overline{a_{n-1}\cdots a_2a_1a_0}[/inlmath] biće
[dispmath]10^{n-1}a_{n-1}+\cdots+10^2a_2+10^1a_1+10^0a_0=\\
=10\left(10^{n-2}a_{n-1}+\cdots+10^1a_2+10^0a_1\right)+a_0=\\
=10\left(10^{n-2}a_{n-1}+\cdots+10^1a_2+10^0a_1-2a_0+2a_0\right)+a_0=\\
=10\underbrace{\left(10^{n-2}a_{n-1}+\cdots+10^1a_2+10^0a_1-2a_0\right)}_{7k}+20a_0+a_0=\\
=10\cdot7k+21a_0=7\cdot10k+7\cdot3a_0=7\underbrace{\left(10k+3a_0\right)}_{\mbox{ceo broj}}\\[/dispmath]
što je i trebalo dokazati.

Re: Djeljivost prirodnih brojeva

PostPoslato: Ponedeljak, 04. Maj 2015, 08:14
od Gamma
Daniele, svaka čast za trud. :thumbup:

Re: Djeljivost prirodnih brojeva

PostPoslato: Ponedeljak, 04. Maj 2015, 08:59
od desideri
Svaka čast i od mene :thumbup:

Re: Djeljivost prirodnih brojeva

PostPoslato: Subota, 18. Mart 2017, 00:40
od Corba248
Evo da i ja doprinesem ovoj zaista zanimljivoj temi. :)
Pošto ste već obradili deljivost sa prvih [inlmath]10[/inlmath] prirodnih brojeva, ja ću početi od [inlmath]11[/inlmath], meni najinteresantnijeg kriterijuma deljivosti:
Dakle, broj [inlmath]n=\overline{a_ka_{k-1}\cdots a_2a_1}[/inlmath] je deljiv sa [inlmath]11[/inlmath] akko je broj:
[dispmath]m=a_1-a_2+a_3-a_4+\cdots[/dispmath] deljiv sa [inlmath]11[/inlmath]. Drugim rečima ako sa [inlmath]N[/inlmath] označimo zbir cifara na neparnim pozicijama, a sa [inlmath]P[/inlmath] zbir cifara na parnim pozicijama nekog broja, taj broj je deljiv sa [inlmath]11[/inlmath] akko je:
[dispmath]N-P\equiv0\pmod{11}[/dispmath] ili
[dispmath]11\mid N-P[/dispmath] (koji vam je draži zapis).



Pređimo na deljivost brojem [inlmath]13[/inlmath]. Broj [inlmath]n=\overline{a_ka_{k-1}\cdots a_2a_1}[/inlmath] je deljiv sa [inlmath]13[/inlmath] akko je broj:
[dispmath]m=\overline{a_3a_2a_1}-\overline{a_6a_5a_4}+\overline{a_9a_8a_7}-\cdots[/dispmath] deljiv sa [inlmath]13[/inlmath]. Isto ovo važi i za deljivost sa [inlmath]7[/inlmath].



Dalje idemo na deljivost sa [inlmath]27[/inlmath]. Broj [inlmath]n=\overline{a_ka_{k-1}\cdots a_2a_1}[/inlmath] je deljiv sa [inlmath]27[/inlmath] akko je i broj:
[dispmath]m=\overline{a_3a_2a_1}+\overline{a_6a_5a_4}+\overline{a_9a_8a_7}+\cdots[/dispmath] deljiv sa [inlmath]27[/inlmath]. Isto važi i za [inlmath]37[/inlmath].



Za deljivost sa [inlmath]10^n,\;n\in\mathbb{N}[/inlmath] je jasno da je neki broj [inlmath]m[/inlmath] deljiv sa [inlmath]10^n[/inlmath] ako se završava sa barem [inlmath]n[/inlmath] nula.



Za deljivost sa [inlmath]25[/inlmath] važi da je neki broj [inlmath]n[/inlmath] deljiv sa [inlmath]25[/inlmath] ukoliko se završava ciframa [inlmath]00[/inlmath], [inlmath]25[/inlmath], [inlmath]50[/inlmath] ili [inlmath]75[/inlmath], prostije rečeno ukoliko mu je dvocifreni završetak deljiv sa [inlmath]25[/inlmath]. (Mala digresija: dvocifreni završeci se mogu pojaviti u zadacima iz teorije brojeva, recimo kako biste odredili dvocifreni završetak broja [inlmath]9^{9^9}[/inlmath] bez digitrona? (hint: ostaci pri deljenju sa [inlmath]100[/inlmath]) o dvocifrenom završetku broja nam govori njegov ostatak pri deljenju sa [inlmath]4[/inlmath], [inlmath]25[/inlmath]...)



U jednom zadatku sam naišao na zanimljiv način provere deljivosti sa [inlmath]19[/inlmath]. Zadatak glasi:
Perica tvrdi da je pronašao algoritam kojim može da utvrdi da li je neki prirodan [inlmath]n[/inlmath] broj deljiv sa [inlmath]19[/inlmath]. Evo njegovog algoritma:
1) Trenutnom broju odbacimo poslednju cifru;
2) Novodobijenom broju dodamo dvostruku vrednost odbačene cifre
3) Sa dobijenim brojem provodimo korake 1) i 2) sve do trenutka dobijanja broja koji je ne veći od [inlmath]19[/inlmath]
(npr. ako imamo [inlmath]n=24817[/inlmath] algoritmom dobijamo niz brojeva [inlmath]2481[/inlmath], [inlmath]2495[/inlmath], [inlmath]249[/inlmath], [inlmath]259[/inlmath], [inlmath]25[/inlmath], [inlmath]43[/inlmath], [inlmath]4[/inlmath], [inlmath]10[/inlmath]).
Perica tvrdi da [inlmath]19\vert n[/inlmath] akko je poslednji dobijeni broj jednak [inlmath]19[/inlmath]. Da li je Perica u pravu?
Odgovor je jeste, ali je rešenje, odnosno dokaz, obiman te ga neću pisati, ali eto jednog načina da utvrdimo da li je neki broj deljiv sa [inlmath]19[/inlmath]. Slični algoritmi se mogu napraviti i za deljivost sa [inlmath]10k\pm1[/inlmath]. Barem tako tvrde autori, ja nisam još uvek pokušavao.



Možda nema neke velike koristi od kriterijuma koje sam naveo u konkretnim zadacima, ali je, meni bar, interesantno kako se pronađe veza između, recimo zbira cifara, razlike cifara itd. nekog broja i njegove deljivosti nekim drugim brojem. :)
P.S. Gore pomenuste (Gamma i desideri) da je [inlmath]7[/inlmath] najproblematičniji po pitanju deljivosti, a mi ovde ,zasad, pokazasmo [inlmath]3[/inlmath] različita kriterijuma deljivosti njime. ;) :)

Re: Djeljivost prirodnih brojeva

PostPoslato: Subota, 20. Januar 2018, 21:39
od Dragoslav2909
Za proveru deljivosti postoji formula koja vazi za sve prirodne brojeve ali nije uvek prakticna za upotrebu