Teorija števil

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

Teorija števil

Odgovor Napisal/-a delta »

Lepo prosim, za pomoč pri nalogah. Nimam ideje, kako bi začela.
1.) Naj bo \(f:\mathbb{N}->\mathbb{N}\) definirana s formulo \(f(n)=\sum_{d|n}d^2\), \(f\) je multiplikativna. Izračunaj \(\sum_{d|n}f(d)\mu(\frac{n}{d})\). \(\mu\) je Mobiusova fja.
Dobim: \(\sum_{d|n}d^2 \mu{(\frac{n}{d})}\) kako naprej?
2.) Določi zadnji dve cifri števila \({11^{12}}^{13}\).
Gledamo po modulu 100. Vemo, da \(\phi(100)=40\), poskusim uporabiti Eulerjev izrek. Poskusim najti manjši a od 40, da bi veljalo \(11^{a}=1\) (mod 100), a je delitelj števila 40. Ne dobim nič uporabnega.
3.) Pokažite, da obstaja neskončno mnogo pitagorejskih trojk \((x,y,z)\) takšnih, da sta x in y zaporedni števili.
4.) Določite vsa naravna števila n, za katera je \(5^n+n^5\) deljivo s 13.
Kako se lotimo takšne enačbe, če je neznanka kot osnova in še v eksponentu?

Prosim, če ima kdo idejo, kako bi se lotila katere izmed nalog. lp :)

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

1) Nisem ravno ekspert ampak izgleda mi, da je tole ravno definicija Mobiusove inverzije. Prva enacba ti iz g(n)=n^2 naredi f(n)=sum g(d). Druga je pa ravno formula, ki ti iz f(n) naredi nazaj g(n).

2) Res ti koristi Eulerjev teorem: 11 in 100 sta tuji stevili, zato velja \(11^{\varphi(100)}=1\mod 100\) Zato lahko vse veckratnike \(\varphi(100)=40\) iz eksponenta odstranis in dobis, da je
\(11^{12^{13}}=11^{12^{13}\mod 40}\mod 100\)
Kjer je eksponent zdaj neka normalna stevilka manjsa od 40, namesto nekaj ogromnega. V eksponentu zdaj lahko malo transformiras (12 in 40 imata skupni delitelj) in spet uporabis podoben postopek.

3) Hm...

4) Mogoce si lahko pomagas s tem, da \(5^n\mod 13\) lahko zavzame samo vrednosti a=1,5,12,8. Potem lahko samo za vsako izmed teh vrednosti resis enacbo \(a+n^5=0\mod 13\), ki ima n samo se v osnovi.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Najlepša hvala za pomoč, vendar še kar precej stvari nisem ugotovila. Lepo prosim še za malo pomoči.
1.)
Aniviller napisal/-a:Druga je pa ravno formula, ki ti iz f(n) naredi nazaj g(n)
,tega ne vidim ravno. Kaj dobimo \(\sum_{d|n}f(d)\mu({\frac{n}{d}})\), kako razpišemo \(\mu({\frac{n}{d}})\)?

2.)
Aniviller napisal/-a:lahko malo transformiras (12 in 40 imata skupni delitelj)
kako naj tranformiram, vem, da Eulerjevega izreka ne smem uporabiti, ker 12 in 40 nista tuja, samo kako naj preoblikujem eksponent? :?

4.) Kako ugotovimo:
Aniviller napisal/-a:a=1,5,12,8
Kako se potem lotimo dobljene enačbe? Hm

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

1)
Definicija Mobiusove inverzije je, da lahko vsoto
\(f(n)=\sum_{d|n}g(d)=\sum_{d|n} d^2\)
obrnes takole:
\(g(n)=\sum_{d|n}\mu(\tfrac{n}{d})f(d)=n^2\)
Sploh ni treba nic razpisat, ker je zapisan izraz ze definicija Mobiusove inverzije in dvojne vsote ni treba racunat.

