Teorija števil

Ko tudi učitelj ne more pomagati...
Odgovori
Jurij
Prispevkov: 585
Pridružen: 27.2.2006 11:09

Re: Teorija števil

Odgovor Napisal/-a Jurij »

Obrnljiva sta, ker sta manjša od \(p\) in oba različna od \(0\).

Preden komentiram dokaz trditve: mislim, da je lažje, če postopaš kot v drugi polovici mojega prejšnjega posta; tam se namreč vidi, da za \(p >2\) rešitve obstajajo natanko tedaj, ko je \(p \equiv 1 \pmod{4}\). Potem ni težko premisliti, da sta rešitvi natanko dve, namreč \(1\) in \(-1\) (oz. \(p-1\)).

Po vsti:
a) To enačbo lahko rešimo: \(x^2-1\equiv 0 \pmod{p}\); ker je \(\mathbb{Z}_p\) cel kolobar (celo polje), lahko sklepamo \(x=1\) ali \(x=-1\). Ker v tem primeru (torej pod predpostavko \(x=x^{-1}\)) ekvivalenčni razred izgleda kot \(\{ x,-x\}\), v obeh primerih dobimo isti razred \(\{ 1,-1\}\).

b) ja. Ampak verjetno si hotela reči tole: dekompozicija \(\mathbb{Z}_p^*\) sestoji iz množic moči 4 in ene oz. dveh množic moči 2.

2.: ker je moč \(\mathbb{Z}_p^*\) večkratnik števila 4, ne more obstajati zgolj en razred moči 2 (ker bi bili vsi ostali potem moči 4), ampak morata biti dva, torej tudi tisti iz točke b), ki pa obstaja natanko tedaj, ko je enačba \(x^2 \equiv -1 \pmod{p}\) rešljiva.

3.: kot v prejšnjem primeru; če bi bila dva, bi bilo \(p-1\equiv 0 \pmod{4}\), zato je samo eden, torej tistega iz točke b) ni.

dokaz posledice: če ima \(x\) inverz, lahko pišemo \(z=x^{-1}y\) in enačba \(x^2+y^2\equiv 0 \pmod{p}\) preide v \(1^2+x^{-2}y^2\equiv 0 \pmod{p}\) oziroma \(z^2\equiv -1 \pmod{p}\); ampak to pa ni rešljivo, zaradi prejšnje trditve, torej \(x\) (in \(y\)) nimata inverzov, torej sta deljiva s \(p\).

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Jurij napisal/-a:Obrnljiva sta, ker sta manjša od p in oba različna od 0.
, hm še vedno ne vidim, zakaj potem obstaja inverz.
Jurij napisal/-a:Potem ni težko premisliti, da sta rešitvi natanko dve, namreč 1 in -1 (oz. p-1).
iz kje to vidimo? iz prejšnje naloge?
a) razumem
b)
Jurij napisal/-a:dekompozicija \mathbb{Z}_p^* sestoji iz množic moči 4 in ene oz. dveh množic moči 2.
ne vidim zakaj.?
2.)
Jurij napisal/-a:ker je moč \mathbb{Z}_p^* večkratnik števila 4, ne more obstajati zgolj en razred moči 2 (ker bi bili vsi ostali potem moči 4)
zakaj bi bili ostali moči 4? Ni mi jasno, kako so ti ekviv. razredi povezani z \(\mathb{Z}_p^*\). Če prav razumem, je \(\mathb{Z}_p^*\) sest. iz ekviv. razredov, zakaj pa npr. ne bi mogli imeti enega ekviv. razreda moči 4(ali zato, ker sta edini možni rešitvi x=1 in x=-1 in dobimo največ ekviv. razred moči 2?) in moramo potem imeti 2 moči 2, da je deljivo s 4.

3. torej velja v obe smeri?: dva ekviv. razreda <=>\(p-1=0(mod 4)\), če pa \(p-1\neq 0(mod 4)\)=> le en ekviv. razred, še vedno ne vidim zakaj?

