Teorija števil
Re: Teorija števil
Hvala za prejšnjo nalogo, ni čudno da nisem našla rešitve:)
Zanima me še za 2 nalogi:
1.) Določite vsa praštevila p, za katera velja da je 3p+8 popoln kub.
\(3p+8=a^3\), pogledam za nekaj prvih praštevil, neuspešno. Kako se rešuje takšno nalogo?
2.) Dokažite, da je \(\sum_{d|n}\frac{1}{d}=\frac{\sigma(n)}{n}\).
Zapišem malo drugače: \(n \sum_{d|n}\frac{1}{d}=\sum_{d|n}d\) kako bi sedaj reševali dalje?
Zanima me še za 2 nalogi:
1.) Določite vsa praštevila p, za katera velja da je 3p+8 popoln kub.
\(3p+8=a^3\), pogledam za nekaj prvih praštevil, neuspešno. Kako se rešuje takšno nalogo?
2.) Dokažite, da je \(\sum_{d|n}\frac{1}{d}=\frac{\sigma(n)}{n}\).
Zapišem malo drugače: \(n \sum_{d|n}\frac{1}{d}=\sum_{d|n}d\) kako bi sedaj reševali dalje?
Re: Teorija števil
1)
Hm. Greva poskusit. Ce je 3p+8=n^3, potem je
\(n^3=8\mod 3\)
kar z Eulerjevo enacbo predelas v
\(n=2\mod 3\)
Ce je \(n=3a+2\), potem prepises
\(3p+8=n^3=27a^3+54a^2+36a+8\)
\(p=a(9a^2+18a+12)\)
To je sestavljeno stevilo, torej resitev ni (a=1 bi bila sansa, samo potem je oklepaj sestavljen).
2)
Hm. Torej imas
\(\sum_{d|n}d=\sigma(n)\)
A ni to ze to?
Hm. Greva poskusit. Ce je 3p+8=n^3, potem je
\(n^3=8\mod 3\)
kar z Eulerjevo enacbo predelas v
\(n=2\mod 3\)
Ce je \(n=3a+2\), potem prepises
\(3p+8=n^3=27a^3+54a^2+36a+8\)
\(p=a(9a^2+18a+12)\)
To je sestavljeno stevilo, torej resitev ni (a=1 bi bila sansa, samo potem je oklepaj sestavljen).
2)
Hm. Torej imas
\(\sum_{d|n}d=\sigma(n)\)
A ni to ze to?
Re: Teorija števil
1.) Aha vse jasno, 100x hvala
2.) Am, kako pa vemo, da velja enakost
2.) Am, kako pa vemo, da velja enakost
delta napisal/-a:\(n \sum_{d|n}\frac{1}{d}=\sum_{d|n}d\)
Re: Teorija števil
2)
Ce d deli n, potem n/d tudi deli n. Vsota tece po vseh deliteljih d, s cimer tudi n/d obisce ravno vse delitelje, samo v obratnem vrstnem redu. V bistvu bi bilo bolj prav pisat
\(n\sum_{d|n}\frac{1}{d}=\sum_{f|n}f;\quad f\cdot d=n\)
Ce d deli n, potem n/d tudi deli n. Vsota tece po vseh deliteljih d, s cimer tudi n/d obisce ravno vse delitelje, samo v obratnem vrstnem redu. V bistvu bi bilo bolj prav pisat
\(n\sum_{d|n}\frac{1}{d}=\sum_{f|n}f;\quad f\cdot d=n\)
Re: Teorija števil
3) Vemo, da ima Pellova enačba \(x^2-2y^2=1\) neskončno rešitev v naravnih številih. Če potem označimo \(n=y\) in \(m=x+y\) (kjer \(x\) in \(y\) rešita Pellovo enačbo), so \((m^2-n^2,2mn,m^2+n^2)\) ustrezne pitagorejske trojice: \(m^2-n^2-2mn=(x+y)^2-y^2-2y(x+y)=1\).
Re: Teorija števil
Matematično tega seveda ne znam dokazati oziroma mislim, da to ne bo matematični dokaz, nisem matematik, pa vseeno ... Mogoče bi bilo v pomoč naslednje, kar sem našel v enem od virov:Zajc napisal/-a:A je kdo že rešil 3.?
Vemo, da števila 3,4 in 5 tvorijo pitagorejsko trojico. Torej naj bodo \(3n\) , \(4n\) in \(5n\) poljubni večkratniki trojice 3, 4 in 5 (\(n>0\)):
\((3n)^2 + (4n)^2=9n^2 + 16n^2\)
\(=(9+16)n^2\)
\(=25n^2\)
\(=(5n)^2\)
Torej \(3n, 4n, 5n\) tvorijo pitagorejsko trojico. Vidimo, da to velja za vsako pozitvno celo število (\(n\)) in glede na to, da nam \(n\) daje različne pitagorejske trojice, lahko ugotovimo, da jih je neskončno mnogo.
No sem naknadno videl, da je že Jurij rešil problem, tako kot se mora in tako kot pač matematiki to počnejo.
Re: Teorija števil
@problemi
s tem dobis samo trivialne razsiritve ene same pitagorejske trojice, ki nas ponavadi niti ne zanimajo. Pa te nikakor ne morejo imeti razlike dolzin katet 1 (po tem sprasuje naloga), ce sta obe deljivi z n.
To, da je pitagorejskih trojic neskoncno je cisto drugo vprasanje (ze primitivnih trojic je neskoncno mnogo).
s tem dobis samo trivialne razsiritve ene same pitagorejske trojice, ki nas ponavadi niti ne zanimajo. Pa te nikakor ne morejo imeti razlike dolzin katet 1 (po tem sprasuje naloga), ce sta obe deljivi z n.
To, da je pitagorejskih trojic neskoncno je cisto drugo vprasanje (ze primitivnih trojic je neskoncno mnogo).
Re: Teorija števil
Pri vas naravoslovcih sta možni samo dve stanji. Eno je "Ni možno!" in drugo je "Trivialno!". Meni je bila pa tako elegantna "rešitev". No, šalo na stran.Aniviller napisal/-a:@problemi
s tem dobis samo trivialne razsiritve ene same pitagorejske trojice, ki nas ponavadi niti ne zanimajo. Pa te nikakor ne morejo imeti razlike dolzin katet 1 (po tem sprasuje naloga), ce sta obe deljivi z n.
To, da je pitagorejskih trojic neskoncno je cisto drugo vprasanje (ze primitivnih trojic je neskoncno mnogo).
Uh, sem pogledal malo bolje v naslednji vir:http://pefprints.pef.uni-lj.si/922/1/hocevar_katja.pdf
Našel pa sem, če bi koga zanimalo, tudi glede primitivnih pitagorejskih trojk Gaussovih celih števil:http://dkum.uni-mb.si/Dokument.php?id=12168
Bo najbolje, da se iz debate umaknem ...
Re: Teorija števil
3. Res lepa rešitev:), do sedaj še nisem vedela, da obstaja povezava med Pellovo enačbo in pit. trojicami(pri pit. trojicah je vmes + \(x^2+y^2 =z^2\), Pellova ima minus \(x^2-ny^2=1\) kako je potem to?? ). In kako se 'spomnimo', da uporabimo za to Pellovo enačbo:
zakaj je res:
Še ena naloga: če ima kdo idejo
9.) Pokaži, da je praštevil oblike 4n+1 neskončno.(nekako s protislovjem.?)
,Jurij napisal/-a:Vemo, da ima Pellova enačba x^2-2y^2=1
zakaj je res:
ali lahko utemeljimo, da to sledi, da je rešitev za Pellovo enačbo neskončno mnogo. Zakaj je primitivnih pit. trojic neskončno mnogo?Aniviller napisal/-a:To, da je pitagorejskih trojic neskoncno je cisto drugo vprasanje (ze primitivnih trojic je neskoncno mnogo).
Še ena naloga: če ima kdo idejo
9.) Pokaži, da je praštevil oblike 4n+1 neskončno.(nekako s protislovjem.?)
Re: Teorija števil
Povezava s Pellovo enacbo najbrz ne gre v obe smeri (to, da je razlika katet 1 je poseben primer, ostale trojice ne dajo Pellove enacbe z desno stranjo 1).delta napisal/-a:ali lahko utemeljimo, da to sledi, da je rešitev za Pellovo enačbo neskončno mnogo. Zakaj je primitivnih pit. trojic neskončno mnogo?
Primitivnih pit. trojic je neskoncno mnogo ze zaradi Evklidove formule (m^2-n^2,2mn,m^2+n^2), kjer takoj vidis, da jih je neskoncno, ce je sodo-lihih parov tujih si stevil neskoncno. Celo rekurzivna formula obstaja, ki iz (3,4,5) zgenerira vse ostale!
http://en.wikipedia.org/wiki/Tree_of_pr ... an_triples
Re: Teorija števil
V virih je moč prebrati, da prvo predpostaviš, da je število takšnih praštevil končno, ko to želiš dokazati ugotoviš, da je ta predpostavka protislovna, ergo ...ampak ....delta napisal/-a: 9.) Pokaži, da je praštevil oblike 4n+1 neskončno.(nekako s protislovjem.?)
Praštevilo oblike 4n+1 lahko zapišeš tudi kot vsoto dveh kvadratov, lahko da ti bo to v pomoč:
\(p=a^2 + b^2=(a+bi)(a-bi)\)
Re: Teorija števil
9)
Denimo, da je takih praštevil končno mnogo: \(p_i \equiv 1 \pmod{4}\) za \(i=1,\dots ,n\). Označimo \(a=2\cdot p_1 \cdots p_n\) in si oglejmo število \(a^2+1\). To ni praštevilo (saj bi bilo sicer oblike \(4n+1\), kar pa je v protislovju s predpostavko), zato je sestavljeno; za vsak njegov prafaktor velja \(p\equiv 3 \pmod{4}\). Naj bo sedaj \(p\) poljuben prafaktor:
\(a^2+1\equiv 0 \pmod{p}\)
\(\Rightarrow \ a^2\equiv -1 \pmod{p}\)
\(\Rightarrow \ (a^2)^{\frac{p-1}{2}}\equiv(-1)^{\frac{p-1}{2}} \pmod{p}\);
ker je \(a\) tuj proti \(p\), po malem Fermatovem izreku sledi
\(1 \equiv (-1)^{\frac{p-1}{2}} \pmod{p}\),
to pa je možno le, če je \(\frac{p-1}{2}\) sodo število: \(\frac{p-1}{2}=2k \ \Rightarrow \ p=4k+1\), to pa je spet protislovje s predpostavko.
Denimo, da je takih praštevil končno mnogo: \(p_i \equiv 1 \pmod{4}\) za \(i=1,\dots ,n\). Označimo \(a=2\cdot p_1 \cdots p_n\) in si oglejmo število \(a^2+1\). To ni praštevilo (saj bi bilo sicer oblike \(4n+1\), kar pa je v protislovju s predpostavko), zato je sestavljeno; za vsak njegov prafaktor velja \(p\equiv 3 \pmod{4}\). Naj bo sedaj \(p\) poljuben prafaktor:
\(a^2+1\equiv 0 \pmod{p}\)
\(\Rightarrow \ a^2\equiv -1 \pmod{p}\)
\(\Rightarrow \ (a^2)^{\frac{p-1}{2}}\equiv(-1)^{\frac{p-1}{2}} \pmod{p}\);
ker je \(a\) tuj proti \(p\), po malem Fermatovem izreku sledi
\(1 \equiv (-1)^{\frac{p-1}{2}} \pmod{p}\),
to pa je možno le, če je \(\frac{p-1}{2}\) sodo število: \(\frac{p-1}{2}=2k \ \Rightarrow \ p=4k+1\), to pa je spet protislovje s predpostavko.
Re: Teorija števil
Najlepša hvala, vse jasno, samo težko se je spomnit
Nekaj v zvezi s teorijo.
Naj bo \(p \in \mathb{P}, p>=3\). \(p=x^2+y^2, x,y \in \mathb{Z}\). Po modulu p:\(x^2+y^2=0(mod p)\). x,y tuja proti p, torej obrnljiva v \(\mathb{Z}_p^*\), \(\mathb{Z}_p^*\) je reduciran sistem ostankov. Vpr.: zakaj sta obrnljiva?
Dokaz naslednje trditve in posledice mi res ni ravno jasen. Kako smo si pomagali z ekvivalenčnimi razredi?
Trditev: Naj bo \(p \in \mathb{P}\). Za enačbo \(x^2=-1(mod p)\) velja:
1. če je p=2 ima eno rešitev
2. če je p=1(mod 4) ima dve rešitvi
3. če je p=3(mod 4) nima rešitve.
Dokaz:(2.,3.)
Na množici \(\mathb{Z}_p^*\) uvedemo ekvivalenčno relacijo kot najmanjšo tisto, pri kateri so ekvivalentni \(x, -x,x^{-1}, -x^{-1}\).
Tipičen ekviv. razred ima 4 elemente\(\{x, -x,x^{-1}, -x^{-1}\}\). Izjemni ekviv. razredi so tisti, ko kakšne točke sovpadajo:
a)\(x=x^{-1}(mod p)=>\)
\(x^2=1(mod p)=>x^2-1=0(mod p)\)
\(x=1(mod p) in x=-1 (mod p)\). Dobimo en dvoelem. ekviv. razred \(\{1,p-1\}\). Kako smo ga dobili?
b) \(x=-x^{-1}(mod p)=> x^2=-1(mod p)\). Ta enačba lahko nima rešitev, ali ima največ 2 rešitvi, ker je st. 2 in je \(p\in \mathb{P}\)
Če ima eno rešitev m, potem je tudi -m rešitev(zakaj? ali zato ker imamo \(x^2\)), dobimo še en ekviv. razred \(\{m,-m\}\). Vsi ekviv. razredi določajo dekompozicijo \(\mathb{Z}_p^*\) na podmnožico moči 4, eno moči 2 in morda še eno moči 2.
Dokaz za 2.:
če je \(p=1(mod 4)=> p-1=0(mod 4)\), \(4|p-1\) zato morata obstajati dva ekviv. razreda moči 2. Torej ima enačba \(x^2=-1 (mod p)\) dve rešitvi (zakaj?)
Dokaz za 3.:
če je \(p=3(mod 4)\) =>\(p-1=2(mod 4)\) in v \(\mathb{Z}_p^*\) je le en ekviv. razred moči 2(zakaj?), zato \(x^2=-1(mod p)\) nima rešitve(zakaj?).
Posledica:
Če je \(n=x^2+y^2, x,y \in \mathb{Z}\) in \(p=3(mod 4 )\) deli n, potem \(p^2\) deli n.
Dokaz:
p|n => \(x^2+y^2=0(mod p)\). Trdimo, da je p|x in p|y. Recimo, da p ne deli x,potem im x inverz modulo p in sledi, da imamo rešitev za kongruenco \(z^2=-1(mod p)\)(zakaj?). To vemo, da po zg. trditvi ne velja, torej p|x in \(p^2|x^2\) ter \(p^2|y^2\)=> \(p^2|x^2+y^2\).
Kdo razume?
Nekaj v zvezi s teorijo.
Naj bo \(p \in \mathb{P}, p>=3\). \(p=x^2+y^2, x,y \in \mathb{Z}\). Po modulu p:\(x^2+y^2=0(mod p)\). x,y tuja proti p, torej obrnljiva v \(\mathb{Z}_p^*\), \(\mathb{Z}_p^*\) je reduciran sistem ostankov. Vpr.: zakaj sta obrnljiva?
Dokaz naslednje trditve in posledice mi res ni ravno jasen. Kako smo si pomagali z ekvivalenčnimi razredi?
Trditev: Naj bo \(p \in \mathb{P}\). Za enačbo \(x^2=-1(mod p)\) velja:
1. če je p=2 ima eno rešitev
2. če je p=1(mod 4) ima dve rešitvi
3. če je p=3(mod 4) nima rešitve.
Dokaz:(2.,3.)
Na množici \(\mathb{Z}_p^*\) uvedemo ekvivalenčno relacijo kot najmanjšo tisto, pri kateri so ekvivalentni \(x, -x,x^{-1}, -x^{-1}\).
Tipičen ekviv. razred ima 4 elemente\(\{x, -x,x^{-1}, -x^{-1}\}\). Izjemni ekviv. razredi so tisti, ko kakšne točke sovpadajo:
a)\(x=x^{-1}(mod p)=>\)
\(x^2=1(mod p)=>x^2-1=0(mod p)\)
\(x=1(mod p) in x=-1 (mod p)\). Dobimo en dvoelem. ekviv. razred \(\{1,p-1\}\). Kako smo ga dobili?
b) \(x=-x^{-1}(mod p)=> x^2=-1(mod p)\). Ta enačba lahko nima rešitev, ali ima največ 2 rešitvi, ker je st. 2 in je \(p\in \mathb{P}\)
Če ima eno rešitev m, potem je tudi -m rešitev(zakaj? ali zato ker imamo \(x^2\)), dobimo še en ekviv. razred \(\{m,-m\}\). Vsi ekviv. razredi določajo dekompozicijo \(\mathb{Z}_p^*\) na podmnožico moči 4, eno moči 2 in morda še eno moči 2.
Dokaz za 2.:
če je \(p=1(mod 4)=> p-1=0(mod 4)\), \(4|p-1\) zato morata obstajati dva ekviv. razreda moči 2. Torej ima enačba \(x^2=-1 (mod p)\) dve rešitvi (zakaj?)
Dokaz za 3.:
če je \(p=3(mod 4)\) =>\(p-1=2(mod 4)\) in v \(\mathb{Z}_p^*\) je le en ekviv. razred moči 2(zakaj?), zato \(x^2=-1(mod p)\) nima rešitve(zakaj?).
Posledica:
Če je \(n=x^2+y^2, x,y \in \mathb{Z}\) in \(p=3(mod 4 )\) deli n, potem \(p^2\) deli n.
Dokaz:
p|n => \(x^2+y^2=0(mod p)\). Trdimo, da je p|x in p|y. Recimo, da p ne deli x,potem im x inverz modulo p in sledi, da imamo rešitev za kongruenco \(z^2=-1(mod p)\)(zakaj?). To vemo, da po zg. trditvi ne velja, torej p|x in \(p^2|x^2\) ter \(p^2|y^2\)=> \(p^2|x^2+y^2\).
Kdo razume?