Teorija števil

Ko tudi učitelj ne more pomagati...
Odgovori
Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Kaj pa primer 2x+5y+100z=200
x=0 mod 5
y=0 mod 2
x=5u
y=2v
100z=200-10u-10v
10z=20-u-v
u+v=0 mod 10
u=10w-v
in končno
x=50w-5v
y=2v
z=2-w

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

Re: Teorija števil

Odgovor Napisal/-a juve »

Aniviller napisal/-a:
juve napisal/-a: 1.) reši diof.enačbo \(15x-24y+14z=5\) ... preuredila sem na kongruenco modula 14 in razcepila modul na 2 in 7.... na koncu dobim da je \(x=2y+5+14t\) in pač tudi nekaj za z (ki je ravno tako odvisen od y in t), pri čemer sem y postavila za polj. parameter, t pa je pač celo število. Je to ok, ali moram dobit prav določena števila ven?
Kaj pa primer 2x+5y+100z=200??
Hm no z je treba še izrazit do konca da se preveri, jaz grem pa raje od začetka ker je težko na sredi "ujet" postopek :) Načeloma bosta 2 prosta parametra ja (očitno iz štetja prostostnih stopenj), prideta kot periodi kongruenc. Se pa da lahkotnejše module probat namesto 7. Po modulu 2 res dobiš
x=1 mod 2
Po modulu 3 je tudi odlično, saj spet dve spremenljivki izgineta:
z=1 mod 3
Iz tega že dobiš
x=1,3,5 mod 6
z=1,4 mod 6
Če bi bila samo x in z, bi bila ta oblika (vse na isti modul) že ugodna, ampak imaš še en korak, tako da kar pustiva pri miru :)
Zdaj imaš x=1+2u in z=1+3v in y se mora pa dat izrazit s tema dvema. Vstaviš
24y=15+30u + 14 + 42v - 5
24y=24+30u + 42v
To je zdaj sicer spet nesrečna nepraštevilska kongruenca (še dodatne pogoje na u in v ti lahko da - če bi pred y stal prafaktor, bi bilo enostavno, tako pa ni preveč lepo).
12y=12+15u + 21v
V glavnem to na desni mora biti z 12 deljivo, da se da y izrazit:
15u+21v=3u+9v=0 mod 12
u+3v=0 mod 4
u=v mod 4
Torej, u in v sta sinhronizirana po modulu 4. Pišeš lahko torej v=u+4w in izraziš s parametroma (u,w) vse. Polna rešitev:
x=1+2u
y=1+3u+7w
z=1+3u+12w
Zanimivo je tudi že takoj na začetku ugotovit
y=z mod 5
kar je potem iz končne rešitve seveda očitno. Ni pa treba tega. Vedno je dovolj toliko kongruenc kolikor bo prostih parametrov (idealno je, če imaš po modulu čim manj spremenljivk, tukaj se je dalo vedno dveh znebit), potem pa zadnja, da poda še dokončno zvezo med parametri, da se da zadnji parameter izrazit.

Izbira parametrov je sicer do neke mere poljubna (podobno kot realnih linearnih enačbah).

ni mi jasno od kje potem dobim kar da je x=1,3,5 mod 6 in z= 1,4 mod 6?

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Saj tega niti ne rabiš (ker greš kar naprej po modulu 2). Je pa to enostavno razvoj na daljšo periodo.
x=1 mod 2 je v resnici x=1,3,5,7,9,11,... in če gledaš periodo 6, ti trije padejo noter :)

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

Re: Teorija števil

Odgovor Napisal/-a juve »

