Keksitään erilaisia todistuksia väitteelle
Luku (a^n - 1) on jaollinen luvulla (a - 1), kun a ja n ovat kokonaislukuja, a>1 ja n>0.
Luku (a^n - 1) on jaollinen luvulla (a - 1), kun a ja n ovat kokonaislukuja, a>1 ja n>0.
Keksitään erilaisia todistuksia
Kanootti3
12213
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 12
Vanhimmat
En minä ainakaan muuta keksi kuin sen tunnetun, missä a^n-1 esitetään kahden geometrisen sarjan erotuksena, ja sitä erotusta vähäsen pyöritellään.
Menee se nyt tietysti jakokulmassa tasan ja osamäärän voidaan osoittaa olevan kokonaisluku, olishan sekin...
Kyllä tuo maitisemasi jakolasku jakokulmassa on ihan pätevä todistus asialle. Tulos on
a^n - 1 = (a - 1) (a^(n-1) a^(n-2) ... a 1).
Ja tuosta tuloksesta näkyy myös tarkastusmielessä heti, että se pitää paikkansa.
Ei tähän tämän kummempaa todistusta tarvita. Turha tehdä kärpäsestä härkästä.
Ohman
Tämä lausekehan (a^n-1)/(a-1) on periaatteessa n-jäsenisen geometrisen sarjan , jonka eka termi on 1 ja suhdeluku a summa, ja siksi vakio, mutta toi summan lauseke pitäisi ensin jotenkin johtaa. Siksi tämä seuraavassa linkissä oleva sepustus on parempi, koska siinä ei tarvita sitä tietoa geometrisen sarjan summasta. Taas lässytän kaikenlaista joutavaa, jotta moder väsyy: http://aijaa.com/W2DfjF
Induktio n:n suhteen on helppo. a-1=1(a-1) eli väite pätee kun n=1. a^{n 1}-1=a(a^n-1) (a-1) ja molemmat suluissa olevat lausekkeet ovat jaollisia luvulla a-1.
Tuon induktiotodistuksen minä aikanaan lukiossa ohitin , kun se tuntui menevän yli hilseen. Nyt sitä yritin uudestaa sisäistää ja tällaisen oman version minä siitä väänsin:
http://aijaa.com/FczqQ3
Tämä olikin kuuma tämä induktiohella kun eka kosketuksessa siihen paloi heti näpit. Korjataan tota nyt hiukan, mutta yritän tässä soveltaa tätä induktiota kahden kasvavan "muuttujan" tapaukseen, enkä tiedä onko sellaista teoriaa olemassakaan: http://aijaa.com/OVpMBw
Näin menee induktiotodistus:
kun n= 1, a - 1 l a- 1 (a-1 jakaa a - 1 :n)
Oletetaan, että a - 1 l a^n - 1 eli että a^n - 1 = k (a - 1)
a^(n 1) - 1 = a (a^n) - 1 = a(1 k (a-1)) - 1 = a k a (a-1) - 1 = (a-1) (1 ka) joten a - 1 l a^(n 1) -1
mot
Ohman
En oikein ymmärtänyt tuplainguktiotasi. On olemassa todistuksia, jotka hyödyntävät esimerkiksi murtoluvuissa ensiksi induktiota nimittäjän suhteen ja sitten osoittajan suhteen. Erilaisia esimerkkejä tuplainduktiosta on osoitteessa https://math.stackexchange.com/questions/18455/good-examples-of-double-induction
En ollut tätä ennen induktiota koskaan tutkinut ja kehitin siihen oman versioni, jossa molempia muuttujia kasvatetaan yhtä aikaa. Nyttemmin on selvinnyt, että molempien muuttujien suhteen pitäisi tehdä oma induktionsa, ja jos ne molemmat pätee, niin sitten yhdistelmäkin pätee. Näin olen sen nyt ymmärtänyt. Tässä tehtävässä ei kuitenkaan ole tarvetta tehdä sitä induktiotodistusta sen kantaluvun a suhteen. Tuli siitä kyllä ihan mielenkiintoinen lopputulos...
Induktio ännän suhteen on tosiaan helppo. Tuo induktio kantaluvun a suhteen vaikuttaa hankalammalta, mutta siitähän saa yhden todistuksen suoraan missä induktiotakaan ei tarvita (onhan se sitten induktiotodistuskin vaikkei induktioaskeleessa induktio-oletusta käytettäisikään ;-)):
Merkitään b = a-1, jolloin a = b 1. Nyt
a^n - 1
= (b 1)^n - 1
= (summa_{k=0,...,n} binomikerroin(n, k) b^k ) - 1
= b * (summa_{k=1,...,n} binomikerroin(n, k) b^k )
= (a-1) (summa_{k=1,...,n} binomikerroin(n, k) b^k )
Tässä on käytetty binomikaavaa ja vähennetty se ykkönen sieltä lopusta (tai alusta, kun se saadaan siis indeksillä k=0) ja huomattu että muut termit ovat jaollisia b:llä, joten kun b otetaan yhteiseksi tekijäksi, jää "b kertaa kokonaisluku".
Unohtui pienentää eksponenttia, kun otin b:n yhteiseksi tekijäksi. Piti olla:
a^n - 1
= (b 1)^n - 1
= (summa_{k=0,...,n} binomikerroin(n, k) b^k ) - 1
= b * (summa_{k=1,...,n} binomikerroin(n, k) b^(k-1) )
= (a-1) (summa_{k=1,...,n} binomikerroin(n, k) b^(k-1) )
Todistus käyttäen modulaariaritmetiikkaa eli kongruensseja:
a^n ≡ 1^n = 1 (mod a-1),
sillä a≡1 (mod a-1).
Näin ollen
a^n - 1 ≡ 0 (mod a-1)
eli
a^n - 1 on jaollinen (a-1):llä.