Voisikohan joku antaa todistuksen sille että kaikista luvuista pystyy muodostamaan yksikäsitteisen alkulukuhajotelman.
Alkulukuhajotelma
Lapanen
182971
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 18
Vanhimmat
"Voisikohan joku antaa todistuksen sille että kaikista luvuista pystyy muodostamaan yksikäsitteisen alkulukuhajotelman."
Tuskin, koska väitteesi on epätosi.
Väite: Alkulukuhajotelmaa ei pysty muodostamaan kaikista luvuista.
Tod: Otetaan luku x = π (pi). Tätä ei pysty ilmaisemaan minkään alkulukujen tulona, m.o.t.
Tarkoituksena oli pyytää todistus sille että kaikista (positiivisista) kokonaisluvuista voidaan muodostaa alkulukuhajotelma.
Tuon todistuksen (lemmoineen) löytää mistä tahansa lukuteorian alkeisesityksestä tai vaikkapa googlettamalla. Koitapa etsiä ensin itse. Jos ei löydy, niin apua tietysti saa.
En loydä todistusta...Enkä suoraan sanottuna haluakaan etsiä mitään Wolframin esittämää sekavaa englanninkielistä todistusta vaan mahdollisimman yksinkertaista "kansantajuista" suomenkielistä versiota..
> En loydä todistusta...
Et vain etsi oikeilla hakusanoilla. Aika nopeasti käyttämällä hakusanoja "prime", "number", "decomposition", "integer" ja "product" selviää, että lausetta kutsutaan englanniksi nimellä "Fundamental theory of arithmetic". Etsimällä tällä löytää enemmän ja vähemmän hyviä todistuksia vaikka kuinka monta.
> Enkä suoraan sanottuna haluakaan etsiä mitään Wolframin
> esittämää sekavaa englanninkielistä todistusta
Se on sitten oma häpeäsi, ellet ymmärrä todistusta. Matematiikassa ei ole suurta väliä, onko todistus englanniksi vai suomeksi, kun matemaattiset merkinnät ovat kuitenkin enimmäkseen (de facto) standardeja. Parin tuntemattoman sanan etsiminen sanakirjasta on paljon helpompaa kuin koko todistuksen löytäminen suomenkielisenä.
Kaikkia asioita ei myöskään voida todistaa niin yksinkertaisesti, että kaikki asiaan perehtymättömätkin voisivat ymmärtää todistuksen kuin vettä vain. Tämä alkulukuhajotelman todistus on kyllä aika yksinkertainen.
> mahdollisimman yksinkertaista "kansantajuista" suomenkielistä versiota..
Wikipediasta löytyy englanniksi aika selkeä sanallinen todistus:
http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
"Suppose there were a positive integer which can not be written as a product of primes. Then there must be a smallest such number: let's call it n. This number n cannot be 1, because of our convention above. It cannot be a prime number either, since any prime number is a product of a single prime, itself. So n = ab where both a and b are positive integers smaller than n. Since n was the smallest number for which the theorem fails, both a and b can be written as products of primes. But then n = ab can be written as a product of primes as well, a contradiction"
Ylläoleva todistus vähän ihmetyttää. Tuntuu että tuolla tavalla voisi todistaa minkä asian tahansa tässä maailmassa.Esimerkki:
Todista että kaikki kokonaisluvut ovat kolmella jaollisia.
Todistus:
vasta-oletus: on olemassa ainakin yksi luku joka ei ole jaollinen kolmella. Olkoon pienin tällainen luku n. Nyt n=ab, jossa a ja b ovat n:ää pienempiä kokonaislukuja. Mutta nyt a ja b ovat molemmat kolmella jaollisia lukuja oletuksen perusteella joten myös luku n on kolmella jaollinen-->ristiriita
-->kaikki luvut ovat kolmella jaollisia.
Höpön löpön, pienin kolmella jaoton positiivinen kokonaisluku on yksi, eikä sitä voida lausua kahden sitä pienemmän positiivisen kokonaisluvun tulona.
"Höpön löpön, pienin kolmella jaoton positiivinen kokonaisluku on yksi, eikä sitä voida lausua kahden sitä pienemmän positiivisen kokonaisluvun tulona"
Ihanko totta? Kiitoksia paljon tiedosta.
Pointtini oli jossain ihan muualla. Mitäpä jos tarkastelemme lukuja jotka ovat suurempia kuin 1 emmekä tiedä mikä on seuraava mahdollisesti kolmella jaoton luku?
> Ylläoleva todistus vähän ihmetyttää.
Kieltämättä sen joutuu lukemaan tarkasti ja miettimään lause lauseelta, mutta minusta se on kyllä ihan pätevä. Voin koettaa vielä selventää sitä:
1) Merkitään pienintä positiivista kokonaislukua, jota ei voida kirjoittaa alkulukujen tulona, n:llä.
2) Triviaalisti "nähdään", että n ≠ 1 ja että n ei voi olla mikään alkuluku.
3) Merkitään nyt n = ab, missä a ja b ovat n:ää pienempiä kokonaislukuja. Sekä a että b voidaan kirjoittaa alkulukujen tulona, koska pienen luku, jota EI voitu kirjoittaa alkulukujen tulona, on n. Koska n ei voinut olla alkuluku, se on mahdollista kirjoittaa joidenkin sitä pienempien kokonaislukujen tulona.
4) Koska a ja b voidaan kirjoittaa alkulukujen tulona, myös tulo n = ab voidaan kirjoittaa alkulukujen tulona, mikä on ristiriidassa kohdan 1 kanssa.
"vasta-oletus: on olemassa ainakin yksi luku joka ei ole jaollinen kolmella. Olkoon pienin tällainen luku n. Nyt n=ab, jossa a ja b ovat n:ää pienempiä kokonaislukuja. Mutta nyt a ja b ovat molemmat kolmella jaollisia lukuja oletuksen perusteella"
Tämä kaatuu mielestäni siihen, että mitä tahansa positiivista kokonaislukua n EI voida kirjoittaa kahden sitä pienemmän kokonaisluvun (≠1) tulona (nimittäin jos kyseessä on alkuluku). Alkulukuhajotelman todistuksessa tiedetään, että n ei voi olla alkuluku, joten n voidaan esittää muodossa n = ab.
Hyvä yritys kuitenkin, kyllä tuo jollekin varmaan läpi menee.. ;-)
Olen pahoillani, viestini taisi vaikuttaa hieman ylimieliseltä. Se ei ollut tarkoitus. Menetelmäsi ongelma on siinä, että tiedät, mikä on pienin ykköstä suurempi kolmella jaoton luku: 2. Sen sijaan et tiedä, mikä on pienin luku, jolla ei ole esitystä alkutekijöiden tulona, sillä sellaista ei ole. Et voi käyttää vastaoletuksena väitettä, joka tunnetaan todeksi.
"vasta-oletus: on olemassa ainakin yksi luku joka ei ole jaollinen kolmella. Olkoon pienin tällainen luku n. Nyt n=ab, jossa a ja b ovat n:ää pienempiä kokonaislukuja. Mutta nyt a ja b ovat molemmat kolmella jaollisia lukuja oletuksen perusteella"
"Tämä kaatuu mielestäni siihen, että mitä tahansa positiivista kokonaislukua n EI voida kirjoittaa kahden sitä pienemmän kokonaisluvun (≠1) tulona (nimittäin jos kyseessä on alkuluku)"
Mutta mitä tapahtuukaan jos tarkastelemme kaikkia niitä kokonaislukuja jotka eivät ole alkulukuja? Tällöin ne ovat vasta-oletuksen ristiriitaisuuden perusteella kaikki kolmella jaollisia...?!?
Toinen lapanen: "Mutta mitä tapahtuukaan jos tarkastelemme kaikkia niitä kokonaislukuja jotka eivät ole alkulukuja?"
Kun käyt läpi mahdolliset vaihtoehdot pienimmän kolmella jaottoman ei-alkuluvun n tekijöille a ja b, huomaat lukujen a ja b olevan joko
* välttämättä molemmat alkulukuja tai
* toisen olevan 1 ja toisen n itse.
Ei minkäänlaista ristiriitaa kummassakaan tapauksessa.
"Todista että kaikki kokonaisluvut (alkulukuja lukuunottamatta) ovat kolmella jaollisia.
Todistus:
vasta-oletus: on olemassa ainakin yksi luku joka ei ole jaollinen kolmella. Olkoon pienin tällainen luku n. Nyt n=ab, jossa a ja b ovat n:ää pienempiä kokonaislukuja. Mutta nyt a ja b ovat molemmat kolmella jaollisia lukuja oletuksen perusteella joten myös luku n on kolmella jaollinen-->ristiriita
-->kaikki luvut ovat kolmella jaollisia. "
"Kun käyt läpi mahdolliset vaihtoehdot pienimmän kolmella jaottoman ei-alkuluvun n tekijöille a ja b, huomaat lukujen a ja b olevan joko"
Mutta kun tässä tilanteessa ei tiedetä mikä on pienin kolmella jaoton luku. Millä perusteella sitä sitten alat tarkastelemaan?
Fakta tässä on se että
1)n on pienin kolmella jaoton luku
2)a ja b ovat n:ää pienempiä ja siis oletuksen perusteella molemmat kolmella jaollisia
--> n:n täytyy olla kolmella jaollinen
-->ristiriita.
"Mutta kun tässä tilanteessa ei tiedetä mikä on pienin kolmella jaoton luku."
Esitetään siis jokin arvaus. Valitaan jokin kolmella jaoton positiivinen kokonaisluku luku m, joka ei myöskään ole alkuluku eikä 1. Tutkitaan todistuksesi mukaisesti, olisiko m pienin kolmella jaoton luku, ts. n = m?
"1)n on pienin kolmella jaoton luku
2)a ja b ovat n:ää pienempiä ja siis oletuksen perusteella molemmat kolmella jaollisia"
m ei ole alkuluku, joten se voidaan kirjoittaa muodossa m = ab. Koska m ei ollut kolmella jaollinen, myöskään a tai b eivät voi olla kolmella jaollisia. Näin ollen m ei voi olla pienin kolmella jaoton luku, ts. pätee n < m.
Olisiko sitten n = min{a, b}? Iteroidaan vain uudelleen ja uudelleen ja havaitaan, että n:n on pakko olla jokin alkuluku. Sijoitetaan tämä saatu N todistukseesi ja havaitaan, että vastaoletus pätee arvolla N ja että myös oletus "olkoon pienin tällainen luku n" pätee, kun n = N.
En sitten tiedä, oliko tuosta juuri hyötyä... ;-)
"vasta-oletus: on olemassa ainakin yksi luku joka ei ole jaollinen kolmella. Olkoon pienin tällainen luku n."
Minun ei kyllä tarvitse tietää pienintä lukua n, koska voin näyttää vastaoletuksen todeksi löytämällä minkä tahansa kolmella jaottoman luvun. Vastaoletus on siis tosi, koska 4 ei ole jaollinen kolmella => väite on epätosi.
Todistukset, joissa yhden esimerkin x löytäminen riittää todistamaan asian Y todeksi (todista, että jollakin x pätee Y) tai joissa vastaesimerkillä x näytetään Y epätodeksi (Y ei päde kaikilla X, koska se ei päde x:llä), ovat yleensä paljon helpompia kuin todistukset, joissa pitää näyttää asia todeksi tai epätodeksi kaikilla parametrin arvoilla.
"Mutta kun tässä tilanteessa ei tiedetä mikä on pienin kolmella jaoton luku."
Mutta juuri tähän tietoonhan vastaoletuksesi perustuu: oletetaan, että tiedetään pienimmän kolmella jaottoman ei-alkuluvun olevan n.
Selitän asian nyt juurta jaksaen. Yritetään siis osoittaa vastaoletuksen avulla, että jokainen luonnollinen luku alkulukuja lukuunottamatta on jaollinen kolmella.
Oletetaan, että olisi kuitenkin kolmella jaottomia ei-alkulukuja, joista n on pienin. Koska n ei ole alkuluku, voidaan se kirjoittaa muodossa ab, jossa a, b < n, kunhan vain n ei ole yksi. Jos n = 1, on selvää ettei todistusta voi viedä tällaisenaan läpi, joten oletetaan, että n ei ole 1. (Tämä lisäoletus on täysin laillinen, sehän vain täsmentää väitettä.)
Nyt on neljä mahdollisuutta. Käydään läpi nämä vaihtoehdot ja huomataan vain yhden olevan mahdollinen:
(1) Luvut a ja b eivät ole alkulukuja. Koska a, b < n, täytyy kolmosen jakaa kummatkin luvut a ja b. Tämä ei ole mahdollista, sillä n oli pienin kolmella jaoton. Siis vaihtoehto (1) ei käy.
(2) Toinen luvuista a ja b on 1, toinen n itse. Kuitenkin piti olla a, b < n, joten tämä vaihtoehto (2) ei käy.
(3) Toinen luvuista a ja b on alkuluku, toinen ykkösestä eroava muttei alkuluku. Sovitaan, että a on tuo alkuluku. Nyt b < n eikä alkuluku, joten sen on oltava jaollinen kolmella. Näin ollen luvun n pitäisi myös olla jaollinen kolmella (sillä n = ab), joten vaihtoehto (3) ei käy.
(4) Luvut a ja b ovat molemmat alkulukuja. Ei ristiriitaa, joten tämä vaihtoehto on ainoa oikea.
Tavalla, jota käytettiin alkulukuhajotelman olemassaolon osoittamiseen ei siis saatu todistusta komposiittilukujen jaollisuudelle kolmella.
Huomaa, että vaikka a, b < n kohdassa (4), ei voida päätellä, että a ja b olisivat kolmella jaollisia: ne ovat alkulukuja. Luku n on siis todella olemassa: se on luku 4.
Se, että luku 4 voidaan kirjoitaa muodossa 2*2, ei anna keinoa johtaa ristiriitaa vastaoletukselle.
Osaisitko tiivistää mahdollisimman lyhyesti sanoilla miksi todistus toimii alkulukuhajotelmalle mutta ei sille että kaikki luvut ovat kolmella jaollisia?
Alkuoperäiset todistukset näyttävät hyvin samanlaisilta eikä tuossa alkulukuhajotelmatodistuksessa tarkasteltu erikseen mahdollisuuksia a:lle ja b:lle.
"Osaisitko tiivistää mahdollisimman lyhyesti sanoilla miksi todistus toimii alkulukuhajotelmalle mutta ei sille että kaikki luvut ovat kolmella jaollisia?"
Avainkohta on se, että kolmosella jaollisuutta todistettaessa tekijät saattavat olla alkulukuja. Alkulukuhajotelman olemassaoloa todistaessa vastaoletus kieltää tämän. Nyt siis koetetaan käyttää metodia tilanteessa, jossa se ei vain toimi.
Vähän kuin niistäisi nenänsä aanelosella.
"Alkuoperäiset todistukset näyttävät hyvin samanlaisilta eikä tuossa alkulukuhajotelmatodistuksessa tarkasteltu erikseen mahdollisuuksia a:lle ja b:lle."
Tarkastelua ei ole alkuperäisessä tekstissä kirjoitettu näkyviin, mutta kyllä se siellä piilossa tehdään: a ja b eivät voi olla molemmat alkulukuja, toinen niistä ei voi olla alkuluku ja molemmat eivät voi olla ei-alkulukuja. Jokaisessa kohdassa ristiriita muodostuu luvun n määritelmän takia.
"Avainkohta on se, että kolmosella jaollisuutta todistettaessa tekijät saattavat olla alkulukuja. Alkulukuhajotelman olemassaoloa todistaessa vastaoletus kieltää tämän"
Eikös tuossa kolmosella jaollisuutta todistettaessa oletettu vastaoletuksessa, että kaikki n:ää pienemmät luvut ovat kolmosella jaollisia (koska n oli pienin ei kolmella jaollinen), joten ne eivät siis voi olla alkulukuja.
Ytritän vain miettiä missä kohtaa tämä hullu todistus kaatuu...