2)
Eksponent posebej:
\(12^{13}=x\mod 40\)
\(8\cdot 3\cdot 6 \cdot 12^{11}=x\mod 40\)
To sem naredil, ker je 8 najvecji skupni delitelj leve strani in modula 40. S tem ves, da je itak x tudi veckratnik stevila 8 in lahko pises x=8y in pokrajsas osmico:
\(3\cdot 6\cdot 12^{11}=y\mod 5\)
Ker po modulu 5 velja 6=1 in 12=2, dobis takoj
\(y=3\cdot 2^{11}\mod 5\)
potem pa se z Eulerjevim teoremom prides do y=4 in x=8y=32.

S tem prides do
\(11^{32}\mod 100\)
kjer pa lahko parkrat dvojko noter neses, 11^(2*16)=121^16=21^16=441^8=41^8=... ali pa uporabis kak drug teorem, da ugotovis, da je v resnici ze \(11^{10}=1\mod 100\).

4) Ker imas itak periodicnost po 13 lahko zaradi majhne stevilke itak preveris vseh 12 moznosti. Drugace pa lahko se malo premeces:
\(n^5+1=0\mod 13\)
\(n^5=12\mod 13\)
Ker ves, da je \(n^{\phi(13)}=n^{12}=1 \mod 13\), lahko poskusis enacbo potencirat tako, da bo na levi ostal samo n.

Rabis dat na tako potenco, da bo v eksponentu 5*p=1 mod 12, torej isces multiplikativni inverz 5 po 12. To je trivialno, ker ves, da je multiplikativni inverz kar \(5^{\varphi(12)-1}=5^{3}=5\), ocitno je kar sam sebi inverz.

Torej je resitev
\(n=12^5\mod 13=12\).

Izbrskas lahko tudi teorem, da ima \(n^k=a\mod m\) resitve samo, ce je \(a^{\phi(m)/d)}=1\mod m\), \(d=\gcd(k,\phi(m))\). V tem primeru ima d resitev. To je zgolj posledica tega, da mora biti mogoce najti potenco, na katero das celo enacbo, da ostane na levi \(n^{1+t\cdot \phi(m)}=n\)

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Btw, pri n^5+1=0 sem nesel na drugo stran in -1 pretvoril v 12. V bistvu je boljse da obdrzis -1, ker je potem ocitno, da je (-1)^5=-1.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

1.) aha :) , ja sedaj razumem, nisem vedela kaj je Mobiusova inverzija
2.) super :) vse jasno, hvala
4.) am,
Aniviller napisal/-a: preveris vseh 12 moznosti
kako to preverjaš? za n vstavljamo samo, kako vemo, da smo našli vse ostanke pri delj. s 13?

Od tukaj naprej ne vem, kako. Kako smo pri tem uporabili omenjeni teorem?
Aniviller napisal/-a:Torej je resitev
n=12^5\mod 13=12.

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

4) No preveris lahko samo v tem delno resenem problemu, ko smo "a" izbrali da je fiksen. Ce je n resi enacbo \(n^5+a=0\mod 13\), potem jo resi tudi vsak n+13k za vsak celi k. Tako resitve za vsak a podajo celo druzino resitev. Zato lahko preveris samo za n=0 do 12 (z vstavljanjem pogledas ce se izide).

Ce stevila od 0 do 12 vstavis v \(n^5 \mod 13\), dobis
0 1 6 9 10 5 2 11 8 3 4 7 12

enacbo \(n^5+a=0\mod 13\) torej resijo:
a=1 -> n=12+13*k
a=5 -> n=8+13*k
a=12 -> n=1+13*k
a=8 -> n=5+13*k

Zdaj se je pa treba spomnit, da smo na zacetku samo rekli, da je a = 5^n mod 13, kar je lahko zavzelo le vrednosti 1,5,12,8. Torej se nismo zakljucili! Imamo namrec v bistvu sistem enacb za a in n, resili smo eno, zdaj je treba pa se drugo. V tem primeru resitve niso periodicne po n-ju na 13, ampak na vsaj 12 (Eulerjev izrek), ker je zdaj n v eksponentu namesto v osnovi! Se vedno lahko kar preveris vseh 12, kar smo v bistvu ze naredili. Za n-je po vrsti od 0 naprej, velja 5^n mod 13=
1 5 12 8 1 5 12 8 1 5 12 8 ...
V resnici je torej periodicno celo na 4, ne na 12.

