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

Dokazivanje djeljivosti

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

Dokazivanje djeljivosti

Postod elektricar » Nedelja, 22. Januar 2017, 14:57

* MOD EDIT * Zadatak izdvojen iz ove teme

Ako nije problem da mi pomognete oko ovog problema. Naime, treba dokazati da je broj [inlmath](n+1)(n+2)\cdots(n+n)[/inlmath] djeljiv sa [inlmath]2^n[/inlmath], a nije djeljiv sa [inlmath]2^{n+1}[/inlmath]. Rjesenje u knjizi nikako nisam mogao shvatiti. Pokusavao sam da ovaj izraz zapisem kao [inlmath]2n(2n-1)(2n-2)\cdots(n+1)[/inlmath] pa da onda izuzimam dvice ispred zagrada pa bih onda dobio [inlmath]2^{n/2}n(2n-1)(n-1)\cdots(n+1)[/inlmath] pa bih onda malo filozofirao te postavljao uslove za ako je [inlmath]n[/inlmath] paran broj onda bi prva dva clana bila djeljiva sa [inlmath]4[/inlmath] itd. medutim nisam tako uspio. Ako ko ima ideju
 
Postovi: 25
Zahvalio se: 17 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

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

Re: Dokazivanje djeljivosti

Postod mala_mu » Nedelja, 22. Januar 2017, 15:53

Ovo lako možemo riješiti indukcijom po [inlmath]n\in\mathbb{N}[/inlmath], većina zadataka se može dokazati preko indukcije.

Baza: Neka je [inlmath]n=1[/inlmath], tada [inlmath](1+1)=2[/inlmath], je djeljivo sa [inlmath]2^1[/inlmath], ali nije sa [inlmath]4=2^{1+1}[/inlmath].

Korak: Pretpostavimo da za neko [inlmath]n\ge1[/inlmath] broj [inlmath](n+1)\cdots(n+n)[/inlmath] jeste djeljiv sa [inlmath]2^n[/inlmath], a nije djeljiv sa [inlmath]2^{n+1}[/inlmath].

Trebamo dokazati da je broj [inlmath](n+1+1)\cdot(n+1+2)\cdots(n+1+n+1)[/inlmath] djeljiv sa [inlmath]2^{n+1}[/inlmath], a nije djeljiv sa [inlmath]2^{n+2}[/inlmath]!
[dispmath](n+2)\cdot(n+3)\cdots(2n+1)\cdot(2n+2)=\\
2\cdot(n+1)\cdot(n+2)\cdot(n+3)\cdots(2n+1)=\\
2(n+1)\cdot(n+2)\cdot(n+3)\cdots(n+n)\cdot(2n+1)[/dispmath] Gdje je [inlmath](n+1)\cdots(n+n)[/inlmath] po IP djeljivo sa [inlmath]2^n[/inlmath], pa možemo napisati [inlmath](n+1)\cdot(n+2)\cdots(n+n)=2^n\cdot k[/inlmath], [inlmath]k[/inlmath] je neparan, dalje imamo
[dispmath](n+1+1)\cdots(n+1+n+1)=2\cdot2^n\cdot k\cdot(2n+1)=2^{n+1}\cdot k\cdot(2n+1)[/dispmath] To znači da [inlmath]2^{n+1}[/inlmath] dijeli [inlmath](n+1+1)\cdots(n+1+n+1)[/inlmath]
Kako je [inlmath]k(2n+1)[/inlmath] neparan to [inlmath](n+1+1)\cdots(n+1+n+1)[/inlmath] nije djeljiv sa [inlmath]2^{n+2}[/inlmath]
Sorry I'm late a black cat blocked my path so I had to take a different way then a dragon came down and blocked my path then I saw an old lady having trouble crossing the street so I helped her then a cat was stuck in a tree and the owners asked me to help then I got lost on the road of life
Korisnikov avatar
mala_mu  OFFLINE
Zaslužni forumaš
 
Postovi: 50
Lokacija: Banja Luka
Zahvalio se: 23 puta
Pohvaljen: 72 puta

Re: Dokazivanje djeljivosti

Postod Onomatopeja » Nedelja, 22. Januar 2017, 17:20

A moze se primetiti da je [inlmath](n+1)(n+2)\cdots(n+n)=\displaystyle\frac{(2n)!}{n!}=2^n\cdot1\cdot3\cdots(2n-1)[/inlmath], gde smo iskoristili da je [inlmath](2n)!=2^nn!\cdot1\cdot3\cdots(2n-1)[/inlmath] (kod parnih se samo izvuce dvojka). Odatle samo tvrdjenje lako sledi.
 
Postovi: 613
Zahvalio se: 15 puta
Pohvaljen: 588 puta

Re: Dokazivanje djeljivosti

Postod elektricar » Ponedeljak, 23. Januar 2017, 00:13

Nije mi jasno kako je Onomatopeja zakljucio da je [inlmath]\frac{(2n)!}{n!}=(n+1)(n+2)\cdots2n[/inlmath]. Izracuno sam permutaciju od [inlmath]2n[/inlmath] te sam dobio kao i onomatopeja, ali ne razumijem zasto si na kraju podjelio sa permutacijom od [inlmath]n[/inlmath]
Poslednji put menjao Daniel dana Ponedeljak, 23. Januar 2017, 01:16, izmenjena samo jedanput
Razlog: Korekcija pravopisa
 
Postovi: 25
Zahvalio se: 17 puta
Pohvaljen: 0 puta

  • +1

Re: Dokazivanje djeljivosti

Postod Daniel » Ponedeljak, 23. Januar 2017, 01:48

Nema ovo veze s permutacijama, već s faktorijelom – iako se faktorijel koristi za računanje broja permutacija.
Ako [inlmath](n+1)(n+2)\cdots2n[/inlmath] pomnožiš sa [inlmath]1[/inlmath], a [inlmath]1[/inlmath] napišeš kao [inlmath]\frac{1\cdot2\cdots n}{1\cdot2\cdots n}[/inlmath], dobićeš
[dispmath](n+1)(n+2)\cdots2n=(n+1)(n+2)\cdots2n\cdot\frac{1\cdot2\cdots n}{1\cdot2\cdots n}=\frac{1\cdot2\cdots n(n+1)(n+2)\cdots2n}{1\cdot2\cdots n}[/dispmath] i zatim prepoznaš da je izraz u brojiocu jednak [inlmath](2n)![/inlmath], a izraz u imeniocu jednak [inlmath]n![/inlmath].

Korigovao sam ti pravopis (i u ovom tvom poslednjem, i u ranijim postovima) – molim te da obratiš pažnju na to da se nakon tačke (zareza), a pre naredne rečenice (reči) uvek stavlja razmak, tj. belina.
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: Dokazivanje djeljivosti

Postod elektricar » Ponedeljak, 23. Januar 2017, 12:11

Hvala Vam beskonacno mnogo, shvatio sam. Izvinjavam se za pravopis, nisam znao da se treba odvajati i poslije zareza.
 
Postovi: 25
Zahvalio se: 17 puta
Pohvaljen: 0 puta


Povratak na TEORIJA BROJEVA

Ko je OnLine

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


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