posledica: razumem :)
Najlepša hvala za pomoč :)

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

Re: Teorija števil

Odgovor Napisal/-a Jurij »

- Pa saj ravno to je poanta praštevila: če je naravno število manjše od nekega praštevila, ima inverz (modulo to praštevilo), saj je \(\mathbb{Z}_p\) polje.

- Pravzaprav sem napisal bedarijo (1 in -1 nista rešitvi). Lahko imaš največ dve rešitvi (ker je polinom stopnje 2); iz tistega prej vidimo, da enačba je rešljiva, torej jo reši nek u; očitno jo potem reši tudi -u, torej imaš 2 rešitvi.

b) Poglej, relacija je zastavljena tako, da so ekvivalenčni razredi moči največ 4, saj so enaki \(\{ x,-x,x^{-1},-x^{-1} \}\). Lahko se zgodi da so manjši: to je možno v primeru, da je bodisi \(x=x^{-1}\) bodisi \(x=-x^{-1}\) (če so trije elementi iz prejšnje množice enaki, prideš v protislovje). Prvi primer se zgodi natanko enkrat (to je a)), drugi pa le včasih (in če se zgodi, se zgodi samo enkrat, ker vsebuje rešitvi kvadratne enačbe; to je b)). Skratka, imaš recimo ekv. razrede moči 4: \(A_1,\dots ,A_r\), en ekvivalenčni razred moči 2: \(B_1=\{1,-1\}\), glede na deljivost \(p\) s 4 pa imaš lahko še en ekv. razred moči 2: \(B_2=\{y,-y\}\), kjer \(y\) zadošča \(y^2\equiv -1 \pmod{p}\) (ta razred obstaja natanko tedaj, ko je ta enačba rešljiva). Zato imaš dekompozicijo oblike bodisi \(\mathbb{Z}_p^*=A_1\cup \dots \cup A_r \cup B_1\) bodisi \(\mathbb{Z}_p^*=A_1\cup \dots \cup A_r \cup B_1 \cup B_2\).

3. ja, seveda imaš ekvivalenco v obe smeri: če imaš dva ekv. razreda, potem ti moči množic v dekompoziciji povejo \(p-1=4r+2+2\), torej \(p\equiv 1 \pmod{4}\); če pa imaš en ekv. razred, dobiš \(p-1=4r+2\), torej \(p\equiv 3 \pmod{4}\).

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

Re: Teorija števil

Odgovor Napisal/-a Jurij »

Mogoče še to: če je \(p \equiv 1 \pmod{4}\), potem lahko rešitev enačbe \(x^2\equiv -1 \pmod{p}\) izračunaš eksplicitno preko Wilsonovega izreka:
množico neničelnih ostankov pri deljenju s \(p\) razdeli na dve množici: \(A=\{1,2,\dots ,\frac{p-1}{2} \}\) in \(B=\{\frac{p-1}{2}+1,\dots ,p-2,p-1 \}\); velja \(|A|=|B|=\frac{p-1}{2}\). Označi \(x=1\cdot 2 \cdot \dots \cdot \frac{p-1}{2}\); ker je \(j(p-j)\equiv -j^2 \pmod{p}\), lahko na ta način zmnožimo ustrezne dvojice elementov iz množic \(A\) in \(B\), od koder sledi \((p-1)!=(-1)^{\frac{p-1}{2}}x^2=x^2\). Po Wilsonovem izreku potem sledi \(x^2\equiv -1 \pmod{p}\).

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Najlepša hvala sedaj mi je vse skupaj malo bolj jasno :)
b), 3. razumem
lp

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Nekaj nalog, če kdo ve, kako se reši.

1. Določite ostanek pri deljenju števila \({{10}^{11}}^12\) s 13.

