Teorija števil

Ko tudi učitelj ne more pomagati...
Odgovori
delta
Prispevkov: 420
Pridružen: 19.8.2009 14:16

Re: Teorija števil

Odgovor Napisal/-a delta »

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?

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

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?

delta
Prispevkov: 420
Pridružen: 19.8.2009 14:16

Re: Teorija števil

Odgovor Napisal/-a delta »

1.) Aha :) vse jasno, 100x hvala
2.) Am, kako pa vemo, da velja enakost
delta napisal/-a:\(n \sum_{d|n}\frac{1}{d}=\sum_{d|n}d\)

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

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\)

delta
Prispevkov: 420
Pridružen: 19.8.2009 14:16

Re: Teorija števil

Odgovor Napisal/-a delta »

Aha, razumem :) , hvala.

Zajc
Prispevkov: 1099
Pridružen: 26.6.2008 19:15

Re: Teorija števil

Odgovor Napisal/-a Zajc »

A je kdo že rešil 3.?

Jurij
Prispevkov: 585
Pridružen: 27.2.2006 11:09

Re: Teorija števil

Odgovor Napisal/-a Jurij »

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

problemi
Prispevkov: 4931
Pridružen: 24.8.2009 1:20

Re: Teorija števil

Odgovor Napisal/-a problemi »

Zajc napisal/-a:A je kdo že rešil 3.?
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:

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

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

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

problemi
Prispevkov: 4931
Pridružen: 24.8.2009 1:20

Re: Teorija števil

Odgovor Napisal/-a problemi »

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

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

delta
Prispevkov: 420
Pridružen: 19.8.2009 14:16

Re: Teorija števil

Odgovor Napisal/-a delta »

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:
Jurij napisal/-a:Vemo, da ima Pellova enačba x^2-2y^2=1
,
zakaj je res:
Aniviller napisal/-a:To, da je pitagorejskih trojic neskoncno je cisto drugo vprasanje (ze primitivnih trojic je neskoncno mnogo).
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?

Še ena naloga: če ima kdo idejo :)
9.) Pokaži, da je praštevil oblike 4n+1 neskončno.(nekako s protislovjem.?)

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

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

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

problemi
Prispevkov: 4931
Pridružen: 24.8.2009 1:20

Re: Teorija števil

Odgovor Napisal/-a problemi »

delta napisal/-a: 9.) Pokaži, da je praštevil oblike 4n+1 neskončno.(nekako s protislovjem.?)
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 .... :)

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)\)

Jurij
Prispevkov: 585
Pridružen: 27.2.2006 11:09

Re: Teorija števil

Odgovor Napisal/-a Jurij »

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.

delta
Prispevkov: 420
Pridružen: 19.8.2009 14:16

Re: Teorija števil

Odgovor Napisal/-a delta »

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? :)

Odgovori