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

Deljivost izraza prostim brojem – takmičenje Hrvatska

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

Deljivost izraza prostim brojem – takmičenje Hrvatska

Postod drmm » Sreda, 05. Avgust 2020, 21:13

Pozdrav, ponovo ja. Ovog puta sam naleteo na jedan zanimljiv zadačić iz teorije brojeva. Malo je teži, pa ko ima vremena i volje nek' izvoli :D :

Tekst zadatka: Dokazati da za svaki prost broj [inlmath]p[/inlmath] i prirodan broj [inlmath]n\geq p[/inlmath] vrednost izraza
[dispmath]{n\choose p}-\left\lfloor\frac{n}{p}\right\rfloor[/dispmath] deljiv sa [inlmath]p[/inlmath]
drmm  OFFLINE
 
Postovi: 19
Zahvalio se: 1 puta
Pohvaljen: 17 puta

Sharuj ovu temu na:

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

Re: Deljivost izraza prostim brojem – takmičenje Hrvatska

Postod drmm » Sreda, 05. Avgust 2020, 21:57

Postaviću rešenje zadatka odmah ispod teksta. Pre samog rešenja postaviću dva hint-a ukoliko je neko zaglavio a ipak želi sam da otkrije rešenje. Ukoliko ipak neko želi skroz sam da reši zadatak savetujem da ne čita ostali deo poruke













Rešenje zadatka


Hint 1: Upotrebiti indukciju po [inlmath]n\geq p[/inlmath]

Hint 2: Posebno razmotriti slučaj [inlmath]n\equiv-1\pmod p[/inlmath]



Rešenje: Primenićemo dokaz indukcijom po [inlmath]n\geq p[/inlmath]:
1. (Baza indukcije) Za [inlmath]n=p[/inlmath] imamo:
[dispmath]{p\choose p}-\left\lfloor\frac{p}{p}\right\rfloor=1-1=0[/dispmath] Očigledno je [inlmath]p|0[/inlmath]

2. (Induktivna hipoteza) Pretpostavimo da je tvrdjenje tačno za [inlmath]n=k>p[/inlmath]. Tada možemo zapisati:
[dispmath]{k\choose p}=\left\lfloor\frac{k}{p}\right\rfloor+pr[/dispmath] gde je [inlmath]r\in\mathbb{N}[/inlmath]

3. (Induktivni korak) Primetimo pre svega da važi:
[dispmath]{k+1\choose p}=\frac{k+1}{k+1-p}\cdot{k\choose p}[/dispmath] Shodno induktivnoj hipotezi dobijamo:
[dispmath]{k+1\choose p}-\left\lfloor\frac{k+1}{p}\right\rfloor=\frac{k+1}{k+1-p}\left(\left\lfloor\frac{k}{p}\right\rfloor+pr\right)-\left\lfloor\frac{k+1}{p}\right\rfloor[/dispmath] Razmotrimo sada dva slučaja:

(a) [inlmath]k\not\equiv-1\pmod p[/inlmath]
Tada je [inlmath]\left\lfloor\frac{k+1}{p}\right\rfloor=\left\lfloor\frac{k}{p}\right\rfloor[/inlmath] i [inlmath]p\not|(k+1)[/inlmath]. Sada dobijamo:
[dispmath]\frac{k+1}{k+1-p}\left(\left\lfloor\frac{k}{p}\right\rfloor+pr\right)-\left\lfloor\frac{k+1}{p}\right\rfloor=\\
=\frac{k+1}{k+1-p}\cdot\left\lfloor\frac{k}{p}\right\rfloor+\frac{k+1}{k+1-p}\cdot pr-\left\lfloor\frac{k}{p}\right\rfloor=\\
=\frac{p}{k+1-p}\cdot\left\lfloor\frac{k}{p}\right\rfloor+\frac{pr(k+1)}{(k+1-p)}[/dispmath] Prethodno dobijeni izraz je očigledno deljiv sa [inlmath]p[/inlmath]

(b) [inlmath]k\equiv-1\pmod p[/inlmath]
Sada možemo zapisati [inlmath]k=p\cdot s-1,\,s\in\mathbb{N}[/inlmath]. Zamenom dobijamo:
[dispmath]\frac{k+1}{k+1-p}\left(\left\lfloor\frac{k}{p}\right\rfloor+pr\right)-\left\lfloor\frac{k+1}{p}\right\rfloor=\\
=\frac{ps}{p(s-1)}\left(\left\lfloor\frac{ps-1}{p}\right\rfloor+pr\right)-\left\lfloor\frac{ps}{p}\right\rfloor=\\
=\frac{s}{s-1}\left(s-1+pr\right)-s=\frac{prs}{s-1}[/dispmath] Ponovo, prethodno dobijeni izraz je deljiv sa [inlmath]p[/inlmath].

