Eräällä yliopiston matikan kurssilla, joka aikaisemmin liittyi omaan tutkintoon, käsiteltiin kongruenssiyhtälöitä, jotka onnistuin ohittamaan aika mallikkaasti ymmärtämättä juurikaan, että mistä oikein on kysymys. Tästä nyt ei voi syyttää kuin omaa laiskuutta.
Mutta asiaan, eli ymmärtämättä jäi, että millä periaatteella katsotaan tietyn renkaan (vaikka esim. Z_7) kääntyvät alkiot?
Ja kun nämä käänteisalkiot ilmeisestikin liittyvät kongruenssiyhtälöiden ratkaisuun, niin miten ratkaistaan esim. yhtälö 5x = 2 (mod 12)?
Tai 5x toiseen = 2 (mod 12)?
Sori, näppis ei suostu antamaan hattumerkkiä. Ja kiitos, jos joku vaivautuu selvittämään asiaa.
Mutta asiaan, eli ymmärtämättä jäi, että millä periaatteella katsotaan tietyn renkaan (vaikka esim. Z_7) kääntyvät alkiot?
Ja kun nämä käänteisalkiot ilmeisestikin liittyvät kongruenssiyhtälöiden ratkaisuun, niin miten ratkaistaan esim. yhtälö 5x = 2 (mod 12)?
Tai 5x toiseen = 2 (mod 12)?
Sori, näppis ei suostu antamaan hattumerkkiä. Ja kiitos, jos joku vaivautuu selvittämään asiaa.
Vastaukset 9
Vanhimmat
Z_n:n alkio m on kääntyvä jos ja vain jos (n,m)=1. Kongruenssiyhtälön 5x=2 mod 12 voi ratkaista Eukleideen algoritmilla tai kiinalaisella jäännöslauseella. Tapauksessa 5x^2=2 mod 12 tutki mitä eri arvoja lauseke 5x^2 mod 12 saa kun x käy läpi kokonaisluvut.
Tuollaisilla yhtälöillä ei pakosti ole ratkaisua.
Z_n tarkoittaa tässä kai Z/nZ? Merkitsen tätä syklistä ryhmää merkinnällä C_n.
[Huom! Pitää erotella esim. C_4 -ryhmä ja F_4 - kunta toisistaan. (F_4, ) ei ole sama ryhmä kuin (C_4, ). Huomaa, että C_4 ei ole kunta.
Sen sijaan alkuluvuille p, C_p = F_p.
On yleistä tietoa, että äärelliset kunnat ovat kaikki muotoa F_(p^r), missä p on alkuluku. Lisäksi ne muodostavat täsmälleen kaikki äärelliset kunnat. ]
Ryhmälle C_n, kääntyvät alkiot ovat sellaiset alkiot a, että a ja n ovat suhteessa jaottomat. Tämän pitäisi olla helposti nähtävissä - ellei ole, kysy selitystä.
phi-funktio laskee sellaisten alkioiden määrän. Jos n= p_1^r_1 * p_2^r_2*...*p_m^r_m , alkulukumuodossaan, silloin
phi(n) = n * TULO_(i=1,..,m) (1-1/p_i).
Nämä phi(n) alkiota muodostavat ryhmän (C_n)*. Tämä ryhmä on syklinen jos ja vain jos n on muotoa 1,2,4,p^r,tai 2p^r, jollekin alkuluvulle p.
Jos (C_n)* on syklinen, sillä on jokin generaattori g. (Kokeile pieniä aklkioita vuorotellen, kunnes löydät sellaisen, jonka asteluku on phi(n) -- itse asiassa riittää, jos asteluku ei ole phi(n)/p, jokaiselle phi(n)-luvun alkutekijälle.) Silloin kaikki (C_n)*-ryhmän alkiot löytyvät ottamalla 1, g, g^2,...,g^(phi(n)-1).
Jos (C_n)* ei ole syklinen, ei ole mitään helppoa tapaa löytää sen alkioita, kuin käymällä ne läpi yksitellen.
Noniin, katsotaanpas esimerkkejä:
5x=2 (mod 12). 5 ja 12 ovat keskenään jaottomia, joten 5:llä on käänteisluku, joka on myös 5. Siispä x=10 (mod 12).
5x^2=2 (mod 12). Voimme sieventää sen muotoon x^2=10 (mod 12). Tällä on ratkaisu vain jos 10 on neliö mod 12, eli 'quadratic residue mod 12'. Tämän tunnistamisesta voit lukea täältä: http://mathworld.wolfram.com/QuadraticResidue.html .
Tai voit kokeilulla huomata, että vain 1, 4 ja 9 ovat mahdollisia neliöitä mod 12. Siispä ratkaisua ei ole.
Korkeamman asteen yhtälöt on aika paljon vaikeampia ratkaista, mutta niihin on konstinsa -- voin kertoa, jos haluat.
"Korkeamman asteen yhtälöt on aika paljon vaikeampia ratkaista, mutta niihin on konstinsa -- voin kertoa, jos haluat."
Ainakin minä haluaisin kuulla näistä tavoista.
... tässä paria tekniikkaa. Ensimmäinen on neliöjuurille, mutta sen voi aika helposti yleistää korkeamman asteisille juurille. Voit itse tarkistaa yksityiskohdat. (Kaikki nämä yhtälöt ovat mod p, missä p on alkuluku):
1)x^2 = a mod p, (missä a on neliö mod p).
Jos p=3 mod 4, silloin meillä on ratkaisut x=+- a^((p+1)/4) . (Tarkista!)
Jos p=5 mod 8, silloin meillä on ratkaisuina joko x=+-a^((p+3)/8), tai sama kerrottuna 2^((p-1)/4):llä. (Tarkista!)
Muussa tapauksessa: Etsi pienin (Z/pZ)*-ryhmän generaattori, g. Oletetaan myös, että p on muotoa 2^n+1. (Jos se on eri muotoa, voimme silti muuntaa sen väliaikaisesti tätä muistuttavaan muotoon, pienellä lisävaivalla.)
Laitamme x=g^r. Eli meidän pitäisi ratkaista r, ja teemme sen ratkomalla r:n binäärimuodossa (...r_1 r_0). Tämä tapahtuu korottamalla yhtälö eri potensseihin muotoa (p-1)/2^k, k=2,3,... .
(Huom! Eulerin kriteeri kertoo, että a^((p-1)/2)=1 mod p jos ja vain jos a on neliö mod p. )
Esim. x^2= 3^(2r)= 13 mod (2^16+1)
13^(2^14)= 1 mod p, joten r_0=0.
13^(2^13)= 1 mod p, joten r_1=0.
13^(2^12)= -1 mod p, joten r_2=1.
Nyt kerromme 13 sopivalla luvulla, eliminoidaksemme r_2 aiheuttaman tekijän (eli 3^4) x:stä. Sen jälkeen nostamme tuloksen potenssiin 2^11, ja saamme 1. Joten r_3=0....
Jatkamme näin, kunnes meillä on r binäärimuodossa.
2) Toinen metodi perustuu siihen, että yritämme lohkoa polynomistamme P(x) lineaaritekijää laskemalla suurin yhteinen tekijä sopivan polynomin kanssa. Suurin yhteinen tekijä saadaan Euklidin algoritmilla.
Huomaa, että g(x)= x^(p-1)-1=(x+1)(x+2)...(x+p-1) mod p. Eli ensin otamme g:n ja P:n suurimman yhteisen tekijän, jolloin pääsemme eroon toistuvista juurista.
Tämän jälkeen otamme suurimman yhteisen tekijän x^((p-1)/2)-1 kanssa. Tämä faktorisoi polynomimme kahteen eri polynomiin, paitsi jos kaikki ratkaisut ovat joko neliöitä tai epäneliöitä mod p.
Jos onnistui, jatkamme kahden polynomitekijän faktorisointia, kunnes meillä on lineaaritekijät, eli ratkaisut. Jos ei onnistunut, kokeilemme yhteistä tekijää (x+1)^((p-1)/2)-1 kanssa. Jos ei taaskaan onnistu, kokeilemme (x+2)^((p-1)/2)-1 kanssa jne. Lähes 100% todennäköisyydellä onnistumme muutaman kokeilun jälkeen.
... joka kannattaa muistaa on, että jos meillä on esim. 5x=10 mod 15, voimme jakaa kaiken 5:llä, tyyliin x=2 mod 3. Tämä antaa ratkaisuiksi: 2,5,8,11,14.
Tuo jo mainittu Kiinalainen jäännöslause tarkoittaa vain sitä, että voit jakaa kongruenssin mod n useampaan kongruenssiin -- jakamalla n-luvun keskenään jaottomiin tekijöihin. Tämän perusteella voit ratkaista alkuperäisen yhtälön (katso Kiinalaisen jäännösteoreeman todistusta saadaksesi tarkan ratkaisutavan).
Esim. kun 5x=2 mod 12, tämä kongruenssi on sama kuin kongruenssipari x=1 mod 3 ja x=2 mod 4.
Käyttämättä Kiinalaisen jäännöslauseen todistusta:
Ensimmäisen kongruenssin vaihtoehdot ovat x=1,4,7,10,13. Toisen vaihtoehdot ovat x=2,6,10,14. Joten kongruenssipari toteutuu vain kun x=10.
Kuten sanottua, kiitoksia molemmille vastauksista. Asia ei teorialtaan ole vaikeaa ymmärtää, mutta jotenkin käytännön tekeminen tuntui aikoinaan silloisen kurssin aikaan vaikealta.
Nykyään pakkomatikat omaan nykyiseen tutkintoon (taloustieteet) liittyen on tehty. Ainoa kiehtova asia ko. jälkimmäisellä kurssilla oli oikeastaan kahden muuttujan funktiot, mutta kurssin tarkoituksen ja aikataulun vuoksi niiden teoriaan ei kovin syvällisesti luonnollisesti keretty perehtymään. Valitettavasti.
Menköön samaan topikkiin, mutta löytyykö jostain todistusta sille, miksi kahden muuttujan funktion ääriarvoja tarkastellessa Hessiaania tarkastellaan , kuten tarkastellaan?
Kiitos.
Vielä lisäys edelliseen, eli jostain syystä matematiikka on uskomattoman kiehtovaa. Valitettavasti ajan puute estää ottamasta matematiikan kursseja sivuaineeksi tätä enempää, mitä olen kerennyt käymään. Harva asia on matematiikassa jäänyt perehtymisen jälkeen ymmärtämättä, mutta koska lamppu ei syty aina ihan hetkessä, niin matematiikan opiskelu vie minulta pirusti aikaa..
Perustelut, ja jopa outline-proof siitä Hessianin käytöstä löytyy näiden luentomuistiinpanojen osiosta 2.3.3 (pdf-tiedoston sivut 50-52, mutta sivuilla lukee sivunumerot 38-40)
http://www.damtp.cam.ac.uk/user/sjc1/teaching/VC_2000.pdf
Todistus ei ole kovin mielenkiintoinen, mutta lyhyesti: se tulee suoraan Taylorin teoreemasta sekä symmetristen matriisien ominaisuuksista (reaaliset eigenarvot ja ortonormaali eigenvektori-joukko) .
Matematiikka on todella kaunista. Itse pidän lähinnä puhtaasta matikasta (kaikki derivointi ym. tekninen kikkailu on jo soveltavaan päin).
Mm. Kombinatoriikka on lempialaani: se pitää sisällään paljon sellaista matikkaa, jonka konseptit ovat itsestäänselviä, mutta hauskuus on nerokkaissa, ja usein oivaltavissa todistuksissa. Todistukset eivät aina ole edes vaikeita ymmärtää, mutta on selvää että niiden keksiminen on vaatinut luovuutta. (Neliväriteoria on klassinen esimerkki.)
Kombinatoriikkaa ovat esim. graafiteoria ja Ramseyn teoria. Matematiikan satunnaisharrastajalle 'Proofs from the Book' on hieno kirja, joka sisältää kuvakirja-tyyliin kauneimpia todistuksia eri aloilta, eritoten kombinatoriikasta.
Esim. tässä on muistiinpanot Cambridgen neljännen vuoden matikan kurssista Ramsey teoriassa: http://www.dpmms.cam.ac.uk/~par31/notes/ramsey.pdf
Ainakin ykkössivun kaunis todistus (Ramsey teorian koko perusta) on ymmärrettävissä kelle tahansa.
Teoria on seuraava: Kuvittele, että kaikki kokonaislukuparit on merkitty joko siniseksi tai punaiseksi. Silloin on olemassa Ääretön kokonaislukujen osajoukko, jonka kaikki parit on väritetty yhdellä värillä.
(Tässä ollaan vähän samoilla jäljillä kuin pigeonhole-principle-periaatteessa: eli on mahdotonta laittaa n 1 tavaraa eri laatikoihin, jos laatikoita on vain n. Kuulostaa itsestäänselvältä? 'Proofs from the Book'-kirjassa on kokonainen kappale yllättäviä tuloksia, joita voi johtaa siitä!)
Sivuilla 2,3,4 samaa todistusta kehitellään muokkaamalla ja laajentamalla yhtä ja samaa todistusta. Esimerkit antavat kuvaa siitä, miten teoriaa voi soveltaa.
Kombinatoriikka perustuu nimenomaan eri todistustekniikoihin ja niiden hyödyntämiseen. Usein samasta teoriasta onkin kymmeniä versioita.
Useimmat klassiset älypähkinät ovat kombinatoriikkaa: Esim. Jos olet juhlassa, ja sinulla on kaikista eniten ystäviä, ja jokaisella ihmisparilla on yhteinen ystävä, niin silloin tunnet kaikki juhlassa. Tämän todistus löytyy sekin 'Proofs from the Book'- kirjasta. :)
Ei ole olemassa, eikä voi olla olemassa tapaa joka kertoisi kaikista diofantoksen yhtälöistä onko niillä ratkaisua vai ei, puhumattakaan ratkaisu(i)sta. Nyt kun sanon että ei ole olemassa tapaa niin tarkoitan että kerta kaikkiaan ei ole, en siis sitä että ei olisi vielä löydetty.