Parittomat tekijät

Tällä viikolla, kun koulujen kesälomat alkavat vedellä viimeisiään ja vettä sataa edelleen, on hyvä perehtyä yhteen Pulmakulman kaksivuotisen historian kauneimmista (jos kohta myös yhteen vaativimmista) pulmista.

Tekijöihinjako on yksi lukuteorian perusjuttuja. Tarkoitus on luetella, millä kaikilla luvuilla jokin kokonaisluku voidaan jakaa tasan. Yleensä rajoitutaan tutkimaan vain positiivisia lukuja. Esimerkiksi luvun $10$ tekijät ovat $1, 2, 5$ ja $10$ . Yksi tärkeimmistä lukuteorian lauseista on aritmetiikan peruslause, jonka mukaan mikä tahansa ykköstä suurempi kokonaisluku voidaan esittää alkulukujen tulona ja tämä esitys on tekijöiden järjestystä vaille yksikäsitteinen.

Ja nyt siihen viikon vaikeaan pulmaan.

Olkoon nyt $n$ jokin positiivinen kokonaisluku. Tutkitaan lukuja $n+1, n+2, \ldots , 2n$ . Osoita, että näiden lukujen suurimpien parittomien tekijöiden summa on $n^2$ .

Ratkaisu: Kun tutkitaan pienten lukujen suurimpia parittomia tekijöitä, huomataan jotain mielenkiintoista. Esimerkiksi, kun $n=3$ , ovat lukujen 4, 5 ja 6 suurimmat parittomat tekijät 1, 5 ja 3. Vastaavasti asettamalla $n=4$ huomataan, että lukujen 5, 6, 7 ja 8 suurimmat parittomat tekijät ovat 5, 3, 7 ja 1. Edelleen eteenpäin menemällä alkaa näyttää siltä, että lukujen $n+1, n+2, \ldots , 2n$ suurimmat parittomat tekijät ovat aina eri lukuja. Ja näin todella onkin.

Aritmetiikan peruslauseen mukaan jokainen luku voidaan siis esittää yksikäsittesenä alkulukujen tulona. Tämä taas puolestaan tarkoittaa sitä, että jos kahdella luvulla on sama suurin pariton tekijä, voivat niiden alkutekijähajotelmat poiketa toisistaan vain parillisten tekijöiden osalta. Ja koska 2 on ainoa parillinen alkuluku, tarkoittaa tämä sitä, että jos kahdella eri luvulla on sama suurin pariton tekijä, on toinen niistä vähintään kaksinkertainen toiseen nähden. Tästä seuraa heti se, että millään kahdella luvuista $n+1, n+2, \ldots , 2n$ ei voi olla samaa suurinta paritonta tekijää, sillä $2n$ ei ole yli kaksinkertainen lukuun $n+1$ verrattuna.

Edelleen lukujen $n+1$ ja $2n$ välillä on täsmälleen $n$ lukua, joten erilaisia suurimpia parittomia tekijöitä täytyy olla $n$ kappaletta. Näistä suurin on $2n-1$ , joten pienimmän on oltava 1, ja välttämättä kaikki muutkin parittomat luvut näiden väliltä ovat mukana. Näin saadaan aritmeettisena summana

$1+3+5+\cdots +2n-1=n\cdot\frac{1+(2n-1)}{2}=n^2.$

Tämä oivallinen pulma tuli kesällä jossain internetin ihmemaassa vastaan, mutta tarkemmin tutustuin siihen Daniel Grillerin kautta. Kiitokset myös Alex Bellosille ja Matthew Scroggsille Grillerin hienon Elastic Numbers -pulmakirjan mainostamisesta!

Aiheeseen liittyy

2 thoughts on “Parittomat tekijät”

Petri Laarne says:

14.8.2017 at 09:08

Tämä on todella nätti ratkaisu, mutta itse päädyin tulokseen hieman lyhyemmällä tavalla (joka tietenkin perustuu samaan asiaan).

Käytetään induktiota, kun tiedetään luvulla $n$ ehdon toteutuvan. Luvun $n+1$ tapauksessa lista tarkasteltavista luvuista muuttuu seuraavasti: $n+1$ poistuu ja tilalle tulevat $2n+1$ ja $2n+2$ . Jälkimmäinen kumoaa poistuvan, koska niillä on sama suurin pariton tekijä. Suurimpien parittomien summa siis kasvaa luvulla $2n+1$ , joka on parittomana itse suurin pariton tekijänsä. Ja koska $(n+1)^2=n^2+2n+1$ , ehto toteutuu tälläkin luvulla.

Vastaa
- Opettaja H. says:
  
  15.8.2017 at 08:59
  
  Hyväksytään.
  
  Vastaa