Rešitev:
Pomagam si z Eulerjevim izrekom \(a^{\phi(m)}=1(mod m)\).
Dobim: \(10^{\phi(13)}=1(mod 13)\)
\(10^{12}=1(mod13)\)
Sedaj pogledam ostanek \(11^{12}\) pri deljenju z 12. \(11^{\phi{12}}=1(mod 12)\)
\(11^4=1(mod12)\), torej dobim \(10^1=10(mod 13)\). Ostanek je tako 10. Kje sem se pri tem izračunu zmotila, Mathematica mi vrne
rezultat 1.

2.Zapiši v obliki verižnega ulomka \(\sqrt{n^2-1}\)
3.Zapiši v obliki verižnega ulomka \(\sqrt{\frac{7}{4}}\)
4.Pokažite, da diofantska enačba \(x^2+y^2=m\) ni rešljiva za \(m=3(mod 4)\)
Ali kdo ve, kako se lotimo Pelleve enačbe, če ima na desni -1. Primer je iz 2.8. 5.) naloga.

Lepo prosim za pomoč :)

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

1) tvoja resitev je pravilna.

Koda: Izberi vse

http://www.wolframalpha.com/input/?i=10^%2811^12%29+mod+13
Oklepaji so ti manjkali.

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Ulomki:
\(\sqrt{\frac{7}{4}}=1+(\sqrt{\frac{7}{4}}-1)=1+\frac{\frac74-1}{\sqrt{\frac74}+1}\)
\(=1+\frac{3}{4+4\sqrt\frac74}\)
V imenovalcu je spet isti koren, kar pomeni, da lahko spet vstavis isti izraz samega vase:
\(=1+\frac{3}{4+4\left(1+\frac{3}{4+4\sqrt\frac74}\right)}\)
\(=1+\frac{3}{8+\frac{3}{1+\sqrt\frac74}}\)
to lahko ponavljas, dokler ne prides do ponavljanja.

Tistega simbolicnega mogoce lahko takole:
\(\sqrt{(n-1)(n+1)}=(n-1)\sqrt{1+\frac{2}{n-1}}\)
Ta koren pa lahko predelas v nekaj, kar lahko rekurzivno vstavljas:
\(\sqrt{1+\frac{2}{n-1}}=1+\frac{1+\frac{2}{n-1}-1}{\sqrt{1+\frac{2}{n-1}}+1}\)
oziroma
\(u=1+\frac{2}{(n-1)(u+1)}\)
kjer je "u" okrajsava za rekurzivni rezultat, ki ga samo naprej vstavljas samega vase.

Mozno da ni najboljsi nacin.

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Aja se to, tole so posploseni verizni ulomki, sicer moras malo bolj pazit kaj delas.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Pri \(\sqrt{\frac{7}{4}\) dobim \(1+\frac{3}{8+\frac{3}{2+\frac{3}{8+\frac{3}{1+\sqrt\frac74}}}}\), opazim, da se 8 in 2 ves čas ponavljata. Samo, ali ne bi mogli dobiti v števcu 1 namesto 3, da bi se reklo verižni ulomek, Mathematica za tega za prvih 8 št. vrne:{1, 3, 10, 3, 2, 3, 10, 3}

Pri simboličnem je potem pred verižnim ulomkom faktor (n-1), ali to kaj moti in je treba zapisati drugače?
Aniviller napisal/-a:Aja se to, tole so posploseni verizni ulomki, sicer moras malo bolj pazit kaj delas.
??kateri so poslošeni in kateri ne, pri katerih moram pazit, in kaj?

Hvala za pomoč. :)

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Ja ravno to sem mislil s tem, da je posplosen verizni ulomek.
http://en.wikipedia.org/wiki/Generalize ... d_fraction
Pazit moras, ker ce hoces da je v kanonicni obliki, moras na vsakem koraku vedet koliksen je celi del imenovalca, kar je zoprno pocetje - lahko gres s kalkulatorjem ali z resevanjem neenacb ali s poskusanjem.
\(\sqrt{\frac74}=1+(\sqrt{\frac74}-1)=\)
\(=1+\frac{\frac34}{\sqrt{\frac74}+1}=\)
\(=1+\frac{1}{\frac{4}{3}(\sqrt{\frac74}+1)}=\) //nekako ugotovis, da je ta stvar spodaj med 3 in 4
\(=1+\frac{1}{3+(\frac{4}{3}\sqrt{\frac74}+\frac{4}{3}-3)}=\)
\(=1+\frac{1}{3+(\frac{4}{3}\sqrt{\frac74}-\frac{5}{3})}=\)
\(=1+\frac{1}{3+\frac{\frac{28}{9}-\frac{25}{9}}{\frac{4}{3}\sqrt{\frac74}+\frac{5}{3}}}=\)
\(=1+\frac{1}{3+\frac{1}{4\sqrt{\frac74}+5}}=\) //imenovalec je 10.29..., vzames 10 + nekaj.
in tako naprej... dokaj zoprno je.