Torej imamo resitve
a=1 -> n=4*m
a=5 -> n=1+4*m
a=12 -> n=2+4*m
a=8 -> n=3+4*m

Zdaj se ti je pa sistem zreduciral na resevanje diofantskih enacb. Za a=1 moras resit
n=4*m=12+13*k
in tako naprej.... s tem res dobis potem vse moznosti za n.

Lahko da tale postopek ni idealen in da sem spregledal kaj ocitnega, moje primarno podrocje ni teorije stevil, poznam jo samo bezno. Bom se razmislil in ce se spomnim kaj boljsega bom napisal.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

4.) Najlepša hvala za razlago, mi je že bolj jasno, samo ne vem točno, kako smo dobili:
Aniviller napisal/-a:a=1 -> n=12+13*k
a=5 -> n=8+13*k
a=12 -> n=1+13*k
a=8 -> n=5+13*k
Vprašala bi še nekaj pri drugih nalogah, če ima kdo kakšno idejo, bi bila zelo dobrodošla :)
5.) Določite dve pozitivni rešitvi Pellove enačbe \(x^2-18y^2=1\) Zakaj Pellova enačba \(x^2-18y^2=-1\) nima rešitev?
Prvi del sem rešila tako, da najprej izr. verižni ulomek za \(\sqrt{18}\), dobim \(\sqrt{18}=[4;4,8]\), perioda je soda, zato je najmanjša rešitev \(x_1=17, y_1=4\) in \(x_2=577, y_2=136\) po formuli \(x_n+y_n=(x_1+y_1)^n\). Ali je to vredu?
Drugi del naloge ne vem kako naj se lotim.?

6.) Prikažite \(\sqrt{n^2-1}\) kot neskončni verižni ulomek in rešite Pellovo enačbo \(x^2-(n^2-1)y^2=\pm 1\)
Rešujem podobno kot, če so števila, je to vredu?

Pitagorejske trojke:
7.) Določite vse primitivne rešitve Diofantske enačbe \(x^2+y^2 = 71^2\). (Pitagorejska trojka)
Za primitivne pitagorejske trojke vemo: \(x=m^2-n^2\),\(y=2mn\), \(z=m^2+n^2\), vemo še da je ntk. ena izmed x,y sodo število. Kako naj si pri reševanju pomagam le s tem? Kako bi to dala v Mathematico?(z Reduce ne zna)
8.) Naj bo \((x,y,z)\) prim. pit. trojka. Dokažite, da je \(xy\) deljivo z 12 in da je xyz deljivo s 60. Kako bi začela?
Lepo prosim za pomoč, lp :)

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

delta napisal/-a:4.) Najlepša hvala za razlago, mi je že bolj jasno, samo ne vem točno, kako smo dobili:
Aniviller napisal/-a:a=1 -> n=12+13*k
a=5 -> n=8+13*k
a=12 -> n=1+13*k
a=8 -> n=5+13*k
To je le alternativni zapis resitev enacbe \(n^5+a=0 \mod 13\). Vemo, da je itak periodicno na 13, vrednosti za n, ki resijo enacbo, pa lahko dobimo enostavno z vstavljanjem. Ce vstavis n=0, dobis \(a=0\mod 13\), kar ni med moznimi a-ji. Ce vstavis n=1, dobis \(1+a=0\mod 13\), kar ustreza a=12. In tako naprej... Isto enacbo lahko resis enostavno tako, da n^5 potenciras tako, da dobis n*n^fi(13).

S Pellovo enacbo se nisem delal, vem toliko kot sem zdajle prebral :)

7) Ocitno resujemo enacbo \(m^2+n^2=71\). 71 je liho prastevilo. Po Fermatovem teoremu o vsoti kvadratov vemo, da se liho prastevilo da razcepit na vsoto kvadratov le, ce je \(71=1\mod 4\), kar ni res, torej resitev ni.