Aniviller napisal/-a:
3) Pa saj štirko lahko izpostaviš in pokrajšaš. Od kod točno to dobiš?
No recimo da greš takoj na pitagorejske trojice in zapišeš
n=2pq
2n+1=p^2-q^2
tretja (koren desne strani) je potem p^2+q^2
(obratno ne gre, ker 2pq je sodo). Takoj lahko skombiniraš
4pq+1=p^2-q^2
1=p^2-q^2-4pq
Po modulu 4 ugotoviš, da mora bit q sodo, p pa liho. n torej deljivo s 4. No mogoče bo ta zgornja Diofantka ratala :)
joooj, šele zdaj vidim da je deljivo s 4... al si rada kompliciram življenje =) drugače sem sklepala iz transformacij ki so tukaj http://en.wikipedia.org/wiki/Pell's_equation ampak sem šele zdaj ugotovila da sta možni 2, mogoče bi se z drugo razšlo ali pa je v celoti to pač napačen postopek =)

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Pokaži, da enačba ni rešljiva v naravnih številih: \((2x)^{2x}-1=y^{z+1}\).

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

No kot prvo ničla ne sme bit naravno število ker sicer daš z=0, izbereš x in dobiš y. Vprašanje se torej glasi, ali je leva stran lahko popolna potenca.

Če razbiješ na levi na
[(2x)^x-1][(2x)^x+1]
je to faktorizacija na dve tuji si števili (zaradi 2x je to liho*liho in ne moreta imeti skupnega faktorja 2). Torej mora vsako število posebej bit potenca naravnega števila.
Ampak A in A+2 ne moreta biti oba potenci nekega števila.
Če je
A=B^C,
potem je naslednji kandidat za število na isto potenco
(B+1)^C>A+CB^(C-1)+1>A+2 za vsak C>1.
Tole je dokaz, da so kvadrati in višje potence vedno več kot za 2 narazen. Torej se ne da :)

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Tega ne razumem čisto
Aniviller napisal/-a:potem je naslednji kandidat za število na isto potenco
(B+1)^C>A+CB^(C-1)+1>A+2 za vsak C>1.
zakaj npr. ne gledamo \(B^{C+1}\)? in kako smo zgoraj dobili drugo in tretjo neenakost?

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

No C ali pa C+1 saj nima veze, C je paš potenca, večja od 1. Lahko pišeš C=z+1 če hočeš, to ničesar ne spremeni. Edini pogoj je, da je ista potenca, saj hočeš
B^C*D^C=(BD)^C=y^C
B in D pa nimata skupnih faktorjev (tako da ne moreta s skupnimi močmi nabrat za C - vsak mora zase to narest).

Pri prvi neenakosti sem samo razbil po binomski formuli in obdržal prva dva in zadnji člen (vsi manjkajoči so tudi pozitivni, zato tam znak za večje). Naslednji je pa tudi trivialen. Pač srednji člen je večji od 1, ker je C>1, tudi če bi bil B=1 ne bi pomagalo.

Saj ta trditev o razmikih potenc je tako enostavna, da sigurno lahko pristopiš še kako drugače. Meni se samo tole zdi daleč bolj enostavno - gre za posplošitev tistega znanega dejstva, da razmiki med kvadrati naravnih števil naraščajo po 2.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Zanima me eno bolj teoretično vprašanje.
\(\tau(n)\) je število naravnih deliteljev števila \(n\). Zakaj velja \(\tau(n) \leq 2 \sqrt{n}\)?

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

Takoj po smislu, če je število k delitelj n-ja, potem je n/k tudi. Vsako število ima torej "par", razen, če je n popoln kvadrat, ko je k=sqrt(n) sam svoj par.

Samo, če ima vsak svoj par, jih je nad sqrt(n) lahko kvečjemu toliko kot jih je pod. Neenakost sledi :)

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Razumem, super :)

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Še nekaj v zvezi s teorijo.
Linearne kongruence: \(ax==b(n)\). Velja:
1) Če je \((a,n)=1\), potem ima ntk. eno rešitev modulo \(n\).
2) če je \((a,n)>1\) in \(d|n\), potem ima \(d\) rešitev modulo \(n\).
ne razumem čisto 2)...rekli smo
\(a=a_1 d, n= n_1 d, b= b_1 n\), kongruenca je potem: \(a_1dx==b_1 d(n_1 d)\), delimo z \(d\) in dobimo \(a_1x==b_1(n_1)\) in \((a_1,n_1)=1\), po 1) obstaja ntk. ena rešitev po modulu \(n_1\). Tega dalje ne rezumem:...
Ker je \(n=n_1 d\), \(x\) po modulu \(n\) ni enolično določen, saj mu lahko prištejemo polj. večkratnike \(n_1\).???

