Teorija števil

Ko tudi učitelj ne more pomagati...
Odgovori
Zajc
Prispevkov: 1099
Pridružen: 26.6.2008 19:15

Re: Teorija števil

Odgovor Napisal/-a Zajc »

337

juve
Prispevkov: 20
Pridružen: 23.11.2012 19:53

Re: Teorija števil

Odgovor Napisal/-a juve »

Juhej! :-) hvala!

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Joj ta enačba ima ful na redko rešitve - eksponentno (zarad geometrijske narave rešitev Pellove enačbe).
1,337,65521,12710881,2465845537,478361323441,92799630902161,18002650033695937,3492421306906109761,...
je pa fino, ker je v bistvu n=1 trivialna fundamentalna rešitev, iz katere potem dobiš vse ostale.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

1. Poišči vrednost števila \([1,3,5]\), kjer se 3 in 5 periodično ponavljata.
2. Poišči posplošen verižni ulomek za \(\sqrt{n^2+m}\), kjer je \(m \leq 2n\).
3. Če je rešljiva Pellova enačba \(x^2-dy^2=-1,\) pokaži, da morajo biti vsa praštevila, ki delijo \(d\) oblike \(4k+1.\)
4. Reši enačbo \(x^2-7y^2=2\).
Ali ima kdo kakšno idejo? :)

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

1. Zapiši decimalni del (brez enke) kot x=1/(3+1/(5+x)), rešitev je potem 1+x.
2. Recimo
\(x=n\sqrt{1+\frac{m}{n^2}}=n+n(\sqrt{1+\frac{m}{n^2}}-1)\)
\(=n+\frac{m/n}{\sqrt{1+\frac{m}{n^2}}+1}\)
\(=n+\frac{m}{x+n}\)
\(=n+\frac{m}{2n+\frac{m}{x+n}}\)
\(\displaystyle=n+\frac{m}{2n+\frac{m}{2n+\frac{m}{x+n}}}\)
3. To mislim da je na wiki od Pellove enačbe zelo blizu.
4. Uh. Kaj če bi rešil na desni z enko (Pell), in potem izbral pare (x,y), ki sta sodo-sodo in liho-liho, ti garantirano rešijo zgornjo enačbo. Ne vem pa, če s tem slučajno ne izpustiš česa.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

1. O.k.
2. ali posplošen verižni ulomek nima nujno 1 v števcih? kako ste dobili zadnji dve vrstici?
3. wiki na žalost ne pomaga :?
4. če izračunam rešitve Pellove enačbe \(x^2-7y^2=1\) dobim prvo rešitev \(x=8, y=3\), ki ne zadošča prvotni enačbi z 2 na koncu, saj nobena rešitev, ki ustreza \(x^2-7y^2=1\) ne bo ustrezala tudi \(x^2-7y^2=2\). Ne razumem, kako ste mislili da naj ven poberem prave.

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

2. Ne, zato je "posplošen". Samo vstavljal sem enačbo samo vase (x=...).
3. "The negative Pell's equation"
It has also been extensively studied; it can be solved by the same method of using continued fractions and will have solutions when the period of the continued fraction has odd length. However we do not know which roots have odd period lengths so we do not know when the negative Pell equation is solvable. But we can eliminate certain n since a necessary but not sufficient condition for solvability is that n is not divisible by a prime of form 4m+3. Thus, for example, x2-3py2 = -1 is never solvable, but x2-5py2 = -1 may be, such as when p = 1 or 13, though not when p = 41.
Torej, ne sme bit deljiv s praštevili oblike 4m+3, torej mora bit 4m+1 (4m+0 in 4m+2 pa nista praštevili, ker sta sodi). No samo to ni dokaz :)

Sicer to spomni na Fermatov izrek
http://en.wikipedia.org/wiki/Fermat%27s ... wo_squares
Če vzameš celo enačbo po modulu 4, lahko uporabiš to, da so vsi kvadrati naravnih števil po modulu 4 enaki 0 ali 1. Če je
d=1 mod 4, potem imaš
x^2-y^2=-1 mod 4
kar je izvedljivo, če je x=0 mod 4 in y=1 mod 4. Če je pa
d=-1 mod 4, pa imaš
x^2+y^2=-1 mod 4
kar pa ni možno, saj lahko dobiš samo 0+0, 0+1, 1+0 ali 1+1, nič od tega ni -1.