Podobno je pri simbolicni varianti. Prvi korak je, da ugotovis, da je celi del \(\sqrt{n^2-1}\) kar n-1. Potem pa nadaljujes. Prvi korak je torej
\(\sqrt{n^2-1}=(n-1)\sqrt{1+\frac{2}{n-1}}=(n-1)+(n-1)(\sqrt{1+\frac{2}{n-1}}-1)=\)
\(=(n-1)+(n-1)\frac{\frac{2}{n-1}}{\sqrt{1+\frac{2}{n-1}}+1}=\)
\(=(n-1)+\frac{1}{\frac{1}{2}\sqrt{1+\frac{2}{n-1}}+\frac{1}{2}}\)
Tukaj imas sreco, ker ni tezko opazit, da je imenovalec med 1 in 2 (koren je 1+nekaj malega). Tako da dobis
\(=(n-1)+\frac{1}{1+\frac{1}{2}(\sqrt{1+\frac{2}{n-1}}-1)}=\)
\(=(n-1)+\frac{1}{1+\frac{1}{2}\frac{\frac{2}{n-1}}{\sqrt{1+\frac{2}{n-1}}+1}}=\)
\(=(n-1)+\frac{1}{1+\frac{1}{(n-1)(\sqrt{1+\frac{2}{n-1}}+1)}}=\)
Zadnji imenovalec je enak prvotnemu izrazu plus dodatek: \(\sqrt{n^2-1}+n-1\), celi del tega je 2(n-1):
\(=(n-1)+\frac{1}{1+\frac{1}{2(n-1)+(n-1)(\sqrt{1+\frac{2}{n-1}}-1)}}=\)
Ostanek \((n-1)(\sqrt{1+\frac{2}{n-1}}-1)\) pa ze poznas iz prve vrstice: enak je celemu ulomku, torej se zadeva zacne ponavljat:
\(\sqrt{n^2-1}=[n-1;1,2(n-1),1,2(n-1),...]\)
Zdaj dejansko lahko gres vstavljat:
\(\sqrt{15}=[3;1,6,1,6,1,6,...]\)
in podobno.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

1. Naloga:
Poišči vsa naravna števila, za katera je \(\frac{1}{x}+\frac{1}{y}+\frac{2}{z}\) naravno število. \(x,y,z \in \mathbb{N}\).
Opazim, da bodo morala biti naravna števila kar majhna, če želimo, da se bo zgoraj seštelo v naravno število.
Grem gledat po vrsti:
možne trojke so:(1,1,1), (1,1,2),(2,2,1),(2,2,2),(1,3,3),(3,1,3),(3,3,6),(1,2,4),(2,1,4),(4,4,4), za x,y,z večje od 4 se zgoraj ne sešteje in ne more biti rešitev, razen(3,3,6). Npr.\(\frac{1}{5}+\frac{1}{5}+\frac{2}{5}=\frac{4}{5}\), za vse večje se tudi ne bo seštelo v naravno število.
Je to prav rešeno?

2.naloga:
Imamo števila od 1,...,n. m je število števil, ki so tuja m, torej \(\phi(n)=m\) (Eulerjeva fja).
Napiši formulo za vsoto števil, ki so tuja n v odvisnosti od m in n. Po nekaj izračunih dobim flo:\(\sum\frac{nm}{2}\)
Je prav?

