4^n -1 jaollinen kolmella todistus
Matti Lehtiniemi
koko ongelman.
Todistus alkoi sillä ,että 4^n -1 on aina jaollinen kolmella.
Pyörittelin hieman asiaa päässäni ja sain todistettua sen.
Nyt yllättäen netistä ei löydy googlaamalla tuon 4^n -1 jaollisuutta.Ainakin tunnin pari googlasin.
Onko totta ettei tuota ole todistettu vielä ?
Tai jos on niin mistä todistus löytyy ?
(siis 4^n -1 on aina jaollinen kolmella)
Matti
Matti Lehtiniemi
Ai perhana, mutta tämähän on erikoistapaus.
Siis 6*6 -1 on jaollinen viidellä, 7*7-1 on jaollinen kuudella jne...
Huomasin tuon kun menin sänkyyn löhöämään.Onkohan meikäläisen pää lahoamassa , kun en huomannut
tuota.Tai sitten vaan on tullut niin monta vuotta siitä,kun viimenksi tällaisia ongelmia mietin.
Luulisi kuitenkin tuon collatzin ongelman ratkeavan tämän avulla jotenkin.
Matti
Matti Lehtiniemi
> Siis 6*6 -1 on jaollinen viidell�, 7*7-1 on jaollinen kuudella jne...
Siis mit� helvetti�.
6*6*6-1 on jaollinen viidell�. 6*6*6*6 -1 on jaollinen viidell�.
Miksi t�t� lausetta oiken kutsutaan ?
Luulin ett� t�ss� on kyseess� :
http://fi.wikipedia.org/wiki/Fermat'n_pieni_lause
Mutta tuossa puhutaan vain alkuluvuista ja 4 ei ole alkuluku.
Matti
Tuomas Yrjövuori
> (siis 4^n -1 on aina jaollinen kolmella)
Päädyin joskus vähän samantapaiseen ajatuskuvioon, kun piti luoda
algoritmi murtolukujen muuttamiseksi binäärisiksi jaksollisiksi
esityksiksi tyyliin esimerkiksi,
1/3 = sum(1/4^n, n-->inf) = 0.01010101...(b)
Ainakin itseäni joskus helpottaa lukuteoreettisten juttujen miettiminen
välillä eri lukujärjestelmisissä kuin 10-järjestelmässä. Hexat ja
binäärit ovat tietysti tietokonemaailmasta tuttuja. Kannattaa joskus
kokeilla miettiä asioita myös jossain ei-kahdella-jaollisessa (eikä
5:llä) lukujärjestelmässä.
--
Tuomas Yrjövuori
Jussi Piitulainen
> > Ai perhana, mutta tämähän on erikoistapaus.
> > Siis 6*6 -1 on jaollinen viidellä, 7*7-1 on jaollinen kuudella jne...
>
> Siis mitä helvettiä.
> 6*6*6-1 on jaollinen viidellä. 6*6*6*6 -1 on jaollinen viidellä.
>
> Miksi tätä lausetta oiken kutsutaan ?
Polynomi p(x) voidaan jakaa tekijöihin a * (x - r) * q(x) missä r on
semmoinen nollakohta sille polynomille, vai mikä juuri se nyt on, ja
q(x) on pienempiasteinen polynomi. (Kompleksiluvut ovat sitä varten,
että niitä nollakohtia riittää polynomin asteluvun verran.)
Yksi polynomin x^n - 1 nollakohta on selvästi 1, kun onhan nimittäin
ilmeistä, että 1^n - 1 = 0. Tiedämme niin-ollen:
x^n - 1 = (x - 1)q(x), missä q(x) on x:n polynomi
Jos nyt x:n paikalla on jokin sellainen positiivinen kokonaisluku kuin
4 tai 6 tai 7, niin selvästi, tietämättä mikä nimenomainen polynomi
q(x) on, tiedämme, että x^n - 1 on positiivinen kokonaisluku, (x - 1)
on positiivinen kokonaisluku, ja q(x) on positiivinen kokonaisluku.
Siinä se 4^n - 1 jne. siis on riittävästi tekijöihin jaettuna. Se 3
jne. on tekijä (4 - 1) jne.
Matti Lehtiniemi
Joo, kiitos selityksestä.Ihan järkeenkäypä todistus.
Itse pyöritin todistuksen graafisesti rekursiivisesti päässäni mutta tuokin todistaa sen hyvin.
Muistelin nähneeni jollain TKK:n kurssilla tuon lauseen(Diskreetti matematiikka ?) mutta en millään
saanut googlattua sitä netistä.
Vähän samantyyppinen selitys kun millä todistetaan, että Mersennen alkuluvuissa 2^p -1 täytyy
p:n olla alkuluku jotta 2^p -1 olisi alkuluku.
Tässa Collatzin ongelmassa ja sen ratkaisussa on selvästi kysymys alkuluvuista.Joka tapauksessa
tuo pitää hahmottaa että 4^n -1 on jaollinen kolmella.(eli 2^n -1 on jaollinen jos n on parillinen)
Matti
Matti Lehtiniemi
> p:n olla alkuluku jotta 2^p -1 olisi alkuluku.
Ai mutta hyvänen aika.Tämähän todistaa tuon Mersennen jutun.
Jos p = a*b niin silloin a saadaan siirrettyä muotoon (2*a)^b joilloin kantaluku ei enää on 2 eli
tämä todistuksesi kertoo sen, että tekijä löytyy varmasti.
Matti
Jussi Piitulainen
> > x^n - 1 = (x - 1)q(x), missä q(x) on x:n polynomi
>
> Joo, kiitos selityksestä.Ihan järkeenkäypä todistus.
> Itse pyöritin todistuksen graafisesti rekursiivisesti päässäni mutta
> tuokin todistaa sen hyvin. Muistelin nähneeni jollain TKK:n
> kurssilla tuon lauseen(Diskreetti matematiikka ?) mutta en millään
> saanut googlattua sitä netistä.
Google löysi hakusanalla "algebran peruslause" tämän:
<https://matta.hut.fi/matta2/isom/html/poly-yht3.html> (Simo
K. Kivelän teoksesta M niin kuin Matematiikka, paperinenkin on,
semmoinen kelta-oranssi).
Matti Lehtiniemi
> K. Kivelän teoksesta M niin kuin Matematiikka, paperinenkin on,
> semmoinen kelta-oranssi).
Heh , kyllä mä nyt tuon muistan.
Tarkoitin tuota x^n -1 juuri on yksi.
En ole näitä polynomeja 15 vuoteen pyörittänyt joten en tuota suoraan nähdyt kaavasta.
Kyllähän tuosta juuren (x-1) pystyy näkemään jos pystyt hahmottamaan ettei q(x) tarvitse laskea ollenkaan.
Kivelän pojan kyllä olen joskus tuntenut.Ja olen tainnut Kivelän luennollakin käydä.(Taisi olla niin
aikaisin aamulla että kävin ehkä 1-2 kertaa)
Matti
Jussi Piitulainen
> Tarkoitin tuota x^n -1 juuri on yksi.
> En ole näitä polynomeja 15 vuoteen pyörittänyt joten en tuota
> suoraan nähdyt kaavasta.
Heti olisit nähnyt, jos olisit keksinyt yrittää arvata yhden
juuren.
Tai minä taisin oikeastaan keksiä yrittää nähdä, että x^n - 1
on polynomina jaollinen x - 1:llä, ja sitten riittikin tietää,
että aina p(x) = a(x - r_1)...(x - r_n), joten 1:n täytyisi
olla yksi juurista, ja vot, onhan se: 1^n - 1 = 1 - 1 = 0.
Matti Lehtiniemi
> Jos p = a*b niin silloin a saadaan siirrettyä muotoon (2*a)^b joilloin kantaluku ei enää on 2 eli
Siis (2^a)^b eikä (2*a)^b
M
Jussi Piitulainen
Eihän tämä riitäkään. Vain totean, että q(x) on positiivinen
kokonaisluku, kun x on positiivinen kokonaisluku, mutta perustelu
puuttuu tykkänään. Perustelen väitteen tietämällä sittenkin, mikä
polynomi q(x) on:
x^n - 1 = (x - 1)(sum x^k, 0 <= k < n)
Siitä sen nyt näkee. (Ensi kerralla muistan ilman lähteitäkin, miten
x^n - 1 jaetaan tekijöihin.)
Ohman
wrote:
>
> - Näytä siteerattu teksti -
Koska 1 on yhtälön x^n - 1 = 0 juuri, eli polynomin x^n - 1
nollakohtaa, x - 1 l x^n - 1 (x-1 jakaa polynomin x^n - 1) ja x^n - 1
= (x - 1) P(x), missä P(x) on polynomi astetta n-1.Eli siis jos k on
positiivinen kokonaisluku, k^n - 1 on aina jaollinen k - 1 :llä.
Jos n on parillinen, on myös x = -1 yhtälön x^n - 1 on juuri ja ja x^n
- 1 on myös jaollinen luvulla x + 1.Tällöin x^n - 1 = (x - 1) (x + 1)
Q(x), missä Q(x) on astetta n - 2 oleva polynomi.
Voidaan asia esittää myös näin: n on parillinen,olkoon se 2k (k
positiivinen kokonaisluku). Tällöin
x^(2k) - 1 = (x^k - 1) (x^k + 1) , 1 on yhtälön x^k - 1 = 0 juuri ja
-1 on yhtälön x^k - 1 = 0 juuri, jos k on parillinen tai yhtälön x^k
+ 1 juuri jos k on pariton.
Lisään vielä, että Collatzin probleemaa ei ole ratkaistu.
Ohman
Ohman
Täsmennys:edellisessä kappaleessa olisi ollut parempi sanoa "jaollinen
polynomilla x + 1" eikä "luvulla x + 1", mutta eiköhän asia kuitenkin
selvinnyt.
Siis:jos n on parillinen ja k on positiivinen kokonaisluku niin k^n -
1 on jaollinen luvuilla k + 1 ja k - 1.
>
> Voidaan asia esittää myös näin: n on parillinen,olkoon se 2k (k
> positiivinen kokonaisluku). Tällöin
>
> x^(2k) - 1 = (x^k - 1) (x^k + 1) , 1 on yhtälön x^k - 1 = 0 juuri ja
> -1 on yhtälön x^k - 1 = 0 juuri, jos k on parillinen tai yhtälön x^k
> + 1 juuri jos k on pariton.
>
> Lisään vielä, että Collatzin probleemaa ei ole ratkaistu.
>
> Ohman- Piilota siteerattu teksti -
Ohman
>
> - Näytä siteerattu teksti -- Piilota siteerattu teksti -
>
> - Näytä siteerattu teksti -
Ennen kuin joku viisas ehtii kritisoida, lisään tekstiin vielä sen,
että "kun k on positiivinen kokonaisluku" p.o. "kun k on positiivinen
kokonaisluku > 1".
Ohman
Antti Valmari
>> Ai perhana, mutta tämähän on erikoistapaus.
>> Siis 6*6 -1 on jaollinen viidellä, 7*7-1 on jaollinen kuudella jne...
>
> Siis mitä helvettiä.
> 6*6*6-1 on jaollinen viidellä. 6*6*6*6 -1 on jaollinen viidellä.
Olet ehkä huomannut, että kymmenjärjestelmässä laskettaessa yhteen-,
vähennys- ja kertolaskun tuloksen viimeinen numero riippuu vain kunkin
lähtöarvon viimeisestä numerosta. Tämä toimii yleisemminkin: yksi
lukuteorian perusasioista ja perustekniikoista on, että yhteen-,
vähennys- ja kertolaskun lopputuloksen jakojäännös riippuu ainoastaan
lähtöarvojen jakojäännöksistä. Kaavana sanoen, jos jakojäännöstä
merkitään %:lla, niin esim.
((x+an)(y+bn)) % n = (xy) % n.
(Tässä x, y, n, a ja b ovat kokonaislukuja ja n =/= 0.)
Lasketaan vaikka (6*6*6-1) % 5. Koska 6 = 1+1*5, tulos on sama kuin
(1*1*1-1) % 5 = 0 % 5 = 0.
Tämä tulos ei ole syvällinen, vaan suora seuraus siitä, että (x+an) % n
= x % n. Nimittäin:
((x+an)(y+bn)) % n = (xy + xbn + any + anbn) % n
= (xy + (xb + ay + anb)n) % n = (xy) % n.
> Miksi tätä lausetta oiken kutsutaan ?
Sillä ei ole nimeä, koska se on lukuteorian laskusäännöt tuntevalle
itsestään selvä.
--- Antti Valmari ---
Jussi Piitulainen
> lähtöarvon viimeisestä numerosta. Tämä toimii yleisemminkin: yksi
> lukuteorian perusasioista ja perustekniikoista on, että yhteen-,
> vähennys- ja kertolaskun lopputuloksen jakojäännös riippuu ainoastaan
> lähtöarvojen jakojäännöksistä. Kaavana sanoen, jos jakojäännöstä
> merkitään %:lla, niin esim.
>
> ((x+an)(y+bn)) % n = (xy) % n.
>
> (Tässä x, y, n, a ja b ovat kokonaislukuja ja n =/= 0.)
>
> Lasketaan vaikka (6*6*6-1) % 5. Koska 6 = 1+1*5, tulos on sama kuin
> (1*1*1-1) % 5 = 0 % 5 = 0.
Taidat käyttää tuossa ensin eri kaavaa, jota et erikseen mainitse
mutta joka näyttää vastaavan tekstiäsi ja myös pitävän paikkansa:
(x - y) % n = (x % n - y % n) % n
Siis (6*6*6 - 1) % 5 = ((6*6*6) % 5 - 1 % 5) % 5, joka sitten sievenee
juuri niin kuin esitit.
Jyrki Lahtonen
algebran suosima tapa hoitaa tällaisia.
Siis merkintä
a = b (mod n)
tarkoittaa yksinkertaisesti sitä, että luku a-b on jaollinen luvulla n.
Kongruenssit vakiomodulin (yllä n) suhteen kunnioittavat puolittain
kerto- ja yhteenlaskua (ja kertolaskun seurauksena potenssiin
korottamista), joten:
4 = 1 (mod 3) (koska 4-1=3 on selvästi kolmella jaollinen)
=> 4^n = 1^n (mod 3)
mikä olikin väite.
Kongruenssi on matematiikassa parempi kuin insinöörien ja ohjelmoijien
suosima jakojäännösoperaattori. Valmarilla olikin oikein (!!) käytetty
tästä jälkimmäisestä symbolia "%", josta joskus näkee valitettavasti
myös käytettävän merkintää "mod". Kongruenssin etuna on se, että se on
ekvivalenssirelaatio, eli säännöt
a = a (mod n),
a = b (mod n) => b = a (mod n),
a = b (mod n) ja b = c (mod n) => a = c (mod n)
ovat aina voimassa. Niinpä luvut voidaan jakaa ekvivalenssiluokkiin,
muodostaa renkaita yms. struktuureja jne.
Heittäessäni keikkaa Nokialla niin kyllä niin mieleni pahoitin, kun
insinöörit käyttivät "mod":ia vaikka tarkoittavat "%":ia :-). Mod on
luonteeltaan vertailuoperaattori, eli
a = b (mod n)
tarkoittaa samaa kuin (pseudo-C notaatiolla kirjoitettu)
(a%n)==(b%n).
Jakojäännöksen muodostaminen on taas on luonteeltaan laskutoimitus, joka
ottaa sisäänsä kaksi lukua ja sylkee ulos yhden.
Virhe muuten ei rajoittunut Nokian insinööreihin, vaan näytti olevan
maailmanlaajuinen. Lienee saanut alkunsa jostakin ohjelmointikielestä ja
levinnyt sieltä kuten syöpä.
Cheers,
Jyrki Lahtonen, Turun yliopisto
Matti Lehtiniemi
No ei tämäkään mikään täysin itsestäänselvä selitys ole, jouduin minäkin 5-10 minuuttia tuota ihmettelemään ennen kun tajusin mitä
tarkoitit.
Minusta tuo Jussin selitys on havainnollisempi.
Tuo modulo-aritmetiikka on aika kaukana reaalimaailman haasteista ja olisin ehkä joskus 15 vuotta sitten
osannut hahmottaa ratkaisun tuota kautta.
Aika mielenkiintoinen juttu tuokin kuitenkin.Väittäisin ettei noita modolu-juttuja kovin hyvin osattu edes
korkeakouluissa 20 vuotta sitten. Nykyään kun on PGP:t ja RSA:t niin tällainenkin matematiikka koetaan
tärkeäksi.
Oma kiva pikku juttunsa tämä kokonaislukujen kanssa värkkääminen.
Matti
Matti Lehtiniemi
Pascalissa on div ja mod . Eli mod on jakojäännös.
C:ssä taas % on modulo.
Mun mielestä aivan sama mitä merkintää käytetään.
Matti
Ohman
me.kolumbus.fi> wrote:
> > maailmanlaajuinen. Lienee saanut alkunsa jostakin ohjelmointikielest ja levinnyt sielt kuten sy p .
>
> Pascalissa on div ja mod . Eli mod on jakoj nn s.
> C:ss taas % on modulo.
> niin
> Mun mielest aivan sama mit merkint k ytet n.
>
> Matti
Todistin tuolla aiemmin jo sen, että jos n on pariton kokonaisluku
(n>2) ja k on kokonaisluku (k>1), niin k^n - 1 on jaollinen luvulla k
- 1. Ja jos n on parillinen (n>= 2), on k^n - 1 jaollinen sekä
luvulla k - 1 että luvulla k + 1.
En oikein ymmärtänyt,mihin tuota jatkokestelua tarvittiin tässä
asiassa. Oliko tarkoitus ehkä valaista asiaa joltain toiselta
"kantilta"? Vai eikö todistustani ymmärretty?
Ohman
Matti Lehtiniemi
>(n>2) ja k on kokonaisluku (k>1), niin k^n - 1 on jaollinen luvulla k
>- 1. Ja jos n on parillinen (n>= 2), on k^n - 1 jaollinen sekä
>luvulla k - 1 että luvulla k + 1.
Jussihan todisti tuon ensimmäisen asian minkä kirjoitit ennen sinua.
Tuota toista asiaahan ei tässä varsinaisesti kysyttykään.
M
Jussi Piitulainen
> Kongruenssi on matematiikassa parempi kuin insinöörien ja
> ohjelmoijien suosima jakojäännösoperaattori. Valmarilla olikin
> oikein (!!) käytetty tästä jälkimmäisestä symbolia "%", josta joskus
> näkee valitettavasti myös käytettävän merkintää "mod". Kongruenssin
Tavallisesti % on kyllä prosenttimerkki eikä jakojäännösoperaattori.
Matematiikassa käytetään yleisesti identtisiä merkintöjä aivan eri
asioista, ja nyt paheksut sitä, että jotkut käyttävät yhteensopivia
merkintöjä asioista, joiden välillä on selvä ymmärrettävä yhteys.
Kirjaat itse sen yhteyden näkyviin:
> a = b (mod n)
>
> tarkoittaa samaa kuin (pseudo-C notaatiolla kirjoitettu)
>
> (a%n)==(b%n).
>
> Jakojäännöksen muodostaminen on taas on luonteeltaan laskutoimitus,
> joka ottaa sisäänsä kaksi lukua ja sylkee ulos yhden.
Minä sanoisin, että
a = b (mod n)
tarkoittaa samaa kuin
a mod n = b mod n.
Missä on ongelma? Ei ole määritelty, mitä "n mod m" tarkoittaa? No
määritellään:
n mod m = n - m floor(n/m) (kun m ei ole 0)
Ei ole vieläkään määritelty? Tässä vaiheessa en enää ymmärrä
matemaatikon ajatuksenjuoksua. Tunne on varmaan molemminpuolinen.
Vai onko ongelma se, että matematiikassa ei ole tapana käyttää
jakojäännösoperaattoria lainkaan? Se seikka ei muutu miksikään sillä,
että kieltäydyt ymmärtämästä toisten käyttämää notaatiota.
(Jos tarkoitat merkintää "a (mod n)" niin olen samaa mieltä siitä,
että se on virhe.)
> Virhe muuten ei rajoittunut Nokian insinööreihin, vaan näytti olevan
> maailmanlaajuinen. Lienee saanut alkunsa jostakin
> ohjelmointikielestä ja levinnyt sieltä kuten syöpä.
Sitä on opetettu ainakin Stanfordissa tietojenkäsittelytieteilijöille,
kuitenkin tavalla, joka ei ollenkaan sekoita näitä kahta käsitettä
(jakojäännöstä ja kongruenssia) vaan päinvastoin nimenomaan tekee
niiden eron selväksi. Viittaan Grahamin, Knuthin ja Patashnikin
teokseen Concrete Mathematics.
En näe virhettä. Eikö insinöörien kanssa olisi helpompi keskustella,
jos tyytyisit sanomaan, että matematiikassa tämä asia on tapana tehdä
tällä toisella tavalla, jolla on etunsa heidän tapaansa verrattuna?
Mutta joo, ohjelmointikielten puolelta jakojäännösoperaattori varmasti
tulee. En tiedä, että missään ohjelmointikielessä olisi sellaista kuin
matematiikan kongruenssinotaatio.
Jyrki Lahtonen
>> maailmanlaajuinen. Lienee saanut alkunsa jostakin ohjelmointikielestä
>> ja levinnyt sieltä kuten syöpä.
>
> Pascalissa on div ja mod . Eli mod on jakojäännös.
> C:ssä taas % on modulo.
Ei ole. C:ssä % on jakojäännös. Modulo ei ole jakojäännös vaan
vertailuoperaattori. Syntaksiltaan vähän niin kuin "=", "<" tai ">"
muualla matematiikassa, ja "==" C:ssä (ja "=" Pascalissa), eli ötökkä,
joka ottaa sisäänsä kaksi lukua ja sylkee ulos tyyppiä "boolean" olevan
muuttujan eli totuusarvon. Suluissa mainittu moduli vaan määrittelee
tuon vertailuoperaation.
Siis vähän niin kuin seuraavassa taulukossa
===========================================
lauseke arvo
(5%2) 1
(7%4) 3
5 = 2 (mod 3) tosi
5 = 1 (mod 3) epätosi
>
> Mun mielestä aivan sama mitä merkintää käytetään.
>
> Matti
>
Johonkin hommaan on varmaan samantekevää, mutta kun toi ohjelmoija alkaa
protestoida, kun kirjoitankin, että
2 = 5 (mod 3).
Algebrassa pointti on, että ekvivalenssiluokan alkiot samaistetaan,
joten voin kirjoittaa (modulo 3) yhtä hyvin 2, 8, 11 tai -4.
Ohjelmoin itsekin Pascalilla DOS-aikaan. Luulin, että siinä sitten "mod"
toimii noin kuin jakojäännös, eli jaettassa n:llä on jakojäännökselle n
eri mahdollisuutta. Eipäs menekään noin, sillä
Pascalin mod(-2,3) olikin -2 eikä 1 niin kuin kuvittelin.
Cheers,
Jyrki
Jussi Piitulainen
> Johonkin hommaan on varmaan samantekevää, mutta kun toi ohjelmoija
> alkaa protestoida, kun kirjoitankin, että
>
> 2 = 5 (mod 3).
Kun kirjoitin tuon pitkän vuodatukseni notaatioerimielisyyksistä tässä
(säädin sitä otsikkoa; säädän tätäkin) niin lisään vastapainoksi pari
samanmielistä huomiota.
Ensiksi, minustakaan ohjelmoijan ei pitäisi tässä protestoida, ei
ainakaan sitten enää, kun asia on hänelle selitetty.
> Ohjelmoin itsekin Pascalilla DOS-aikaan. Luulin, että siinä sitten
> "mod" toimii noin kuin jakojäännös, eli jaettassa n:llä on
> jakojäännökselle n eri mahdollisuutta. Eipäs menekään noin, sillä
> Pascalin mod(-2,3) olikin -2 eikä 1 niin kuin kuvittelin.
Toiseksi, jos näin on, niin tuo Pascalin mod ei ollut oikein
onnistunut tai ainakaan onnistuneesti nimetty.
Erilaisista jakojäännöksistä näyttää olevan kirjavia käsityksiä
ohjelmointimaailmassa, mutta olisi varmasti suotavaa, että mod sopisi
yhteen matematiikan kongruenssien kanssa. Esimerkiksi Schemessä (R5RS)
on erikseen (remainder m n) ja (modulo m n), jotka taitavat erota
juuri niin, että (remainder -2 3) on -2 mutta (modulo -2 3) on 1.
(C:tä tunnen huonommin, mutta "%" ei siinä ainakaan ennen ollut
virallisesti nimeltään modulo vaan remainder, ja taisi siinä olla
jätetty ikävästi ainakin osittain määrittelemättä, mitä tapahtuu
negatiivisten lukujen kanssa. Saatan erehtyä.)
Jyrki Lahtonen
> Jyrki Lahtonen writes:
>
>> alkaa protestoida, kun kirjoitankin, ettÀ
>>
>> 2 = 5 (mod 3).
>
> (sÀÀdin sitÀ otsikkoa; sÀÀdÀn tÀtÀkin) niin lisÀÀn vastapainoksi pari
> samanmielistÀ huomiota.
Ihan hyvä tuo vuodatuksesi oli. Setä vaan tässä kiukuttelee. Ongelmana
tosiaan on, että algebrassa ei juurikaan tarvita jakojäännöstä. Tai siis
pikemminkin niin, että nuoressa iässä sisäistin tilanteen sellaiseksi,
että oikeasti samaistamme jäännösluokan kaikki alkiot. Aivan varmasti
tässä myötävaikuttaa se, että algebran tehtävässä tyypillisesti tuo
moduli ei tehtävän aikana lainkaan muutu, jolloin siitä on ehdottomasti
merkintöjen yksinkertaistamisen kannalta hyötyä, ettei sitä tarvitse
toistaa. Tavallaan "modulo n" tehtävää pähkäiltäessä maailmankuva
säädetään sellaiseksi, että koko universumi muodostuu nyt
jäännösluokista modulo n. Usein tehdäänn laskun alussa tällainen kattava
ilmoitus tyyliin "kaikki kongruenssit ovat modulo 60" tms.
>
> Ensiksi, minustakaan ohjelmoijan ei pitÀisi tÀssÀ protestoida, ei
> ainakaan sitten enÀÀ, kun asia on hÀnelle selitetty.
>
>> Ohjelmoin itsekin Pascalilla DOS-aikaan. Luulin, ettÀ siinÀ sitten
>> "mod" toimii noin kuin jakojÀÀnnös, eli jaettassa n:llÀ on
>> jakojÀÀnnökselle n eri mahdollisuutta. EipÀs menekÀÀn noin, sillÀ
>> Pascalin mod(-2,3) olikin -2 eikÀ 1 niin kuin kuvittelin.
>
> Toiseksi, jos nÀin on, niin tuo Pascalin mod ei ollut oikein
> onnistunut tai ainakaan onnistuneesti nimetty.
Tongin tuota (ja muistiani) hetken. Itse asiassa se oli Intelin
prosessori, joka tuon käyttäytymisen määritteli. Ohjelmointikieli vain
tarjosi wrapperin konekielikutsulle.
>
> Erilaisista jakojÀÀnnöksistÀ nÀyttÀÀ olevan kirjavia kÀsityksiÀ
> ohjelmointimaailmassa, mutta olisi varmasti suotavaa, ettÀ mod sopisi
> yhteen matematiikan kongruenssien kanssa. Esimerkiksi SchemessÀ (R5RS)
> on erikseen (remainder m n) ja (modulo m n), jotka taitavat erota
> juuri niin, ettÀ (remainder -2 3) on -2 mutta (modulo -2 3) on 1.
Toinen muistipalautuma on keskustelu jostakin matikkaryhmästä. Joku oli
vaivautunut ottamaan selvää Intelin ratkaisujen perusteluista.
Lähtökohtana oli vaatimus, että jos
a DIV b = q
ja
a MOD b = r,
niin tällöin on oltava voimassa yhtälö a=q*b+r. No niin, sitten joku oli
päättänyt, että sääntö
(-a) DIV b = -(a DIV b)
on tärkeämpi kuin se toive, että laskutoimituksen a MOD b vastaus olisi
aina välillä 0,1,...,b-1. Yhdessä ensimmäisen säännön kanssa tästä
sitten seurasi, että negatiivisen luvun jakojäännös on negatiivinen.
Samaan lopputulokseen johtaa ajattelu, että osamäärää ei pyöristetä
alaspäin vaan "kohti nollaa". Muualla tässä säikeessä esitit määritelmän
a MOD b = a - b* FLOOR(a/b).
Tämä on hyvä määritelmä, mutta sama ongelma tulisi sielläkin, jos jonkun
mielestä olisikin hyvä idea vaatia sääntö FLOOR(-x)=-FLOOR(x).
Ongelmana minulla on pitkälti se, että kun lausekkeen osana esiintyy
"MOD n", niin sen jälkeen selkäydinreaktioni on, että vastaus ei ole
kokonaisluku vaan jäännösluokkarenkaan Z/nZ alkio. Kuten tästä nyt on
varmaan käynyt ilmi, niin taitaa olla ns. "henkilökohtainen ongelma",
joka on vuosien varrella paisunut "pet peeve"-asemaan.
Matkapuhelinstandardeiksi tulleissa kontribuuteissa esiintyi silloin
tällöin seuraavanlaisia hirviöitä (sulut jätetty pois minun toimestani
pointtini korostamiseksi):
a + b mod 320 mod 80 + 3a + b + c mod 80
Siis paitsi merkintä, niin myös sen käyttöön liittyvät
presedenssisäännöt olivat hämäriä. Jouduin ne päättelemään aina
kontekstista erikseen. Lisäksi noissa oli turhia mod:ja. Selvempää olisi
sanoa, että lasketaan renkaassa Z/80Z, jos sitä tarkoitetaan :-)
Cheers,
Jyrki
Matti Rönkä
> Aika mielenkiintoinen juttu tuokin kuitenkin.Väittäisin ettei noita
> modolu-juttuja kovin hyvin osattu edes
> korkeakouluissa 20 vuotta sitten. Nykyään kun on PGP:t ja RSA:t niin
> tällainenkin matematiikka koetaan
> tärkeäksi.
Mjaah, 19 vuotta sitten, kun aloitin matematiikan opiskeluni, nuo
tulivat ihan perusjuttuina vastaan ekan vuoden alkeiskursseilla. Sen
verran tärkeitä perusideoita ne ovat algebrassa ja lukuteoriassa olleet
jo 100+ vuotta.
Matti
Jyrki Lahtonen
> Aika mielenkiintoinen juttu tuokin kuitenkin.Väittäisin ettei noita
> modolu-juttuja kovin hyvin osattu edes
> korkeakouluissa 20 vuotta sitten.
Ehkä jossain B-luokan korkeakoulussa ei osattu?
Nykyään kun on PGP:t ja RSA:t niin
> tällainenkin matematiikka koetaan
> tärkeäksi.
>
> Oma kiva pikku juttunsa tämä kokonaislukujen kanssa värkkääminen.
Lukuteoria lienee vanhimpia matematiikan osa-alueita geometrian kanssa.
Vaikea tietenkin sanoa, mistä kohtaa historian aikajanaa geometria,
lukuteoria, analyysi sun muut alkavat, koska nämähän menevät kaikki
suloisesti päällekkäin monessa kohtaa. Pitkäänhän alan harrastajat
olivat myös sellaisia yleisjantusia.
Gauss "Mathematics is the queen of sciences and arithmetic is the queen
of mathematics" kaiketi piti itseään ensisijaisesti lukuteoreetikkona.
Cheers,
Jyrki
Seppo Miettinen
"Jyrki Lahtonen" <laht...@utu.fi> kirjoitti
viestissä:io0tgn$5dh$1...@news.utu.fi...
> On 11.4.2011 15:10, Matti Lehtiniemi wrote:
>
>> Aika mielenkiintoinen juttu tuokin kuitenkin.Väittäisin ettei noita
>> modolu-juttuja kovin hyvin osattu edes
>> korkeakouluissa 20 vuotta sitten.
Matematiikan ylioppilaskokeisiin kongruenssitehtävät ilmestyivät keväällä
1999, alla on ensimmäinen.
Tehtävä 10 b) 1o Osoita, että kymmenjärjestelmän luku an10n + an-110n-1 +
an-210n-2 + ... + a110 + a0 on jaollinen kolmella, jos ja vain jos a0 + a1 +
a2 + ... + an on jaollinen kolmella.
2o Näytä, että luku 72502 + 21573 on jaollinen kolmella.
Seppo
Seppo Miettinen
Ylä- ja alaindeksöinti katosi. Ehkä pikakorjatusta versiosta alla saa
selvää.
olen pahoillani
seppo
"Seppo Miettinen" <seppo.m...@kolumbus.fi> kirjoitti
viestissä:oNTop.32747$mX5....@uutiset.elisa.fi...
>
> "Jyrki Lahtonen" <laht...@utu.fi> kirjoitti
> viestissä:io0tgn$5dh$1...@news.utu.fi...
>> On 11.4.2011 15:10, Matti Lehtiniemi wrote:
>>
>>> Aika mielenkiintoinen juttu tuokin kuitenkin.Väittäisin ettei noita
>>> modolu-juttuja kovin hyvin osattu edes
>>> korkeakouluissa 20 vuotta sitten.
>
> Matematiikan ylioppilaskokeisiin kongruenssitehtävät ilmestyivät keväällä
> 1999, alla on ensimmäinen.
>
> Tehtävä 10 b) 1^o Osoita, että kymmenjärjestelmän luku a_n10^n +
> a_(n-1)10^(n-1) + a_(n-2)10^(n-2) + ... + a_110 + a_0 on jaollinen
> kolmella, jos ja vain jos a_0 + a_1 + a_2 + ... + a_n on jaollinen
> kolmella.
> 2^o Näytä, että luku 7^2502 + 2^1573 on jaollinen kolmella.
>
> Seppo
>
Ohman
>
> - Näytä siteerattu teksti -
Näin on. Tuon näkee ihan suoraan, sen kummempia laskematta. Lisäksi,
jos n on parillinen ja n>=2, näkee ihan samalla tavalla,että
x^n - 1 = (x^2 - 1) (x^ (n-2) + x^(n-4) +...+x^2 + 1) ja koska x^2 - 1
= (x-1) (x+1), saadaan tuo ylimääräinen tulos, jota Matti Lehtiniemi
nyt ei kaivannut ja jonka esittämistä hän ei pidä suositeltavana:
sitähän ei kysytty!
Ohman
Jyrki Lahtonen
> Matematiikan ylioppilaskokeisiin kongruenssitehtävät ilmestyivät keväällä
> 1999, alla on ensimmäinen.
>
Olet pikkaisen myöhässä. Alla kaksi ensimmäistä tehtävää vuoden 1884
matematiikan ylioppilaskokeesta
===========================================================
Etsi lukujen 989 , 2623 ja 3139 pienin yhteinen jaettava .
Todista , että kaikkien niiden kolminumeroisten lukujen summa , joissa
on samat numerot , on jaollinen 3:lla ja 37:llä sekä numeroiden summalla .
============================================================
Cheers,
Jyrki
Ohman
wrote:
> Hei
>
> Ylä- ja alaindeksöinti katosi. Ehkä pikakorjatusta versiosta alla saa
> selvää.
>
> olen pahoillani
>
> seppo
> viestissä:oNTop.32747$mX5.20...@uutiset.elisa.fi...
>
>
>
>
>
> > "Jyrki Lahtonen" <lahto...@utu.fi> kirjoitti
> > viestissä:io0tgn$5d...@news.utu.fi...
> >> On 11.4.2011 15:10, Matti Lehtiniemi wrote:
>
> >>> Aika mielenkiintoinen juttu tuokin kuitenkin.Väittäisin ettei noita
> >>> modolu-juttuja kovin hyvin osattu edes
> >>> korkeakouluissa 20 vuotta sitten.
>
> > Matematiikan ylioppilaskokeisiin kongruenssitehtävät ilmestyivät keväällä
> > 1999, alla on ensimmäinen.
>
> > Tehtävä 10 b) 1^o Osoita, että kymmenjärjestelmän luku a_n10^n +
> > a_(n-1)10^(n-1) + a_(n-2)10^(n-2) + ... + a_110 + a_0 on jaollinen
> > kolmella, jos ja vain jos a_0 + a_1 + a_2 + ... + a_n on jaollinen
> > kolmella.
> > 2^o Näytä, että luku 7^2502 + 2^1573 on jaollinen kolmella.
>
>
> - Näytä siteerattu teksti -
Alkuperäisen jaollisuustehtävän mukaisesti
7^2502 = 1 mod(6) joten myös on 7^2502 = 1 mod(3)
Samoin on 2^1572 = 1 mod(3) (tuo ML:n ei-suvaitsema kongruenssi)
2=2 mod(3) ja siis 2^1573 = 2 mod(3). Tästä seuraa, että
2^1573 + 7^2502 = 3 mod(3) ja siis 2^1573 + 7^2502 = 0 mod(3) eli luku
3 jakaa tuon summan. mot.
Tuota ensimmäistä 3:lla jaollisuustehtävää en viitsi kommentoida,
selitetäänhän asia varsin monissa kirjoissa.
Ohman
Ohman
Antti Valmari
> (C:tä tunnen huonommin, mutta "%" ei siinä ainakaan ennen ollut
> virallisesti nimeltään modulo vaan remainder, ja taisi siinä olla
> jätetty ikävästi ainakin osittain määrittelemättä, mitä tapahtuu
> negatiivisten lukujen kanssa. Saatan erehtyä.)
C todellakin jättää kaksi vaihtoehtoa osamäärän ja jakojäännöksen
toiminnalle, kun jompikumpi tai molemmat argumentit ovat negatiivisia.
Sentään vaaditaan, että Lahtosen mainitsema jakoyhtälö toteutuu, eli
a = (a/b)*b + (a%b).
Katsoin kahta käsillä olevaa C++-kirjaa, ja kummassakin % oli "modulus"
eikä "reminder". No joo, toisessa oli hakusanastossa "reminder operator
-- see modulus operator".
Muistelen, että osamäärä ja jakojäännös olisivat div ja mod monissa
muissakin kielissä kuin Pascalissa, mm. Adassa, mutta minulla ei ole nyt
käsillä lähteitä, joista voisin tarkastaa asian.
Jyrki Lahtonen kirjoitti:
> Matkapuhelinstandardeiksi tulleissa kontribuuteissa esiintyi
> silloin tällöin seuraavanlaisia hirviöitä (sulut jätetty pois minun
> toimestani pointtini korostamiseksi):
>
> a + b mod 320 mod 80 + 3a + b + c mod 80
>
> Siis paitsi merkintä, niin myös sen käyttöön liittyvät
> presedenssisäännöt olivat hämäriä. Jouduin ne päättelemään aina
> kontekstista erikseen.
Nyt virnuilumoodi päälle ja tarkastelemaan lukiomatematiikkaa. Siellä
näkee usein merkintöjä tyyliin
sin wt
, jolla tarkoitetaan
sin (wt)
. Voimme siis päätellä, että kertolasku sitoo voimakkaammin kuin sin.
Niinpä tuttu kaava
sin 2x = 2 sin x cos x
tarkoittaa
sin (2x) = 2 sin (x cos x)
. Huijasin, todellisuudessahan sin sitoo voimakkaammin kuin kertolasku.
Ym. tuttu kaava tarkoittaa siis
(sin 2)x = 2 (sin x) cos x
. Ja koska toinen derivaatta tarkoittaa derivaatan derivaattaa
d^2 d d
---- f(x) = -- -- f(x)
dx^2 dx dx
, niin on selvää, että
1 = sin^2 x + cos^2 x = sin sin x + cos cos x
.
Ohman kirjoitti:
> Todistin tuolla aiemmin jo sen, että jos n on pariton kokonaisluku
> (n>2) ja k on kokonaisluku (k>1), niin k^n - 1 on jaollinen luvulla k
> - 1. Ja jos n on parillinen (n>= 2), on k^n - 1 jaollinen sekä
> luvulla k - 1 että luvulla k + 1.
> En oikein ymmärtänyt,mihin tuota jatkokestelua tarvittiin tässä
> asiassa. Oliko tarkoitus ehkä valaista asiaa joltain toiselta
> "kantilta"? Vai eikö todistustani ymmärretty?
Todistuksesi ymmärrettiin kyllä, mutta halusin tuoda esiin, että asia on
lukuteorian kannalta paljon yksinkertaisempi kuin siihenastisesta
keskustelusta (todistuksesi mukaan lukien) kävi ilmi. Tuloshan on
lukuteoreetikolle samaa monimutkaisuusluokkaa kuin koululaiselle se,
että olipa n mikä tahansa luonnollinen luku, niin luvun 10n
kymmenjärjestelmäesitys päättyy nollaan. Samalla halusin esitellä
yleisemmän tavan katsoa asiaa, joka tuottaa helpolla monia muitakin
tuloksia kuin todistuksesi.
Se yleisempi tapa katsoa asiaa esitetään todellakin yleensä
kongruenssina ja ekvivalenssiluokkina, kuten Lahtonen teki. Itse käytin
jakojäännöksiä, koska kuvittelin sen olevan helpommin ymmärrettävissä.
--- Antti Valmari ---
Jukka K. Korpela
> Minä sanoisin, että
>
> a = b (mod n)
>
> tarkoittaa samaa kuin
>
> a mod n = b mod n.
>
> Missä on ongelma? Ei ole määritelty, mitä "n mod m" tarkoittaa?
Ainakaan sillä ei ole matematiikassa yleisesti määriteltyä merkitystä.
> No määritellään:
>
> n mod m = n - m floor(n/m) (kun m ei ole 0)
Määritelmä on matemaattisesti hiukan outo, koska kokonaisluvuilla tehtävä
operaatio, joka tuottaa kokonaisluvun, määritellään reaalilukujen jakolaskun
ja reaalilukuargumenttisen funktion (floor) avulla. Sillä n/m tarkoittaa
tässä ilmeisimmin sitä, että n ja m muunnetaan reaaliluvuiksi ja niille
sitten tehdään reaalilukujen jakolasku. Määritelmä olisi parempi esittää
tavalla, joka pysyy turvallisessa kokonaislukujen maailmassa.
> (Jos tarkoitat merkintää "a (mod n)" niin olen samaa mieltä siitä,
> että se on virhe.)
Miksi se olisi virhe? Matematiikassa se esiintyy vanhastaan
kongruenssimerkinnän osana.
Mutta lukiessani joitakin aikoja sitten matematiikkastandardia SFS-ISO
80000-2 (SFS-ISO 31-11:n seuraaja), hämmästyin huomatessani, että sen
suomenkielisen tekstin mukaan ”n = k (mod m)” luetaan ”n on yhtenevä k
modulo m:n kanssa”. Sehän kuulostaa kovasti siltä, että merkinnällä ”k (mod
m)”, luettuna ”k modulo m”, olisi itsenäinen merkitys.
Onkohan kyseessä suomentajan lipsahdus vai tarkoituksellinen ilmaisu? Kaipa
siitä saa mielekkään, jos lähdemme siitä, että ”k (mod m)” ei tarkoitakaan
kokonaislukua luonnollisten lukujen joukon alkiona vaan jäännösluokkarenkaan
Z_m alkiona eli esimerkiksi "12 (mod 5)" ei tarkoita luonnollista lukua 2
vaan tiettyä Z_5:n alkiota, jolloin sen identiteettiin on leivottu sisään
tieto siitä, millaisesta yhtenevyydestä on kyse.
--
Yucca, http://www.cs.tut.fi/~jkorpela/
Ohman
<Antti.Valm...@c.s.t.u.t.f.i.invalid> wrote:
> Jussi Piitulainen kirjoitti:
>
> > (C:t tunnen huonommin, mutta "%" ei siin ainakaan ennen ollut
> > virallisesti nimelt n modulo vaan remainder, ja taisi siin olla
> > j tetty ik v sti ainakin osittain m rittelem tt , mit tapahtuu
> > negatiivisten lukujen kanssa. Saatan erehty .)
>
> C todellakin j tt kaksi vaihtoehtoa osam r n ja jakoj nn ksen
> toiminnalle, kun jompikumpi tai molemmat argumentit ovat negatiivisia.
>
> a = (a/b)*b + (a%b).
>
> eik "reminder". No joo, toisessa oli hakusanastossa "reminder operator
> -- see modulus operator".
>
> muissakin kieliss kuin Pascalissa, mm. Adassa, mutta minulla ei ole nyt
> k sill l hteit , joista voisin tarkastaa asian.
>
> Jyrki Lahtonen kirjoitti:
>
> > Matkapuhelinstandardeiksi tulleissa kontribuuteissa esiintyi
> > toimestani pointtini korostamiseksi):
>
> > a + b mod 320 mod 80 + 3a + b + c mod 80
>
> > presedenssis nn t olivat h m ri . Jouduin ne p ttelem n aina
> > kontekstista erikseen.
>
> Nyt virnuilumoodi p lle ja tarkastelemaan lukiomatematiikkaa. Siell
> n kee usein merkint j tyyliin
>
> sin wt
>
> , jolla tarkoitetaan
>
> sin (wt)
>
> Niinp tuttu kaava
>
> sin 2x = 2 sin x cos x
>
> tarkoittaa
>
> sin (2x) = 2 sin (x cos x)
>
> . Huijasin, todellisuudessahan sin sitoo voimakkaammin kuin kertolasku.
> Ym. tuttu kaava tarkoittaa siis
>
> (sin 2)x = 2 (sin x) cos x
>
> . Ja koska toinen derivaatta tarkoittaa derivaatan derivaattaa
>
> d^2 d d
> ---- f(x) = -- -- f(x)
> dx^2 dx dx
>
>
> 1 = sin^2 x + cos^2 x = sin sin x + cos cos x
>
> .
>
> Ohman kirjoitti:
>
> > (n>2) ja k on kokonaisluku (k>1), niin k^n - 1 on jaollinen luvulla k
> > - 1. Ja jos n on parillinen (n>= 2), on k^n - 1 jaollinen sek
> > En oikein ymm rt nyt,mihin tuota jatkokestelua tarvittiin t ss
> > asiassa. Oliko tarkoitus ehk valaista asiaa joltain toiselta
> > "kantilta"? Vai eik todistustani ymm rretty?
>
> Todistuksesi ymm rrettiin kyll , mutta halusin tuoda esiin, ett asia on
> lukuteorian kannalta paljon yksinkertaisempi kuin siihenastisesta
> lukuteoreetikolle samaa monimutkaisuusluokkaa kuin koululaiselle se,
> kymmenj rjestelm esitys p ttyy nollaan. Samalla halusin esitell
> yleisemm n tavan katsoa asiaa, joka tuottaa helpolla monia muitakin
> tuloksia kuin todistuksesi.
>
> Se yleisempi tapa katsoa asiaa esitet n todellakin yleens
> kongruenssina ja ekvivalenssiluokkina, kuten Lahtonen teki. Itse k ytin
> jakoj nn ksi , koska kuvittelin sen olevan helpommin ymm rrett viss .
>
> --- Antti Valmari ---
Jos sinusta ei ole yksinkertaista se, että x^n - 1 = (x-1) (x^(n-1) +
x^(n-2) + ...+x + 1) (tulos,jonka näkee suoraan sen kummempia
laskematta), en käy kinastelemaan. Esitin asian 1.kerralla vain vähän
toisella lailla. Ja niitä kongruensseja näet vastauksestani Seppo
Miettisen tehtävään.
Aiheetta enempään
Ohman
Jyrki Lahtonen
Jos sinusta ei ole yksinkertaista se, että x^n - 1 = (x-1) (x^(n-1) +
> x^(n-2) + ...+x + 1) (tulos,jonka näkee suoraan sen kummempia
> laskematta), en käy kinastelemaan.
Tuo oli yksinkertaista. Sitä ei kukaan käsittääkseni ole kiistänyt. Ihan
hyvin asian selitit. Mielestäni oli vain vielä rahtusen
yksinkertaisempaa esittää sama asia siinä muodossa, että sopivassa
jäännösluokkarenkaassa 1^n = 1.
Cheers,
Jyrki
Ohman
>
> > x^(n-2) + ...+x + 1) (tulos,jonka n kee suoraan sen kummempia
> > laskematta), en k y kinastelemaan.
>
> Tuo oli yksinkertaista. Sit ei kukaan k sitt kseni ole kiist nyt. Ihan
> hyvin asian selitit. Mielest ni oli vain viel rahtusen
> yksinkertaisempaa esitt sama asia siin muodossa, ett sopivassa
> j nn sluokkarenkaassa 1^n = 1.
>
> Cheers,
>
> Jyrki
Lopetin jo edellisen juttuni sanomalla "Aiheetta enempään". Mutta nyt
kysymykseni ei koske enää varsinaisesti alkuperäistä tehtävää, joten
tohdin sen silti esittää.
"sopivassa jäännösluokkarenkaassa 1^n = 1"
Renkaassa on tunnetusti kaksi laskutoimitusta,joista toista voidaan
kutsua yhteenlaskuksi (mikä tuo toimitus sitten lieneekin) ja toista
vastaavasti kertolaskuksi. Renkaassa saattaa olla kertolaskun 1-
elementti:jokaiselle renkaan elementille a pätee a x 1 = 1 x a = a.
Jos nyt ymmärsin oikein että tuo sinun "1" on renkaan ykköselemennti
ja "potenssiin n" tarkoittaa n-kertaista elementin kertomista
itsellään, niin
1^n = 1 aina, jokaisessa renkaassa, jossa on elementti 1.
Kysymykseni kuuluu: mitä informaatiota tästä perustavaa laatua
olevasta, jokaisen ykkösalkiolla varustetun renkaan toteuttamasta
yhtälöstä, voidaan vetää jaollisuuteen renkaassa (eli esimerkiksi
keskusteluketjun alkuperäisen tehtävän ratkaisemiseen)?
Vai oliko kyseessä painovirhe?
Ei pitkää luentoa renkaista vaan lyhyt vastaus,please.
Terveisin Ohman
Jyrki Lahtonen
> Lopetin jo edellisen juttuni sanomalla "Aiheetta enempään". Mutta nyt
> kysymykseni ei koske enää varsinaisesti alkuperäistä tehtävää, joten
> tohdin sen silti esittää.
Juu. Kuollutta hevosta tässä piiskataan puolin ja toisin.
>
> "sopivassa jäännösluokkarenkaassa 1^n = 1"
>
> Renkaassa on tunnetusti kaksi laskutoimitusta,joista toista voidaan
> kutsua yhteenlaskuksi (mikä tuo toimitus sitten lieneekin) ja toista
> vastaavasti kertolaskuksi. Renkaassa saattaa olla kertolaskun 1-
> elementti:jokaiselle renkaan elementille a pätee a x 1 = 1 x a = a.
<änkyrä>
Algebran kirjoissa rengas määritellään yleensä siten, että siellä tuo
kertolaskun neutraalialkio löytyy. Funktioalgebroissa (ja ehkä jossakin
muuallakin) tuosta luovutaan, mutta esimerkiksi jatko-opiskeluaikanani
käytännössä kanonisoitu Jacobsonin opus vaatii ykkösalkion. Asia tuskin
on loppuunkäsitelty, koska edelleen useat opukset alkavat
erikoismaininnalla: "kaikissa tässä kirjassa esiintyvissä renkaissa
oletetaan olevan ykkösalkio".
</änkyrä>
>
> Jos nyt ymmärsin oikein että tuo sinun "1" on renkaan ykköselemennti
> ja "potenssiin n" tarkoittaa n-kertaista elementin kertomista
> itsellään, niin
>
> 1^n = 1 aina, jokaisessa renkaassa, jossa on elementti 1.
>
> Kysymykseni kuuluu: mitä informaatiota tästä perustavaa laatua
> olevasta, jokaisen ykkösalkiolla varustetun renkaan toteuttamasta
> yhtälöstä, voidaan vetää jaollisuuteen renkaassa (eli esimerkiksi
> keskusteluketjun alkuperäisen tehtävän ratkaisemiseen)?
>
> Vai oliko kyseessä painovirhe?
>
> Ei pitkää luentoa renkaista vaan lyhyt vastaus,please.
Jäännösluokkarenkaassa Z/3Z alkiot ovat ihanteen 3Z sivuluokkia. Koska
luvut 1 ja 4 kuuluvat samaan sivuluokkaan, niiden vastinpotenssitkin
kuuluvat samaan sivuluokkaan (erikoistapaus siitä, että sivuluokkien
kertolasku on "hyvin määritelty"). Siis 4^n ja 1^n ovat samassa
sivuluokassa. Eli niiden erotus on ihanteessa 3Z. Eli se erotus on
kolmella jaollinen. MOT.
Siis kaikki seuraa siitä, että sivuluokkien kertolaskussa (erityisesti
siis potenssissa) voidaan käyttää mitä tahansa sivuluokan alkiota
edustamaan koko porukkaa. Laskun lopputulos ei siitä riipu. Tämä oli
käsittääkseni se, mihin Antti Valmari pyrki (hänen esittämänsä
%-identiteetit sisälsivät juurikin tuon informaation).
Ohman
Olihan pakerrus!Etpäs malttanut olla pitämättä rengasesitelmää,joka ei
edes vastannut kysymykseeni. Ja olikohan tuo nyt yksinkertaisempi
ajatuksenkulku kuin se, että alkuperäisen ongelman ratkaisun näkee
mitään laskemattakin,kuten mainitsin? Kärpäsestä tehtiin taas härkänen
oikein monen kirjoittajan voimin!
Lopetan nyt lopullisesti tämän asian käsittelyn.
Ohman
Jussi Piitulainen
(Minusta tuo pikku esitelmä hyvinkin vastasi kysymykseesi. Ehkä en
ymmärtänyt kysymystä, tai vastausta. Luulen että ymmärsin jotain.)
Täten kuitenkin todistan (en niin kuin matematiikassa vaan niin kuin
silminnäkijänä) omasta puolestani, että minä en nähnyt enkä vieläkään
näe alkuperäisen ongelman ratkaisua mitään laskematta. Nyt näen, että
x^n - 1 = (x - 1)(sum x^k, 0 <= k < n) pitää paikkansa ja vastaa
kysymykseen, mutta kysymyksessä annettiin vain x^n - 1, josta en tuota
toista tekijää osaa suoraan nähdä.
(Tai siis siinä annettiin 4^n - 1, jonka me yleistimme polynomiksi.)
Ramanujan näki kai mitään laskematta luvusta 1729, että se on pienin
positiivinen kokonaisluku, joka voidaan esittää kahden positiivisen
kokonaisluvun kuutioiden summana kahdella eri tavalla. Niin eri me
olemme.
> Lopetan nyt lopullisesti tämän asian käsittelyn.
:-)
(Minun on ollut tarkoitus kommentoida jotain notaatiokeskusteluun.
Saatan sen vielä tehdä, ehkä. Siitä en aio keskustella, oliko
päätökseni jättää ylle tolkuttoman pitkä lainaus oikea vai ei.
Toivottavasti äät eivät säry. Sori.)
Jyrki Lahtonen
> Olihan pakerrus!Etpäs malttanut olla pitämättä rengasesitelmää,joka ei
> edes vastannut kysymykseeni.
No tuo ei kyllä ollut minusta esitelmä :-).
Kävisikö sitten tämä?
Tarkastelut tehdään renkaassa Z/3Z. Tässä renkaassa
4 = 1.
Siispä (n luonnollinen luku)
4^n = 1^n.
Koska kaikissa renkaissa 1^n = 1, niin tässä renkaassa
4^n = 1.
MOT.
Muu lisätekstini (pl. änkyröinti siitä onko renkaalla aina ykkösalkio
vai ei) yritti selittää, mitä tässä renkaassa alkioiden yhtäsuuruus
tarkoittaa, sekä kertoa, että tässä mahdollisesti ensi lukemalla
piilossa olevat askeleet on katettu siinä Antti Valmarin ensimmäisessä
viestissä.
Cheers,
Jyrki
Jyrki Lahtonen
> Kysymykseni kuuluu: mitä informaatiota tästä perustavaa laatua
> olevasta, jokaisen ykkösalkiolla varustetun renkaan toteuttamasta
> yhtälöstä, voidaan vetää jaollisuuteen renkaassa (eli esimerkiksi
> keskusteluketjun alkuperäisen tehtävän ratkaisemiseen)?
Pahus. Pyydän anteeksi. Luulin, että koko ajan keskityttiin siihen
alkuperäiseen kolmellajaollisuuskysymykseen. Yleisemmin kongruenssit
renkaassa menevät jonkin ihanteen suhteen. Tulos, joka tuosta
identiteetistä irtoaa on tietenkin se, että jos I on renkaan R ihanne,
ja a sen jokin alkio, ja
a = 1 (mod I),
niin tällöin myös
a^n = 1^n = 1 (mod I).
Jaollisuustulokseksi tämä kääntyy silloin, kun ihanne I on pääihanne,
eli yhden alkion, sanokaamme p, generoima. Tällöin tuo kääntyy
implikaatioksi:
(a-1) on jaollinen alkiolla p => (a^n-1) on jaollinen alkiolla p
Koko säikeen alkuna ollut ongelma on tästä erikoistapaus: R=Z, I=3Z,
p=3, a=4. Käyttämäsi polynomien jaollisuustulos vastaa erikoistapausta
R=polynomirengas, vaikkapa C[x], I=niiden polynomien f(x) muodostama
ihanne, joille f(1)=0, p=x-1, a=x, jolloin identiteetit 1^n=1 (mod I)
ja x=1 (mod I) siis jo takaavat, että x-1 on polynomin x^n-1 tekijä.
Rengasajattelusta saadaan tässä yhteydessä se säästö, ettei tarvitse
keksiä noita tekijöihinjakoja. Riittää kun tarkistaa, että
jäännösluokkarenkaassa kertolasku on hyvin määritelty. Tämä taas tehdään
sillä ensimmäisen vuoden algebran peruskurssilla yleisesti yhdessä
rysäyksessä kaikille renkaille ja ihanteille. Yllä viimeisessä
esimerkissä siis ei tarvitse erikseen keksiä, että geometrisen sarjan
summakaavahan tässä toimii (ellei erityisesti sitten tarvitse sitä
toista tekijää johonkin).
Vai menikö tämä sitten luennoinnin puolelle :-)
Cheers,
Jyrki
Antti Valmari
>> >> Ai perhana, mutta tämähän on erikoistapaus.
>> >> Siis 6*6 -1 on jaollinen viidellä, 7*7-1 on jaollinen kuudella jne...
> >
> > Siis mitä helvettiä.
> > 6*6*6-1 on jaollinen viidellä. 6*6*6*6 -1 on jaollinen viidellä.
Jussi Piitulainen wrote:
> Täten kuitenkin todistan (en niin kuin matematiikassa vaan niin kuin
> silminnäkijänä) omasta puolestani, että minä en nähnyt enkä vieläkään
> näe alkuperäisen ongelman ratkaisua mitään laskematta. Nyt näen, että
> x^n - 1 = (x - 1)(sum x^k, 0 <= k < n) pitää paikkansa ja vastaa
> kysymykseen, mutta kysymyksessä annettiin vain x^n - 1, josta en tuota
> toista tekijää osaa suoraan nähdä.
Kuulostan nyt imelältä myyntimieheltä, mutta en keksinyt parempaakaan
tapaa ilmaista asia selvästi: tarjolla on yksinkertainen, helposti
opittava ajattelumalli, jonka omaksumisen jälkeen yllä mainittujen
ongelmien ratkaisut näkee erittäin vähällä laskemisella. Eikö se
kannattaisi opetella? (Kirjoitin "erittäin vähällä laskemisella", koska
"mitään laskematta" on niin voimakas ilmaus, että kirjaimellisesti
tulkittuna se toteutuu tuskin koskaan.)
Jyrki Lahtonen on selittänyt asian jäännösluokkarenkaiden ym. käsittein,
mutta itse muistan kokeneeni ne aluksi kovin abstrakteiksi. Sen takia
esitin asian jakojäännösten käsittein, koska silloin ei tarvitse
ajatella uudenlaisia lukuja. Samasta asiasta siinä on silti kyse.
Asian ydin on siis siinä, että jos laskutoimituksina on vain yhteen-,
vähennys- ja kertolaskuja, ja ollaan kiinnostuneita jakojäännöksistä
jaettaessa m:llä, niin voidaan laskea ikään kuin 1 ja m+1 olisivat sama
luku. Jos halutaan tarkastaa, onko 6*6*6*6-1 jaollinen viidellä, niin
riittää laskea sen jakojäännös viidellä jaettaessa. Tämän laskun
kannalta 1, 6, 11, ... ovat samoja lukuja. Pitää siis laskea onko
1*1*1*1-1 jaollinen viidellä. Siinä ei ole juuri mitään laskemista.
Ajattelumallilla ratkoo helposti myös tehtäviä tyyliin "onko 1234^5678 +
8765^4321 jaollinen 9:llä". Se on osana myös isompien ongelmien
ratkaisua, mutta en anna nyt esimerkkiä, koska isoissa ongelmissa
tarvitaan muutakin ja teksti venyisi pitkäksi.
> Ramanujan näki kai mitään laskematta luvusta 1729, että se on pienin
> positiivinen kokonaisluku, joka voidaan esittää kahden positiivisen
> kokonaisluvun kuutioiden summana kahdella eri tavalla. Niin eri me
> olemme.
Siinä muodossa kuin tuon anekdootin olen kuullut, on täysin mahdollista,
että Ramanujan osasi tuloksen ulkoa ja siis poimi sen muististaan sen
sijaan että olisi laskenut sen sillä hetkellä tai nähnyt suoraan.
--- Antti Valmari ---
Jussi Piitulainen
> Matti Lehtiniemi wrote:
> >> >> Ai perhana, mutta tämähän on erikoistapaus.
> >> >> Siis 6*6 -1 on jaollinen viidellä, 7*7-1 on jaollinen kuudella jne...
> > >
> > > Siis mitä helvettiä.
> > > 6*6*6-1 on jaollinen viidellä. 6*6*6*6 -1 on jaollinen viidellä.
>
> Jussi Piitulainen wrote:
> > Täten kuitenkin todistan (en niin kuin matematiikassa vaan niin kuin
> > silminnäkijänä) omasta puolestani, että minä en nähnyt enkä vieläkään
> > näe alkuperäisen ongelman ratkaisua mitään laskematta. Nyt näen, että
> > x^n - 1 = (x - 1)(sum x^k, 0 <= k < n) pitää paikkansa ja vastaa
> > kysymykseen, mutta kysymyksessä annettiin vain x^n - 1, josta en tuota
> > toista tekijää osaa suoraan nähdä.
(Yllä lainattu tekstini ei ollut vastaus yllä lainattuun alkuperäiseen
kysymykseen vaan muuhun keskustelussa esiin tulleeseen väitteeseen.)
> Kuulostan nyt imelältä myyntimieheltä, mutta en keksinyt parempaakaan
> tapaa ilmaista asia selvästi: tarjolla on yksinkertainen, helposti
> opittava ajattelumalli, jonka omaksumisen jälkeen yllä mainittujen
> ongelmien ratkaisut näkee erittäin vähällä laskemisella. Eikö se
> kannattaisi opetella? (Kirjoitin "erittäin vähällä laskemisella", koska
> "mitään laskematta" on niin voimakas ilmaus, että kirjaimellisesti
> tulkittuna se toteutuu tuskin koskaan.)
...
> Asian ydin on siis siinä, että jos laskutoimituksina on vain yhteen-,
> vähennys- ja kertolaskuja, ja ollaan kiinnostuneita jakojäännöksistä
> jaettaessa m:llä, niin voidaan laskea ikään kuin 1 ja m+1 olisivat sama
> luku. Jos halutaan tarkastaa, onko 6*6*6*6-1 jaollinen viidellä, niin
> riittää laskea sen jakojäännös viidellä jaettaessa. Tämän laskun
> kannalta 1, 6, 11, ... ovat samoja lukuja. Pitää siis laskea onko
> 1*1*1*1-1 jaollinen viidellä. Siinä ei ole juuri mitään laskemista.
Minä ainakin olen kiinnostunut. Olisin varmaan alun perin nähnytkin
ongelman näin, jos olisin jo osannut tarpeeksi.
Toisaalta, jos olisin hallinnut polynomit tarpeeksi hyvin, olisin ehkä
"nähnyt" molemmat tekijät heti sen sijaan, että jouduin niitäkin vähän
ajattelemaan ja jopa katsomaan jotain kirjasta.
Mutta joo, harrastan varmasti asiaa vähän, kunhan kerkiän. Paljosta
työstä ei näytä olevan kyse. Kirjahan minulla jo onkin.
> > Ramanujan näki kai mitään laskematta luvusta 1729, että se on pienin
> > positiivinen kokonaisluku, joka voidaan esittää kahden positiivisen
> > kokonaisluvun kuutioiden summana kahdella eri tavalla. Niin eri me
> > olemme.
>
> Siinä muodossa kuin tuon anekdootin olen kuullut, on täysin mahdollista,
> että Ramanujan osasi tuloksen ulkoa ja siis poimi sen muististaan sen
> sijaan että olisi laskenut sen sillä hetkellä tai nähnyt suoraan.
Olet varmaan oikeassa. Silti: tarkoitin tässä juuri sitä, että
sellaiset asiat "näkee" helpommin, mitkä tuntee hyvin jo ennestään.
Jyrki Lahtonen
muistilokeroista löytyi vanha demotehtävä (koskahan minut mahdetaan taas
päästää luennoimaan 1. vuoden algebraa?).
A) Tarkista, että 100000 = 1 renkaassa Z/41Z (eli 41 jakaa luvun
100000-1). Vinkki: tässäkään ei välttämättä tarvita kuin 3-numeroisilla
luvuilla operointia, joten tosiharrastajalle tämä on päässälasku.
B) Laske 30-numeroisen luvun 14159 26535 89793 23846 26433 83279
jakojäännös jaettaessa luvulla 41.
Vinkki: A-kohdan perusteella riittää (selitä miksi!) laskea luvun
14159+26535+89793+23846+26433+83279 jakojäännös, mikä jo mahtuu
peruslaskimeen. Vinkki opettajalle: jos laskinten kehitys tekee
tehtävästä tulevaisuudessa liian helpon, niin pidennä tutkittavaa lukua
ilmeisellä tavalla.
Vielä "vakuuttavampi" demotehtävä on todistaa, että Fermat'n luku 2^32+1
on jaollinen luvulla 641. Vinkki: 641=5*2^7+1=5^4+2^4.
Cheers,
Jyrki
Antti Valmari
Autokorjaamo haluaa tallettaa autojen tietoja niin, että tiedot löytyvät
rekisterinumeron perusteella. Erilaisia rekisterinumeroita on
suuruusluokkaa parikymmentä miljoonaa (en ole varma, mitkä kaikki
kirjaimet ovat käytössä), mutta korjaamolla on asiakkaita alle 10 000.
Käytössä on Commodore 64, joten ei voida varata talletustilaa miljoonien
autojen tiedoille.
Yksi mahdollisuus on käyttää ns. avoimen osoituksen hajautustaulua ns.
neliöllisellä luotauksella. Varataan taulukko, jossa on 16 384 (= 2^14)
lokeroa. Kussakin lokerossa on yhden auton tiedot tai lokero on tyhjä.
Keksitään ns. hajautusfunktio, joka ottaa vastaan rekisterinumeron ja
tuottaa siitä välillä 0, 1, ..., 16 383 olevan kokonaisluvun. Uuden
auton tiedot yritetään ensisijaisesti tallettaa tämän luvun ilmaisemaan
lokeroon. Jos se on jo varattu, siirrytään seuraavaan lokeroon, paitsi
viimeisestä lokerosta siirrytään ensimmäiseen. Jos sekin on varattu,
siirrytään kaksi askelta eteenpäin (taas tarvittaessa hypäten alkuun),
sitten kolme askelta jne.
Hajautusfunktiot ovat oma taiteenlajinsa, mutta olennaista niissä on,
että hajautusfunktio räiskii ensimmäiset yritykset hujan hajan ympäri
taulukkoa. Rekisterinumeroille on helppo keksiä riittävän hyvä
hajautusfunktio, mutta en mene nyt siihen.
Syy yritysten välimatkan kasvatukseen on, että ilman sitä syntyisi
pitkiä yhtenäisiä varattuja alueita, joiden selaaminen on hidasta.
Askeleen kasvattaminen lieventää tehokkaasti tätä ilmiötä. Tämän
tarkempi pohdinta olisi hauskaa sekin, mutta pysykäämme alkuperäisessä
aiheessamme. Etsintätavasta riippumatta etsinnästä tulee lopulta liian
hidasta jos taulukko täytetään liian täyteen, mutta hyvin toteutetulla
taulukolla esimerkiksi 80 % täyttöaste on ihan ok.
Jos taulukon koko olisi 10 eli lokeroiden numerot olisivat 0, 1, ..., 9,
ja jos ensimmäinen yritys osuisi lokeroon 0, niin seuraavat yritykset
osuisivat lokeroihin 1, 3, 6, 0 (saatiin 10, aloitetaan alusta), 5, 1,
8, 6, 5, 5, 6, 8, 1, 5, 0, 6, 3, 1, 0, 0, 1, 3, ... Huomaamme, että
lokeroita 2, 4, 7, ja 9 ei kokeilla lainkaan tai ainakaan 23:lla
ensimmäisellä kokeella ei osuta niihin. Näin ollen uuden auton tietojen
talletus saattaa epäonnistua, vaikka 40 % taulukon paikoista on vapaina.
Huomaamme myös, että viides kokeilu kokeilee uudelleen paikkaa 0, joka
on jo kokeiltu. Tarvitaan 8 kokeilua että kaikki 6 eri paikkaa saadaan
kokeiltua.
Jos taulukon koko olisi 16, niin yritykset osuisivat lokeroihin 0, 1, 3,
6, 10, 15, 5, 12, 4, 13, 7, 2, 14, 11, 9, 8, 8, 9, 11, 14, 2, 7, 13, 4,
12, 5, 15, 10, 6, 3, 1, 0, 0, 1, 3, 6, ... Huomaamme, että kokeiltiin
kaikki lokerot 0, 1, ..., 15 ennen kuin mitään lokeroa kokeiltiin
toistamiseen. Etsintä on siis niin tehokasta kuin voi toivoa.
Tarinan alun perusteella voi arvata, että etsintä sujuu onnekkaasti myös
kun taulukon koko on 16 384. Itse asiassa se sujuu onnekkaasti aina kun
taulukon koko on kahden potenssi. Todista tämä!
Saattaa olla, että ratkaisussa tarvitaan muutakin kuin
jakojäännösajattelua, mutta ainakin jakojäännösajattelu on keskeisessä
asemassa.
--- Antti Valmari ---
Jussi Piitulainen
> Jos haetaan vielä hiukan ehkä "vakuuttavampi" esimerkki, niin
> muistilokeroista löytyi vanha demotehtävä (koskahan minut mahdetaan
> taas päästää luennoimaan 1. vuoden algebraa?).
>
> A) Tarkista, että 100000 = 1 renkaassa Z/41Z (eli 41 jakaa luvun
> 100000-1). Vinkki: tässäkään ei välttämättä tarvita kuin
> 3-numeroisilla luvuilla operointia, joten tosiharrastajalle tämä on
> päässälasku.
10^5 = 1 (mod 41) johtaa siihen, että
(10 mod 41)^5 = 1 (mod 41), eli ei mihinkään.
(100)(100)(10) = 1 (mod 41) johtaa siihen, että
(18)(18)(10) = 1 (mod 41) eli
(18)(2)(90) = 1 (mod 41) eli
(18)(2)(8) = 1 (mod 41) eli
(80 + 64)(2) = 1 (mod 41) eli
(39 + 23)(2) = 1 (mod 41) eli
(41 + 21)(2) = 1 (mod 41) eli
(21)(2) = 1 (mod 41) minkä jo näenkin.
Toisaalta voisin lähteä vähentämään 41:n helppoja monikertoja näin:
99999 - 82000 = 17999, ja nyt jo huolestun siitä, laskinko oikein.
> B) Laske 30-numeroisen luvun 14159 26535 89793 23846 26433 83279
> jakojäännös jaettaessa luvulla 41.
> Vinkki: A-kohdan perusteella riittää (selitä miksi!) laskea luvun
> 14159+26535+89793+23846+26433+83279 jakojäännös, mikä jo mahtuu
> peruslaskimeen. Vinkki opettajalle: jos laskinten kehitys tekee
> tehtävästä tulevaisuudessa liian helpon, niin pidennä tutkittavaa
> lukua ilmeisellä tavalla.
Nah. Jos kerran laskinta saa käyttää, niin käytän sitten kunnollista
laskinta:
> (modulo 141592653589793238462643383279 41)
5
> (quotient 141592653589793238462643383279 41)
3453479355848615572259594714
> (+ (* 3453479355848615572259594714 41) 5)
141592653589793238462643383279
Minulle tämmöinen tehtävä on ensisijaisesti turhauttava harjoitus
numerojonon kopioimisessa. Se ei tunnu minusta reilulta minua kohtaan.
Vähän kuin Liisan kohtalo ihmemaassa: "Paljonko on yksi plus yksi plus
yksi plus yksi plus yksi plus yksi plus yksi plus yksi plus yksi plus
yksi." "En pysynyt mukana". "Hän ei osaa laskea!"
Vinkki oli hyvä, ja näen miksi, joten opin jotain. Kiitos tästä.
Harjoittelin sitten julkisesti.
> Vielä "vakuuttavampi" demotehtävä on todistaa, että Fermat'n luku
> 2^32+1 on jaollinen luvulla 641. Vinkki: 641=5*2^7+1=5^4+2^4.
Missähän minulla voisi olla tarvetta osata näitä? Salakirjoitusta en
harrasta, mutta satunnaislukugeneraattoreita olisi ehkä kiva ymmärtää.
Ohjelmoidessa on tarjolla vain se lukujen jakojäännösoperaattori, ei
näitä jäännösluokkarenkaita vai mitä ne nyt ovat. Siis jos lukuteoria
sinänsä ei ole kiinnostuksen kohde, niin onko tämä lähinnä tapa tehdä
helposti asioita, joita minulla ei ole tarvetta tehdä?
(En tarkoita provosoida. Kysyn, kun en tiedä. Ehkä vastaus kävelee
jossain vastaan, kun kysymys on herännyt.)
Jyrki Lahtonen
> Vinkki oli hyvÀ, ja nÀen miksi, joten opin jotain. Kiitos tÀstÀ.
> Harjoittelin sitten julkisesti.
Hei, tämä metodi toimi paremmin kuin änkyröinti! Ehkä minäkin opin jotain?
>
>> VielÀ "vakuuttavampi" demotehtÀvÀ on todistaa, ettÀ Fermat'n luku
>> 2^32+1 on jaollinen luvulla 641. Vinkki: 641=5*2^7+1=5^4+2^4.
>
> MissÀhÀn minulla voisi olla tarvetta osata nÀitÀ? Salakirjoitusta en
> harrasta, mutta satunnaislukugeneraattoreita olisi ehkÀ kiva ymmÀrtÀÀ.
> Ohjelmoidessa on tarjolla vain se lukujen jakojÀÀnnösoperaattori, ei
> nÀitÀ jÀÀnnösluokkarenkaita vai mitÀ ne nyt ovat. Siis jos lukuteoria
> sinÀnsÀ ei ole kiinnostuksen kohde, niin onko tÀmÀ lÀhinnÀ tapa tehdÀ
> helposti asioita, joita minulla ei ole tarvetta tehdÀ?
Ensimmäisen demotehtävän tarkoitus oli lähinnä näyttää kummoisia
yleistyksiä tuolla koulusta tutulla yhdeksällä (tai kolmella)
jaollisuussäännöllä on. Ei tuossa tietenkään mitään syvällistä ollut.
> (En tarkoita provosoida. Kysyn, kun en tiedÀ. EhkÀ vastaus kÀvelee
> jossain vastaan, kun kysymys on herÀnnyt.)
Tuolla jälkimmäisellä tehtävällä on ennen kaikkea historiallista
mielenkiintoa. Fermat kuulemma otaksui, että kaikki muotoa 2^2^n+1 oleva
luvut ovat alkulukja. Hän tarkisti asian, kun n=0,1,2,3,4 jolloin
saadaan 3,5,17,257 ja 65537. No, tällä kertaa Fermat'n otaksunta ei
toiminut, koska tuosta eteenpäin ei yhtään alkulukua ole löytynyt.
Muistaakseni kysymys toki on auki jollakin arvolla n<25 (tai jotain
tuota suuruusluokkaa). Euler oli ensimmäinen, joka löysi tuon luvun
2^32+1 tekijän 641. Käyttämällä tuota Ohmanin posteissa monta kertaa
esiintynyttä polynomien tekijöihinjakoa nähdään helposti, että muotoa
2^m+1 oleva luku voi olla alkuluku vain, jos m on kakkosen potenssi.
Muuhun matematiikkaan tuo liittyy kaiketi lähinnä sen Gaussin tuloksen
kautta (ainakin ensimmäiset erikoistapaukset hän kuulemma selvitti
17-kesäisenä), että säännöllinen m-kulmio on harppi/viivoitin
konstruoitavissa tarkalleen silloin, kun m=2^k*p_1*p_2*...*p_r, missä
luvut p_i ovat kaikki muotoa 2^2^n+1 olevia, keskenään eri suuria
alkulukuja. Tuosta voisin pitää vaikka luennon, mutta löytyyhän se myös
kirjoista eikä kapakka ole vielä auki.
Cheers,
Jyrki
Jyrki Lahtonen
> 10^5 = 1 (mod 41) johtaa siihen, ettÀ
Kun näin laskit oikein, että n=5 on pienin positiivinen kokonaisluku,
jolle 10^n = 1 (mod 41), niin jatkotehtävänä voi vielä tehdä itselleen
selväksi, miten tämä ilmenee luvun 1/41 desimaalikehitelmässä?
Cheers,
Jyrki