Teorija števil
Re: Teorija števil
Imam eno nalogo sicer je bolj povezana s teorijo, prosim za pomoč, ter obrazložite.
Funkcija je multiplikativna če je\(f(mn)=f(m)f(n)\) za vsaki tuji si števili \(m\) in \(n\), strogo multiplikativna pa če je \(f(mn)=f(m)f(n)\) \(\forall x \in \mathbf{N}\) .
NALOGA:
Naj bo \(f(n)=\sum_{d|n} d^3\).Pokaži da je multiplikativna. Ali je strogo multiplikativna?
Hvala
Funkcija je multiplikativna če je\(f(mn)=f(m)f(n)\) za vsaki tuji si števili \(m\) in \(n\), strogo multiplikativna pa če je \(f(mn)=f(m)f(n)\) \(\forall x \in \mathbf{N}\) .
NALOGA:
Naj bo \(f(n)=\sum_{d|n} d^3\).Pokaži da je multiplikativna. Ali je strogo multiplikativna?
Hvala
Re: Teorija števil
To lahko direktno poračunaš. Za tuji števili m in n imaš f(n) in f(m)... ker sta n in m tuji, so delitelji mn vsi možni produkti deliteljev n in m. Torej vsota teče po
\(\sum_{d|nm}=\sum_{d_n d_m|nm}=\sum_{d_n|n}\sum_{d_m|m}\)
in vsota potem postane
\(\sum_{d_n|n}\sum_{d_m|m} d_n^3 d_m^3\)
in to lahko zdaj separiraš na produkt posamičnih vsot.
Za netuji števili pa to najbrž ne bo šlo, ker vsote ne moreš separirat (delitelji niso produkti posameznih deliteljev, ker se eni ponavljajo).
\(\sum_{d|nm}=\sum_{d_n d_m|nm}=\sum_{d_n|n}\sum_{d_m|m}\)
in vsota potem postane
\(\sum_{d_n|n}\sum_{d_m|m} d_n^3 d_m^3\)
in to lahko zdaj separiraš na produkt posamičnih vsot.
Za netuji števili pa to najbrž ne bo šlo, ker vsote ne moreš separirat (delitelji niso produkti posameznih deliteljev, ker se eni ponavljajo).
Re: Teorija števil
Poišči vse naravne rešitve enačb:
\(5x+3y=52\) in
\(123x+57y=531\)
Na tekmovanju iz matematike je bilo 140 dijakov. Organizator je za vsakega pripravil en sok. Sokovi so bili v paketih po 16,17, 40 steklenic. Koliko je bilo posameznih paketov? iz tega napišem enačbo: \(16x+17y+40z=140\) kako bi to rešili?
\(5x+3y=52\) in
\(123x+57y=531\)
Na tekmovanju iz matematike je bilo 140 dijakov. Organizator je za vsakega pripravil en sok. Sokovi so bili v paketih po 16,17, 40 steklenic. Koliko je bilo posameznih paketov? iz tega napišem enačbo: \(16x+17y+40z=140\) kako bi to rešili?
Re: Teorija števil
To so navadne linearne diofantske enačbe. Eden izmed načinov je recimo tole:
Enačbo reduciraš po modulu 5:
3y=2 (mod 5)
y=4+5k
vstaviš nazaj
5x=52-3y=40-15k
x=8-3k
S tem imaš vse pare (x,y) za vsak k.
Lahko greš pa tudi s tistim Evklidovim algoritmom (kar je isto v drugi preobleki).
Tista zadnja ima 3... recimo če reduciraš na 17:
16x+6z=4 (mod 17)
Enega si izbereš za parameter (recimo x), in izrazis... mnozim enacbo s 3:
z=12-14x (mod 17) = 12 - 14x+17k
in potem vstavis nazaj da dobis se y:
17y=140-16x-40z=-340+544x-40*17k
y=-20+32x-40k
To so vse celoštevilske rešitve (za poljubna x in k). Zdaj pa moraš uporabit še pogoj pozitivnosti za x,y,z. Pri z-ju to pride
0<=12-14x+17k
k>=14/17 x-12/17
po y pa
k<=4/5 x-1/2
Interval uporabnih k mora biti neničeln, torej mora biti spodnja meja manjša od zgornje:
14/17 x-12/17<4/5 x-1/2
140 x-120<136 x-85
4x<35
x<=8
Upam da nisem prehitro racunal in kaj zasral.
Zdaj lahko najbrž za vsak x probaš če interval po k sploh vsebuje kakšno celo število. Hiter račun ti da tabelo za intervale
x kmin kmax
0 -0.705882 -0.5
1 0.117647 0.3
2 0.941176 1.1
3 1.76471 1.9
4 2.58824 2.7
5 3.41176 3.5
6 4.23529 4.3
7 5.05882 5.1
8 5.88235 5.9
Samo v primeru x=2 imaš v intervalu celo število, in to k=1. Rešitev je torej
x=2, y=4, z=1
Sicer pojma nimam kako bi se to v resnici rešilo, to je nekaj na pamet
Enačbo reduciraš po modulu 5:
3y=2 (mod 5)
y=4+5k
vstaviš nazaj
5x=52-3y=40-15k
x=8-3k
S tem imaš vse pare (x,y) za vsak k.
Lahko greš pa tudi s tistim Evklidovim algoritmom (kar je isto v drugi preobleki).
Tista zadnja ima 3... recimo če reduciraš na 17:
16x+6z=4 (mod 17)
Enega si izbereš za parameter (recimo x), in izrazis... mnozim enacbo s 3:
z=12-14x (mod 17) = 12 - 14x+17k
in potem vstavis nazaj da dobis se y:
17y=140-16x-40z=-340+544x-40*17k
y=-20+32x-40k
To so vse celoštevilske rešitve (za poljubna x in k). Zdaj pa moraš uporabit še pogoj pozitivnosti za x,y,z. Pri z-ju to pride
0<=12-14x+17k
k>=14/17 x-12/17
po y pa
k<=4/5 x-1/2
Interval uporabnih k mora biti neničeln, torej mora biti spodnja meja manjša od zgornje:
14/17 x-12/17<4/5 x-1/2
140 x-120<136 x-85
4x<35
x<=8
Upam da nisem prehitro racunal in kaj zasral.
Zdaj lahko najbrž za vsak x probaš če interval po k sploh vsebuje kakšno celo število. Hiter račun ti da tabelo za intervale
x kmin kmax
0 -0.705882 -0.5
1 0.117647 0.3
2 0.941176 1.1
3 1.76471 1.9
4 2.58824 2.7
5 3.41176 3.5
6 4.23529 4.3
7 5.05882 5.1
8 5.88235 5.9
Samo v primeru x=2 imaš v intervalu celo število, in to k=1. Rešitev je torej
x=2, y=4, z=1
Sicer pojma nimam kako bi se to v resnici rešilo, to je nekaj na pamet
Re: Teorija števil
Zanima me, kako bi se rešilo naslednji dve nalogi:
1. Izrazite \(\sum_{k=1}^n \frac{1}{k(k+1)}\) z \(n\).
2. \(a>0\), velja \(a^{\frac{1}{2}}+a^{-\frac{1}{2}}=3\), izračunaj \(a-a^{-1}\).
1. Izrazite \(\sum_{k=1}^n \frac{1}{k(k+1)}\) z \(n\).
2. \(a>0\), velja \(a^{\frac{1}{2}}+a^{-\frac{1}{2}}=3\), izračunaj \(a-a^{-1}\).
Re: Teorija števil
1. Parcialni ulomki,
\(\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}\)
ko sešteješ, se vse vmes pokrajša, razen
\(=1-\frac{1}{n+1}\)
2. No tudi če nimaš drugih idej, lahko kar a izraziš (nova spremenljivka za sqrt(a) in rešiš kvadratno enačbo).
\(\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}\)
ko sešteješ, se vse vmes pokrajša, razen
\(=1-\frac{1}{n+1}\)
2. No tudi če nimaš drugih idej, lahko kar a izraziš (nova spremenljivka za sqrt(a) in rešiš kvadratno enačbo).
Re: Teorija števil
Pokaži, da za vsako naravno število \(n \in \mathbb{N}\) obstaja število z \(n\) lihimi ciframi, ki je deljivo s \(5^n\).
Zapisali smo:
\(5^1|5\)
\(5^2|75\)
\(5^3|375\)
\(5^4|?375\)
V zadnji vrstici mi ni jasno, kako lahko najdemo tako štirimestno število, saj je \(5^4=5625\) in tega števila ne bi mogli 'stlačiti' v npr. 9375.? Kdo ve kaj tu ni vredu?
Zapisali smo:
\(5^1|5\)
\(5^2|75\)
\(5^3|375\)
\(5^4|?375\)
V zadnji vrstici mi ni jasno, kako lahko najdemo tako štirimestno število, saj je \(5^4=5625\) in tega števila ne bi mogli 'stlačiti' v npr. 9375.? Kdo ve kaj tu ni vredu?
Re: Teorija števil
No pa saj 9375=15*5^4. Sicer pa mislim, da je mišljeno, da imaš n lihih cifer in poljubno število sodih. Za n=5 namreč že ni 5-mestne rešitve.
Re: Teorija števil
Zmotila sem se \(5^4=625\), mislim, da naj bi bilo število sestavljeno samo iz lihih števil. Za \(5^5\) sem našla rešitev: \(5^5*19=59375\).
Re: Teorija števil
No to vem da si se zmotil, to ni panike. Ja, ne vem kako mi je ratalo tole spregledat. Sem si zgeneriral vse, pa sem ga spregledal...
No, potem bo najbrž treba s popolno indukcijo ali kaj takega.
Takole bi jaz počasi gradil rešitev. Lahko bi splošno napadal (recimo hitro ugotoviš, da se mora število končat s 75, veš, da mora biti stvar oblike 5^n*(4m+3) in podobno). Ampak, če je res, da se prejšnje števke samo ponovijo, in dodaš eno novo, bo pa dosti lažje. Če veš nastavek, ga moraš samo še dokazat. Torej, iščeš rešitev \(x_n\), pod predpostavko, da že poznaš \(x_{n-1}\), ki ima željeno lastnost. Zapisat hočeš v obliki
\(x_n=a\cdot 10^{n-1} +x_{n-1}\)
z lihim a<10, ki je naslednja števka. Ostanek po deljenju s 5^(n-1) je zagotovljen (po indukcijski predpostavki):
\(x_n/5^{n-1}=a\cdot 2^{n-1}+\underbrace{(x_{n-1}/5^{n-1})}_q\)
Ta stvar mora biti deljiva s 5 še enkrat. Iščeš torej \(a\in \{1,3,5,7,9\}\), ki zagotovi
\(a\cdot 2^{n-1}+q=0\mod 5\)
Ker sta 2 in 5 tuji števili, ima to vedno rešitev (in to enolično po modulu 5). Ker so števila 1,3,5,7,9 po modulu 5 enaka {1,3,0,2,4}, lahko vedno najdemo tudi enolično enomestno liho rešitev. To je kot dokaz že dovolj, še lepše je pa, če jo kar izračunaš. Po Eulerjevem izreku je 2^4=1 (mod 5), zato lahko enačbo množiš z 2^(1-n mod 4), in pride
\(a=-q\cdot 2^{1-n \mod 4} \mod 5\)
Recimo, če računaš za n=4, velja q=375/5^3=3 in 1-n mod 4 = -3 mod 4=1, torej
\(a=-3\cdot 2 \mod 5 = -6 \mod 5 = 4 \mod 5\)
kar je med lihimi enomestnimi števili a=9.
Naslednji korak
n=5, q=9375/5^4=15 (je 0 po modulu 5), torej sploh ni kaj računat, saj je
\(a=0\mod 5\)
kar je med lihimi enomestnimi števili a=5.
Naslednji
n=6, q=59375/5^5=19, 1-n mod 4 = -5 mod 4 = 3, torej
\(a=-19\cdot 2^3 \mod 5 = 1\cdot 8 \mod 5 = 3\mod 5\)
kar je med lihimi enomestnimi a=3.
n=7, q=359375/5^6=23, 1-n mod 4 = -6 mod 4 = 2, zato
\(a=-23 \cdot 2^2 \mod 5 = 2 \cdot 4 \mod 5 = 8\mod 5 = 3\mod 5\)
kar je spet a=3.
n=8, q=3359375/5^7=43, 1-n mod 4 = -7 mod 4 = 1,
\(a=-43\cdot 2 \mod 5 = 2 \cdot 2 \mod 5 = 4 \mod 5\)
in a=9.
In tako naprej.
No, potem bo najbrž treba s popolno indukcijo ali kaj takega.
Takole bi jaz počasi gradil rešitev. Lahko bi splošno napadal (recimo hitro ugotoviš, da se mora število končat s 75, veš, da mora biti stvar oblike 5^n*(4m+3) in podobno). Ampak, če je res, da se prejšnje števke samo ponovijo, in dodaš eno novo, bo pa dosti lažje. Če veš nastavek, ga moraš samo še dokazat. Torej, iščeš rešitev \(x_n\), pod predpostavko, da že poznaš \(x_{n-1}\), ki ima željeno lastnost. Zapisat hočeš v obliki
\(x_n=a\cdot 10^{n-1} +x_{n-1}\)
z lihim a<10, ki je naslednja števka. Ostanek po deljenju s 5^(n-1) je zagotovljen (po indukcijski predpostavki):
\(x_n/5^{n-1}=a\cdot 2^{n-1}+\underbrace{(x_{n-1}/5^{n-1})}_q\)
Ta stvar mora biti deljiva s 5 še enkrat. Iščeš torej \(a\in \{1,3,5,7,9\}\), ki zagotovi
\(a\cdot 2^{n-1}+q=0\mod 5\)
Ker sta 2 in 5 tuji števili, ima to vedno rešitev (in to enolično po modulu 5). Ker so števila 1,3,5,7,9 po modulu 5 enaka {1,3,0,2,4}, lahko vedno najdemo tudi enolično enomestno liho rešitev. To je kot dokaz že dovolj, še lepše je pa, če jo kar izračunaš. Po Eulerjevem izreku je 2^4=1 (mod 5), zato lahko enačbo množiš z 2^(1-n mod 4), in pride
\(a=-q\cdot 2^{1-n \mod 4} \mod 5\)
Recimo, če računaš za n=4, velja q=375/5^3=3 in 1-n mod 4 = -3 mod 4=1, torej
\(a=-3\cdot 2 \mod 5 = -6 \mod 5 = 4 \mod 5\)
kar je med lihimi enomestnimi števili a=9.
Naslednji korak
n=5, q=9375/5^4=15 (je 0 po modulu 5), torej sploh ni kaj računat, saj je
\(a=0\mod 5\)
kar je med lihimi enomestnimi števili a=5.
Naslednji
n=6, q=59375/5^5=19, 1-n mod 4 = -5 mod 4 = 3, torej
\(a=-19\cdot 2^3 \mod 5 = 1\cdot 8 \mod 5 = 3\mod 5\)
kar je med lihimi enomestnimi a=3.
n=7, q=359375/5^6=23, 1-n mod 4 = -6 mod 4 = 2, zato
\(a=-23 \cdot 2^2 \mod 5 = 2 \cdot 4 \mod 5 = 8\mod 5 = 3\mod 5\)
kar je spet a=3.
n=8, q=3359375/5^7=43, 1-n mod 4 = -7 mod 4 = 1,
\(a=-43\cdot 2 \mod 5 = 2 \cdot 2 \mod 5 = 4 \mod 5\)
in a=9.
In tako naprej.
Re: Teorija števil
Zgornje razumem, hvala. Kakšna ideja, kako bi rešili \(\zeta(s)=\sum_{k=1}^\infty \frac{\tau(k)}{k^s}\),
ali \(\frac{1}{\zeta(s)}=\sum_{k=1}^\infty \frac{\mu(k)}{k^s}\)
vemo še :\(\zeta(s)=\Pi_{p \in P}(1-\frac{1}{p^s})^{-1}\). \(\tau\) je število deliteljev \(k\).
ali \(\frac{1}{\zeta(s)}=\sum_{k=1}^\infty \frac{\mu(k)}{k^s}\)
vemo še :\(\zeta(s)=\Pi_{p \in P}(1-\frac{1}{p^s})^{-1}\). \(\tau\) je število deliteljev \(k\).
Re: Teorija števil
Hm... kako to misliš "rešili"? To so pač Dirichletove vrste za tri različne potence zeta funkcije (en kvadrat ti manjka), povezane so pa z Dirichletovo konvolucijo. Če misliš govorit o dokazih, ne vem kaj hočeš predpostavit kot znano. Te stvari lahko smatraš tudi kot definicije danih funkcij.
Re: Teorija števil
Ja, dokaz tega je treba naredit(ne rešit). Sem razpisala, pa se nič ne vidi...
Re: Teorija števil
1/zeta imaš na srečo že razpisano kot produkt... poskusiš skupaj pobrat vse člene z istim imenovalcem. Če pogledaš
\(\prod (1-\frac{1}{p^s})\)
vidiš, da ko zmnožiš, dobiš v različnih členih spodaj produkte poljubnega števila praštevil, vendar vsakega največ enkrat! Tako da to ti takoj pove, da členi, ki imajo faktorje na večjo potenco od 1, ne bodo nastopali v vsoti. Ker vsak faktor -1/p^s pridela en minus, bodo členi z lihim številom prafaktorjem imeli minus, ostali pa plus. V tem pa že vidiš definicijo Mobiusove funkcije.
Za kvadriranje bi šel pa raje s kvadriranjem vrste, ne produkta. Ko kvadriraš \(\sum \frac{1}{k^s}\), dobiš v imenovalcih vse možne produkte parov naravnih števil. Vsako število se v vsoti pojavi tolikokrat, na kolikor načinov ga lahko razbiješ na produkt dveh števil. V produktu \((\sum_k \frac{1}{k^s})(\sum_l\frac{1}{l^s})\) bo prišlo \(\frac{1}{n^s}\) kadar bo n=k*l, torej za vsak k, ki deli n (l je pa s tem določen), torej bo toliko členov, kot je število deliteljev.
\(\prod (1-\frac{1}{p^s})\)
vidiš, da ko zmnožiš, dobiš v različnih členih spodaj produkte poljubnega števila praštevil, vendar vsakega največ enkrat! Tako da to ti takoj pove, da členi, ki imajo faktorje na večjo potenco od 1, ne bodo nastopali v vsoti. Ker vsak faktor -1/p^s pridela en minus, bodo členi z lihim številom prafaktorjem imeli minus, ostali pa plus. V tem pa že vidiš definicijo Mobiusove funkcije.
Za kvadriranje bi šel pa raje s kvadriranjem vrste, ne produkta. Ko kvadriraš \(\sum \frac{1}{k^s}\), dobiš v imenovalcih vse možne produkte parov naravnih števil. Vsako število se v vsoti pojavi tolikokrat, na kolikor načinov ga lahko razbiješ na produkt dveh števil. V produktu \((\sum_k \frac{1}{k^s})(\sum_l\frac{1}{l^s})\) bo prišlo \(\frac{1}{n^s}\) kadar bo n=k*l, torej za vsak k, ki deli n (l je pa s tem določen), torej bo toliko členov, kot je število deliteljev.
Re: Teorija števil
juve napisal/-a:Pa še takle primer: določi najmanjše naravno št n>1 tako da bo \(\sqrt{\frac{1^2+2^2+...+n^2}{n}}\) naravno št... Nasvet je da problem reduciraš na reševanje pelove enačbe... hm
Spet sem pri tej nalogi. Zanima me ce se je kdo slucajno dokopal do rezultata, jaz dobim namrec kar velik n in malce dvomin da je pravilno.