3.Naloga:
V posodi je n kroglic, od tega r rdečih, ostale so modre. Iz posode izvlečemo dve kroglici.
Določi diofantsko enačbo, ki ji ustrezata r in n, če veš, da je število možnosti,pri katerih izvlečemo kroglici iste barve, enako številu možnosti, pri katerih izvlečemo kroglici različne barve.
Koliko je v posodi rdečih kroglic, če je skupno število kroglic najmanjše možno?

Rešim tako:
Če želimo imeti iste barve: \(\frac{{r \choose 2}}{{n \choose 2}}=\frac{r(r-1)}{n(n-1)}+\frac{{n-r \choose 2}}{{n \choose 2}}=\frac{2r^2-2r-2rn+n+n^2}{n(n-1)}\)
Različni barvi: \(\frac{{r \choose 1}{n-r \choose 1}}{{n \choose 2}}=\frac{2r(n-r)}{n(n-1)}\)
Izenačimo: \(4r^2 -2r-4rn+n+n^2=0\)
\((2r-n)^2-(2r-n)=0\)
\((2r-n)(2r-n-1)=0\)
Iz tega dobimo: \(r=n/2\) in \(r=(n+1)/2\)

Je to prav?
Kako potem ven dobimo diofantsko enačbo in št. rdečih kroglic?

Prosim, če mi lahko kdo razloži, kaj je pri izračunih narobe, ker ne vidim, kje bi se lahko zmotila. Ali pa kakšen komentar,...

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

1)
Izgleda mi v redu. Mimogrede lahko se opazis, da je to naravno stevilo v najboljsem primeru (x=y=z=1) enako 4. Tako da lahko mogoce kaksen korak pohitris s tem.

2)
Kaksen je tvoj postopek?

3)
Saj to kar si dobila je diofantska enacba - isces celostevilske resitve nekega izraza z r in n. Sicer bi pa po moje lahko kar verjetnost za vlecenje razlicnih barv izenacila z 1/2.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

2.) Najprej sem zapisala po formuli: \(\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) ... (1-\frac{1}{p_k}))\) ne vidi se nič pametnega.
Potem sem šla gledat, kaj se dogaja:
\(\phi(2)=1\)
\(\phi(3)=2, 1+2=3\)
\(\phi(4)=2, 1+3=4\)
\(\phi(5)=4, 1+2+3+4=\)vseh je m=4, vidim, da jih lahko seštejem po parih, 1+4, 2+3, torej \(5*4/2=\frac{mn}{2}\), velja še \(\phi(n)=n-1=m,\), če je n praštevilo.
\(\phi(6)=1*2=2, 1+5=6*\frac{2}{2}\)
\(\phi(7)=6, 1+2+3+4+5+6\), spet isto seštevam prvega in zadnjega \(7*\frac{6}{2}=21\)
\(\phi(8)=4, 1+3+5+7\) tudi, če ni praštevilo se sešteje tako. Vsota je torej: \(\sum{}= n\frac{m}{2}\)
Je o.k?


3.) zakaj 1/2, kako potem določim število rdečih?

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Ja od vseh moznosti je 50/50 moznosti za razlicne in za enake :)
Potem pa je misljeno, da najdes resitev, ki ima najmanjsi mozen "n" in za to resitev podas r. Pa malo pazi, koliko moznosti je sploh v mesanem primeru.

2)
Hm... jaz tudi nimam kaksne boljse ideje... formula izgleda drzi, ni pa to dokaz. Teorije stevil nisem ravno vesc, tako da najbrz ne vidim kaksnih splosno znanih stvari.

Hm samo malo... razen ce... stevila, ki so n-ju tuja, so simetricno porazdeljena po intervalu od 0 do n: ce je k tuj n (gcd(k,n)=1), potem je tudi gcd(n-k,n)=1. Zato lahko pri vsoti grupiras nasprotne clene,
k+(n-k)=n, ki jih je m/2.

Odgovori