4. Aja pa res potem nobena izmed rešitev ne zadosti temu. Saj bi si lahko mislil... no pa saj wiki ima tudi na to rešitev. Kvadriraš jo, pa dobiš nazaj Pellovo.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

2. Aha, razumem, hvala :)
Ali je 3. sedaj na ta način že dokazana? ne razumem čisto,...Fermatov izrek govori o vsoti, ne o razliki dveh kvadratov, kako smo potem uporabili ta izrek?
4. kvadriram? ne vem, na desni moram dobiti 2, če kvadriram 1 ali -1 je to še vedno 1.

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

No rekel sem, da je sorodno Fermatovemu izreku. Potem sem pa ga vzel za inspiracijo dokazovanja. Tisto spodaj je pa ok dokaz. Po modulu 4 uporabiš dejstvo, da kvadrati zavzamejo samo dve možnosti, in da zato ne moreš izpolnit enačbe, če tisti predfaktor nima pravega ostanka pri deljenju.

4.
Tole je izpeljava
http://en.wikipedia.org/wiki/Pell_equat ... formations

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Hvala za zgornje, razumem :) . Imam pa nekaj težav pri naslednjih nalogah.
5. Pokaži, da je kub vsakega števila ene od oblik \(9k-1, 9k, 9k+1\).
6. Reši diofantsko enačbo: \(2x^2-5y^2=7.\)
7. Med naravnimi števili od 1 do \(n\) je \(m\) tujih proti \(n.\) Izračunaj vsoto vseh naravnih števil, manjših od \(n\), ki so tuja \(n\). Zapiši kot funkcijo \(m\) in \(n.\)
8. Poišči vse rešitve enačbe \(n^3+2n-3 ==0(mod 45)\).
Pri zadnji najprej razbijem na \(5 \cdot 3^2\), za \(5\) ni težko pogledat, dobim \(n==1(mod 5)\) in \(n==3(mod 5)\), kako pa za \(3^2\)?
Ima kdo kakšno idejo, bi bila zelo vesela :)

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

5. Točno isto kot to, da so kvadrati vsi 0 in 1 mod 9. Po modulu 9:
n mod 9:
0,1,2,3,4,5,6,7,8
n^3 mod 9:
0,1,8,0,1,8,0,1,8
Pri čemer je seveda 8=-1 mod 9
6. Huh. Probaš lahko sorodno (ampak najbrž ne enako) transformacijo kot za dvojko na desni. Nimam prakse s temi enačbami, tako da si res sproti zmišljujem postopke. Ampak recimo takoj spet vidiš, da je y lih (če daš enačbo mod 2), in da je x=1 ali -1 mod 5 (če daš enačbo mod 5). Mogoče lahko s tem dobiš namige kako transformirat. Bom še malo razmislil...
7. No m je kar phi(n) -- Eulerjeva phi funkcija. Po drugi strani pa takole: za vsak prafaktor p števila n, dobiš n/p števil, ki n-ju niso tuja. Vsota teh je p+2p+...n=p*(n/p)*(n/p+1)/2=n*(n/p+1)/2. Seveda moraš pazit, da ne dobiš podvojevanja: Za razcep na tuja prafaktorja n=p*q, šteješ p*q dvakrat, tako pri p-ju kot pri q-ju. Če ima samo dva prafaktorja p in q (n=p*q), potem lahko vsoto tujih zapišeš kot vsoto vseh minus vsoto netujih za vsak prafaktor, plus nazaj n:
n*(n+1)/2-n*(n/p+1)/2-n*(n/q+1)/2+n=n/2*(n-n/p-n/q+1)=n/2*n(1-1/p)(1-1/q)
Tukaj mogoče že zavohaš n*phi(n)/2. Lahko pa poskusiš dokazat rekurzivno - izfaktoriziraš prafaktorje enega po enega. Zdajle se mi ne da. Lahko, da je lažja rešitev, malo googlaj, meni se ne da, je pozno.
8. Ja to lahko razbiješ na sistem kongruenčnih enačb, kot imaš pisano. Zadostit moraš torej obema
\(n^3+2n-3=0\mod 5\)
\(n^3+2n-3=0\mod 9\)
Druga implicira \(n^3+2n-3=0\mod 3\), kar je pa res za vsak n (vidiš s faktorizacijo). To ti dosti pove o sistemu (polinom je vedno deljiv s 3). Torej se da trojko izpostavit in pokrajšat in to zreducira kongruenco z devetko na kongruenco s trojko.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Hvala. :)
5. Hm, za kube mi je jasno, samo za kvadrate jaz dobim: 0, 1, 4 in 7.
6. Mi je uspel rešit, najprej dobiš y=lih, potem x= sod in nato prideš v protislovje, ni rešitev
7. dobim \(m n/2\), je ok?
8. Hm, tega pa ne razumem. faktorizacija?, zakaj je polinom deljiv s 3?
4. sem ugotovila, da mi še ni čist jasno, kako uporabim transformacije pri reševanju enačbe

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