8 ) Tukaj gres lahko popolnoma direktno.
\(xy=(m-n)(m+n)2mn=2n(m-n)m(m+n)\)
Z dve je ocitno deljivo. Po drugi strani je m>n in eden izmed m in n je sod. Torej so faktorji (m-n),m,(m+n) izmenicno lihi in sodi in je vsaj eden izmed njih sod, torej je celotno stevilo delivo vsaj s 4.
Deljivost s 3 dokazes lahko kar tako, da izcrpas vse moznosti.
m in n imata lahko katerokoli kombinacijo ostankov po deljenju s 3. Faktorjev imas dovolj, da bo vsaj eden deljiv s 3:
* Ce je m=0 mod 3 ali n=0 mod 3, je itak cela stvar deljiva s 3.
* Ce je m=n mod 3 (ostanka sta enaka), potem je m-n deljiv s 3.
* S tem smo porabili ostanke (0,0),(0,1),(0,2),(1,0),(2,0),(1,1),(2,2). Ostane le se (1,2) in (2,1), pri cemer pa je vsota ostankov deljiva s 3: m+n=0 mod 3.

Za xyz moras pa dokazat se deljivost s 5. Tu lahko tudi enostavno izcrpas vse moznosti. Iz xy clenov takoj pokazes na isti nacin, da je deljivo, ce je res karkoli od tega
\(m=0\mod 5\)
\(n=0\mod 5\)
\(m=n\mod 5\)
\(m+n=0\mod 5\)
Preostanejo se pari ostankov(m,n): (1,2),(1,3),(2,1),(3,1),(4,2),(4,3),(2,4),(3,4). Za te lahko magari rocno preveris, da je n^2+m^2=0 mod 5. Lahko pa tudi tistega, ki je sod (recimo m) zapises m=2q, malo premeces in dobis
\(n^2-q^2=0 mod 5\) za lihi tuji stevili n in q, ki nista deljivi s 5. To je res, ce je n=q mod 5 ali n=-q mod 5. Prvi primer je ekvivalenten trditvi, da je \(2n=m \mod 5\), kar pokrije primere (1,3),(2,1),(4,2),(3,4). Drugi primer pa pravi \(2n=-m\mod 5\), kar pokrije ostale 4 primere.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

4.) Aha :) hvala. Zdaj vidim, kaj smo naredili, nečesa pa še ne razumem
Aniviller napisal/-a:Isto enacbo lahko resis enostavno tako, da n^5 potenciras tako, da dobis n*n^fi(13).
zakaj na levi strani hočemo imeti n? hm

7.) :) super :D , sedaj sem se lotila podobne naloge, kjer pa rešitve obstajajo
7b.) \(x^2+y^2=1201^2\) vidim, da je to tudi liho praštevilo, velja pa \(1201=1(mod 4)\), imamo \(m^2+n^2=1201\), vemo še, da je ntk. eno izmed m,n sodo. Recimo, da m sodo \(m=2k\), \(n=2l+1\), dobim \(4k^2+4l^2+4l+1=1201\). Kako bi se to rešilo dalje?
Ali pa če je kaj lažja naloga \(x^2+y^2=317^2\)

8.) vse jasno :) , hvala

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