Drugo vpr.: v 2) se zgodi, da imamo lahko več rešitev za linearno enačbo, kar se v linearni algebri ne zgodi. To se zgodi zato, ker so v \(\mathbb{Z}_n\) delitelji niča. V linearni algebri pa delamo nad obsegi in \(\mathbb{Z}_n\) je obseg ntk. tedaj, ko je \(n \in \mathbb{P}\). Kako bi dokazali zadnji stavek??

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

Re: Teorija števil

Odgovor Napisal/-a Aniviller »

2) Tako je, pravilno razumeš. Mogoče lahko razmislek zapišeš v nekoliko daljši obliki:
\(a_1 x = b_1 \mod n_1\)
enolična rešitev po modulu \(n_1\) tukaj pomeni
\(x=x_1+k n_1\)
ampak ko pa delaš po modulu \(n=dn_1\), pa ima zgornja serija rešitev več rešitev v eni perodi (natanko d), ker se šele pri k=d ponovi. Torej, po modulu \(dn_1\) prištevanje večkratnikov \(n_1\) ne vodi nazaj v isto vrednost.

Drugo vprašanje: ne vem kako rigorozen dokaz rabiš, ampak ... najprej lahko dokažeš, da \(n\notin \mathbb{P}\) ni obseg. Obstaja namreč faktorizacija \(pq=n\) kjer \(p,q\neq 1,n\). Poleg prave ničle \(0=n\mod n\) imaš torej še vsaj dva delitelja niča: \(pq=0\mod n\). Število deliteljev niča je seveda odvisno od tega, koliko faktorjev ima n.

Podobno potem v obratno smer, s protislovjem. Če je n praštevilo, \(\mathbb{Z}_n\) pa ni obseg, potem obstaja delitelj niča. Ampak potem pa obstaja \(pq=0\mod n\), kar bi pomenilo, da je \(pq=kn\), in če \(p,q\neq 1,n\), imata p,n skupni faktor.

No - seveda tukaj smo se ukvarjali samo z delitelji niča... formalno bi bilo treba dokazat še ostale lastnosti obsega. Ampak recimo, da vemo, da je \(\mathbb{Z}_n\) vsaj komutativni kolobar.

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

Re: Teorija števil

Odgovor Napisal/-a delta »

Hvala za zgornje, razumem:).
Zanima me še nekaj. Neskončni verižni ulomek je periodičen če in samo če je število kvadratično iracionalno število t.j. če zadošča neki kvadratni enačbi s celimi števili. Kako to potem preveriš v praksi? npr. da me zanima, če je \(\sqrt{19}\) periodičen, torej kako ugotovim, če je kvadratna iracionala? zapisali smo še, da lahko kv. ir. št. zapišemo v obliki \(\alpha=A+B\sqrt{n}; A,B \in \mathbb{Q}\) in \(n \in \mathbb{Z}\), \(n\) ni popoln kvadrat. Kako se da za neko število takoj povedat(če se da??) da ga lahko zapišemo s periodičnim verižnim ulomkom.

Drugo vpr.: periodični ulomki so oblike: npr. \(\sqrt{19}=[4;2,1,3,2,8]\), splošno \(\sqrt{n}=[a_0; a_1,..., a_{n-1}, a_n]\), \(a_n=2 a_0\), ostali tvorijo palindrom. Ali to velja za VSE periodične ulomke?

Rock
Prispevkov: 9229
Pridružen: 27.11.2008 11:14
Kraj: Ljubljana

Re: Teorija števil

Odgovor Napisal/-a Rock »

delta napisal/-a:Neskončni verižni ulomek je periodičen če in samo če je število kvadratično iracionalno število
Zanima me, zakaj taka formulacija (nisem matematik):
ali lahko prvi 'če' izpustimo?
Zadostuje:
Neskončni verižni ulomek je periodičen samo (v primeru), če je število kvadratično ... ___?

Odgovori