Ovime je dokaz indukcijom završen.
drmm  OFFLINE
 
Postovi: 19
Zahvalio se: 1 puta
Pohvaljen: 17 puta

Re: Deljivost izraza prostim brojem – takmičenje Hrvatska

Postod Daniel » Petak, 14. Avgust 2020, 00:05

drmm je napisao:[dispmath]\cdots=\frac{prs}{s-1}[/dispmath] Ponovo, prethodno dobijeni izraz je deljiv sa [inlmath]p[/inlmath].

Ako može pojašnjenje, na osnovu čega zaključujemo da je deljiv sa [inlmath]p[/inlmath]?
Zbog čega imenilac [inlmath]s-1[/inlmath] ne bi mogao biti jednak [inlmath]p[/inlmath] (ili deljiv sa [inlmath]p[/inlmath]), čime bi se [inlmath]p[/inlmath] kao faktor skratio u brojiocu i imeniocu?
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: 8380
Lokacija: Beograd
Zahvalio se: 4461 puta
Pohvaljen: 4454 puta

Re: Deljivost izraza prostim brojem – takmičenje Hrvatska

Postod drmm » Petak, 14. Avgust 2020, 21:18

Nadam se da nije problem da malo zakasnim sa odgovorom (ne samo u ovoj temi, vec u svim temama), jer u sledeću subotu imam državno takmičenje, pa moram da se spremam intenzivno.
drmm  OFFLINE
 
Postovi: 19
Zahvalio se: 1 puta
Pohvaljen: 17 puta

Re: Deljivost izraza prostim brojem – takmičenje Hrvatska

Postod Daniel » Petak, 14. Avgust 2020, 23:35

Naravno da nije problem.
Srećno na takmičenju, i ako može Matemanija nešto da ti pomogne – tu smo.
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: 8380
Lokacija: Beograd
Zahvalio se: 4461 puta
Pohvaljen: 4454 puta

  • +1

Re: Deljivost izraza prostim brojem – takmičenje Hrvatska

Postod Onomatopeja » Subota, 15. Avgust 2020, 14:35

Neka je [inlmath]k\in [0,p-1][/inlmath] takvo da je [inlmath]\displaystyle n=p\left\lfloor\frac{n}{p}\right\rfloor+k.[/inlmath] Tada je
[dispmath]\begin{align*}
{n\choose p}&={p\left\lfloor\frac{n}{p}\right\rfloor+k\choose p}=\frac{\Bigl(p\left\lfloor\dfrac{n}{p}\right\rfloor+k\Bigr)\cdots \Bigl(p\left\lfloor\dfrac{n}{p}\right\rfloor+1\Bigr)p\left\lfloor\dfrac{n}{p}\right\rfloor \Bigl(p\left\lfloor\dfrac{n}{p}\right\rfloor-1\Bigr)\cdots \Bigl(p\left\lfloor\dfrac{n}{p}\right\rfloor-(p-k-1)\Bigr)}{p!}\\
&=\frac{\Bigl(p\left\lfloor\dfrac{n}{p}\right\rfloor+k\Bigr)\cdots \Bigl(p\left\lfloor\dfrac{n}{p}\right\rfloor+1\Bigr)\left\lfloor\dfrac{n}{p}\right\rfloor \Bigl(p\left\lfloor\dfrac{n}{p}\right\rfloor-1\Bigr)\cdots \Bigl(p\left\lfloor\dfrac{n}{p}\right\rfloor-(p-k-1)\Bigr)}{(p-1)!}.
\end{align*}[/dispmath]
Zato je [inlmath]\displaystyle {n\choose p} \equiv \frac{k!\left\lfloor\dfrac{n}{p}\right\rfloor (-1)^{p-k-1}(p-k-1)!}{(p-1)!}\equiv \frac{(p-1)! \left\lfloor\dfrac{n}{p}\right\rfloor}{(p-1)!} \equiv \left\lfloor\frac{n}{p}\right\rfloor\pmod p,[/inlmath] sto je i trebalo pokazati.
 
Postovi: 610
Zahvalio se: 15 puta
Pohvaljen: 584 puta

Re: Deljivost izraza prostim brojem – takmičenje Hrvatska

Postod Daniel » Nedelja, 16. Avgust 2020, 17:20