delta napisal/-a:4.) Aha :) hvala. Zdaj vidim, kaj smo naredili, nečesa pa še ne razumem
Aniviller napisal/-a:Isto enacbo lahko resis enostavno tako, da n^5 potenciras tako, da dobis n*n^fi(13).
zakaj na levi strani hočemo imeti n? hm
Ker ga iscemo :) Ti imas a-je in hoces n-je. Ce noces s poskusanjem vseh 13 n-jev, gres lahko tako, da ga izrazis v obliki n=nekaj.
7b.) x^2+y^2=1201^2 vidim, da je to tudi liho praštevilo, velja pa 1201=1(mod 4), imamo m^2+n^2=1201, vemo še, da je ntk. eno izmed m,n sodo. Recimo, da m sodo m=2k, n=2l+1, dobim 4k^2+4l^2+4l+1=1201. Kako bi se to rešilo dalje?
Ali pa če je kaj lažja naloga x^2+y^2=317^2
Hm ja dokaz da lahko prastevilo razbijes na vsoto kvadratov se ne pomeni da znas to ucinkovito narest :) Vsaj jaz ne vem nekega enostavnega algoritma razen preverjanja vseh moznosti. Kot si opazila seveda lahko se malo poenostavis, ker ves da je en sod in en lih
4k^2+4l^2+4l+1=1201
4k^2+4l^2+4l=1200
k^2+l(l+1)=300
l(l+1) je sod, torej je k^2 sod, torej je k=2q.
4q^2+l(l+1)=300
Vidimo, da je l(l+1) sigurno deljiv s 4.
l(l+1)=4(75-q^2)
Tukaj se da pa ze prakticno rocno preverit vse q, ki so manjsi od korena iz 75.

Najbrz obstaja lepsi nacin, ampak tudi takole se pride skozi :)

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Potrebovala bi še malo pomoči.

7c.) Poiščite vse pit. trikotnike, katerih dolžine stranic so tuja si števila, ena izmed katet je 15.
Rešim na podoben način kot prejšnje. Dobim:
\(x=m^2-n^2=15\),
\(m=2k, n=2l+1\),
\(k^2-l(l+1)=4\), torej bo k sodo \(k=2q\)
\(l(l+1)=4(q^2-1)\)

Grem preverit na roke:
\(q=2: l(l+1)=12 => l=2\)
\(q=3: l(l+1)=32\) ni o.k.
\(q=4: l(l+1)=60\) ni o.k.
...
V prejšnjih primerih je bilo tako, da je z naraščanjem q vrednost na desni padala, tu se to ne zgodi, ker je kateta. Vpr.: kako najdemo vse rešitve?

9.) Poišči vsa cela števila n, za katera \(5|3(n^2+n)+7\)
Izračunam:
\(3(n^2+n)+7=3(n^2+n)+2(mod 5)\), zato
\(n(n+1)=1+5k\), k mora biti liho \(k=2q+1\)
\(n(n+1)=2(5q+3)\)
podobno notri vstavljam različne q:
za q=0 se izide, kako najdemo VSE rešitve? hm

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

7c) ja s te strani je zoprno ker imas minus tam. Ampak po drugi stani ti pa minus omogoca, da razstavis na produkt!
(m-n)(m+n)=15
15 lahko razcepis samo na 2 nacina: 1*15 in 5*3. Imas torej sisteme linearnih enacb za vsako moznost. Ker je m+n > m-n, imas 2 moznosti.
m+n=15, m-n=1. Ce sestejes enacbi, dobis m=8 in s tem n=7.
m+n=5, m-n=3. m=4,n=1.

Trojici sta torej
m=8, n=7 -> x=15, y=112, z=113
m=4, n=1 -> x=15, y=8, z=17

9) Enacba
\(n(n+1)=1\mod 5\)
ima itak resitve periodicne na 5. Ce najdes n med 0 in 4, ki resi enacbo, so tudi n+5k resitve. Samo 1,2,3,4 moras preverit. Hitro vidis, da je resitev n=2 in s tem tudi 7,12,...

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

Re: Teorija števil

Odgovor Napisal/-a delta »

7c.) in 9.) vse jasno :) hvala
Vprašala bi še nekaj, kako bi dala Mathematici za izračunat kongruenco: \(4x=1(mod 26)\), ne uspe mi jo izračunat.
Zadnjič spremenil delta, dne 4.8.2012 14:55, skupaj popravljeno 1 krat.

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

4x=1 mod 26 nima resitev, ker je levi del vedno sod, desni pa vedno lih. Kongruence so obnasajo drugace, ce imata faktor in modul skupni delitelj. V tem primeru lahko bodisi pokrajsas, ce se da, (ax=ay mod ab lahko spremenis v x=y mod b), ali pa ni resitev, ce se ne da.

Z Mathematico nisem nikoli delal teorije stevil tako da ne poznam ustreznih funkcij.

Odgovori