5. Za kvadrate sem imel v mislih tisto modulo 4, ne 9. To je tisto, ki je nastopalo pri dokazu za Pella z -1 na desni.
6. Super, pa res.
7. Ja.
8. No n^3+2n-3 je za vsak n deljivo s 3, ker je 0 po modulu 3. To ti da navdih za razstavit. Polinom lahko faktoriziraš na
n(n+1)(n-1)+3(n-1)
kar je očitno deljivo s 3. Potem lahko če ne drugega vzameš vsak primer posebej.
Napadamo enačbo, in želimo trojko pokrajšat iz kongruence:
n(n+1)(n-1)+3(n-1) = 0 mod 9
n=3k:
k(3k+1)(3k-1)+3k-1=0 mod 3
-k=1 mod 3
k=2 mod 3
n=3k+1:
(3k+1)(3k+2)k+3k=0 mod 3
2k=0 mod 3
k=0 mod 3
n=3k-1:
(3k-1)k(3k-2)+3k-2=0 mod 3
2k=2 mod 3
k=1 mod 3
Z drugimi besedami, n={1,2,6} mod 9, kar se seveda da ugotovit direktno s poskušanjem prvih devetih naravnih števil brez faktorizacije. S poskušanjem tudi prvo enačbo rešiš n={1,3} mod 5. Rešitev sistema enačb je pa potem na dlani. Rešitve prve enačbe so torej oblike
n={1,2,6}+k*9
kar po vstavljanju v drugo enačbo postane
n={1,2,1} + k*4 mod 5
kjer ima vsaka opcija na desni svojo rešitev. Če je bilo n=1+9k ali n=6+9k, potem je
n=1+4k mod 5,
kar se ujema z n=1 mod 5 kadar je k=0 mod 5, ter z n=3 mod 5 kadar je k=3 mod 5. To ti da rešitve
n=1,6,28,33 mod 45
Varianta n=2+9k ti da pa potem še rešitve
n=11,48
Lahko pa tudi samo modula zmnožiš in ročno poiščeš ujemanja.

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

4.
Če sledim postopku:
\(x^2-7y^2=2\)
\((x^2-7y^2)^2=4\)
\((x^2+7y^2)^2-4\cdot 7 x^2 y^2 = 4\)
Recimo, da pri prvi eliminiraš y z uporabo originalne enačbe:
\((2x^2-2)^2-4\cdot 7 x^2y^2=4\)
\((x^2-1)^2-7(xy)^2=1\)
\(u^2-7v^2=1\)
To je zdaj Pellova enačba z rešitvami (8,3) in ostalimi rekurzivno določenimi. Zdaj mora pa veljat u=x^2-1 in v=xy. To reši par x=3 in y=1.

Moraš pa pazit pri rekurziji. Rekurzivna zveza za (u,v) recimo da naslednji par (127,48) ampak 128 ni popoln kvadrat. Poglej, kakšno rekurzijo rabiš, da dobiš pravo stvar.

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Namig: rekurzija je ista kot za u,v s tem da notri dajes x.y kot prejsnje clene. To zato, ker je Pellova enacba s svojo enko enota in tvojo enacbo z dvojko lahko vedno mnozis z osnovno in se ohrani. Rekurzija pride pa od (u+v sqrt7)(x-y sqrt7).

Odgovori