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

Djeljivost prirodnih brojeva

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

Djeljivost prirodnih brojeva

Postod Gamma » Nedelja, 03. Maj 2015, 00:21

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.
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+
  • +1

Re: Djeljivost prirodnih brojeva

Postod desideri » Nedelja, 03. Maj 2015, 12:49

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].
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1542
Lokacija: Beograd
Zahvalio se: 1097 puta
Pohvaljen: 864 puta

Re: Djeljivost prirodnih brojeva

Postod Gamma » Nedelja, 03. Maj 2015, 18:35

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

Re: Djeljivost prirodnih brojeva

Postod desideri » Nedelja, 03. Maj 2015, 18:53

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:
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1542
Lokacija: Beograd
Zahvalio se: 1097 puta
Pohvaljen: 864 puta

Re: Djeljivost prirodnih brojeva

Postod Gamma » Nedelja, 03. Maj 2015, 19:02

Mislio sam da ga prebacimo iz komšiluka u našu kuću :) Ako ima koristi od njega.
Gamma  OFFLINE
 
Postovi: 1009
Zahvalio se: 183 puta
Pohvaljen: 239 puta

Re: Djeljivost prirodnih brojeva

Postod desideri » Nedelja, 03. Maj 2015, 19:43

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
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1542
Lokacija: Beograd
Zahvalio se: 1097 puta
Pohvaljen: 864 puta

Re: Djeljivost prirodnih brojeva

Postod Daniel » Ponedeljak, 04. Maj 2015, 00:19

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.
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

Re: Djeljivost prirodnih brojeva

Postod Gamma » Ponedeljak, 04. Maj 2015, 08:14

Daniele, svaka čast za trud. :thumbup:
Gamma  OFFLINE
 
Postovi: 1009
Zahvalio se: 183 puta
Pohvaljen: 239 puta

Re: Djeljivost prirodnih brojeva

Postod desideri » Ponedeljak, 04. Maj 2015, 08:59

Svaka čast i od mene :thumbup:
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1542
Lokacija: Beograd
Zahvalio se: 1097 puta
Pohvaljen: 864 puta

Re: Djeljivost prirodnih brojeva

Postod Corba248 » Subota, 18. Mart 2017, 00:40

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. ;) :)
Zaslužni forumaš
 
Postovi: 314
Zahvalio se: 37 puta
Pohvaljen: 352 puta

Sledeća

Povratak na TEORIJA BROJEVA

Ko je OnLine

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

cron

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