Što se tiče dokaza preko indukcije i mog pitanja,
Daniel je napisao:
drmm je napisao:[dispmath]\cdots=\frac{prs}{s-1}[/dispmath] Ponovo, prethodno dobijeni izraz je deljiv sa [inlmath]p[/inlmath].

Ako može pojašnjenje, na osnovu čega zaključujemo da je deljiv sa [inlmath]p[/inlmath]?

ne uočavam da je deljivost sa [inlmath]p[/inlmath] odavde baš očigledna, ali u međuvremenu sam tu deljivost uspeo da dokažem (na ne baš kratak način). Uvrstimo [inlmath]k=ps-1[/inlmath] u jednakost [inlmath]{k\choose p}=\left\lfloor\frac{k}{p}\right\rfloor+pr[/inlmath],
[dispmath]{ps-1\choose p}=\left\lfloor\frac{ps-1}{p}\right\rfloor+pr\\
\frac{(ps-1)(ps-2)\cdots(ps-p+1)(ps-p)}{p(p-1)(p-2)\cdots2\cdot1}=s-1+pr\\
\frac{(ps-1)(ps-2)\cdots(ps-p+1)(s-1)}{(p-1)(p-2)\cdots2\cdot1}=s-1+pr[/dispmath] E sad, ako bismo pretpostavili da je [inlmath]s-1[/inlmath] deljivo sa [inlmath]p[/inlmath], tj. da je [inlmath]s-1=mp[/inlmath] ([inlmath]m\in\mathbb{N}[/inlmath]):
[dispmath]\frac{\left(mp^2+p-1\right)\left(mp^2+p-2\right)\cdots\left(mp^2+1\right)m\cancel p}{(p-1)(p-2)\cdots2\cdot1}=m\cancel p+\cancel pr\\
r=\frac{\left(mp^2+p-1\right)\left(mp^2+p-2\right)\cdots\left(mp^2+1\right)m}{(p-1)(p-2)\cdots2\cdot1}-m\\
r=m\frac{\left(mp^2+p-1\right)\left(mp^2+p-2\right)\cdots\left(mp^2+1\right)-(p-1)(p-2)\cdots2\cdot1}{(p-1)(p-2)\cdots2\cdot1}[/dispmath] Pošto [inlmath]\left(mp^2+p-1\right)\left(mp^2+p-2\right)\cdots\left(mp^2+1\right)[/inlmath], kad se izmnoži, predstavlja neki izraz oblika [inlmath]mp^2f(m,p)+(p-1)(p-2)\cdots2\cdot1[/inlmath], to možemo pisati
[dispmath]r=m\frac{mp^2f(m,p)+\cancel{(p-1)(p-2)\cdots2\cdot1}-\cancel{(p-1)(p-2)\cdots2\cdot1}}{(p-1)(p-2)\cdots2\cdot1}\\
r=\frac{m^2p^2f(m,p)}{(p-1)(p-2)\cdots2\cdot1}\\
\overset{mp=s-1}{=\!=\!=\!\Longrightarrow}\quad r=\frac{mp(s-1)f(m,p)}{(p-1)(p-2)\cdots2\cdot1}[/dispmath] Uvrštavanjem dobijenog izraza za [inlmath]r[/inlmath] u posmatrani izraz [inlmath]\frac{prs}{s-1}[/inlmath],
[dispmath]\frac{prs}{s-1}=\frac{ps}{\cancel{s-1}}\cdot\frac{mp\cancel{(s-1)}f(m,p)}{(p-1)(p-2)\cdots2\cdot1}=\frac{mp^2sf(m,p)}{(p-1)(p-2)\cdots2\cdot1}[/dispmath] što znači da će, u slučaju da je [inlmath]s-1[/inlmath] deljivo sa [inlmath]p[/inlmath], taj izraz biti deljiv ne samo sa [inlmath]p[/inlmath], već i sa [inlmath]p^2[/inlmath].
U suprotnom, u slučaju da [inlmath]s-1[/inlmath] nije deljivo sa [inlmath]p[/inlmath], deljivost izraza [inlmath]\frac{prs}{s-1}[/inlmath] sa [inlmath]p[/inlmath] sasvim je očigledna.

Naravno, ukoliko postoji neki očigledniji način da se deljivost izraza [inlmath]\frac{prs}{s-1}[/inlmath] sa [inlmath]p[/inlmath] odmah uoči, zanimaće me da ga vidim.
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: 8380
Lokacija: Beograd
Zahvalio se: 4461 puta
Pohvaljen: 4454 puta


Povratak na TEORIJA BROJEVA

Ko je OnLine

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


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