Todista, että bac= a n + a+ 1 n

Kotitehtävät, joulukuu 2011 Helpompi sarja

1. Ratkaise yhtälöryhmä

x²+y²= 2z y²+z²= 2x z²+x²= 2y reaaliluvuillax,y jaz.

Ratkaisu. Jokainen luvuista on puolet kahden neliön summasta ja siten välttämättä ei-negatiivinen. Vähennetään toinen yhtälö ensimmäisestä:2(z−x) =x²−z²= (x−z)(x+z). Koskax+z6=−2, on oltavax=z. Vastaavasti päätelläänx=y ja ratkaistavaksi jää yhtälöx²=x, jonka ratkaisut ovat 0 ja 1. Siis ratkaisut ovatx=y=z= 0 jax=y=z= 1.

2. Olkoonareaaliluku janpositiivinen kokonaisluku. Todista, että bac=

a n

+ a+ 1

n

+· · ·+

a+n−1 n

.

Tässäbxctarkoittaa suurinta kokonaislukua, joka on pienempi tai yhtäsuuri kuinx.

Ratkaisu. Vasemman puolen lauseke on askelfunktio f(a), jonka arvo nousee yhdellä jokaisen kokonaisluvun a kohdalla.

Oikean puolen lauseke on summa askelfunktioista fk(a) = b^a+k_n c, k = 0,1, . . . , n−1, joista kunkin arvo nousee yhdellä jokan:nnen kokonaisluvunakohdalla, nimittäin silloin kuna+k≡0 (modn). Koska jokaisella kokonaislu- vulleaon täsmälleen yksik= 0,1, . . . , n−1, jolla ehto toteutuu, kumpikin puoli kasvaa yhdellä silloin, kun lukuaa kasvatetaan yhdellä. Koska kumpikin puoli on nolla silloin, kuna= 0, yhtälö on tosi.

3. Etsi kaikki positiivisten rationaalilukujen parit(a, b), joille

√a+√ b=

q 2 +√

3.

Ratkaisu. Korotetaan yhtälö puolittain neliöön:a+b+ 2√

ab= 2 +√

3. Koska√

3ei ole rationaaliluku, täytyy ollaa+b= 2ja4ab= 3. Kun ratkaistaanbjälkimmäisestä yhtälöstä ja sijoitetaan edelliseen, saadaana+_4a³ −2 = 0 elia²−2a+³₄ = 0. Tästä saadaan helposti ratkaisuta=³₂, b= ¹₂ jaa=¹₂, b= ³₂. On myös helppo tarkastaa, että ratkaisut toteuttavat yhtälön.

4. Koodilukossa on kymmenen näppäintä0,1, . . . ,9. Se avataan näppäilemällä nelinumeroinen koodi (jonka numeroissa voi olla toistoja). Lukko aukeaa heti, kun oikea lukujono on syötetty peräkkäisillä näppäilyillä siitä riippumatta, mitä näppäimiä on painettu aiemmin. Jos koodi sattuisi olemaan 2011, lukko aukeaisi esimerkiksi näppäilysarjalla 45652032011 mutta ei sarjalla 20011. Mikä on lyhyin lukujono, jonka näppäileminen avaa lukon varmasti, on sen koodi mikä hyvänsä?

Ratkaisu. (Tarkoitus oli kysyä, kuinka pitkä lukujonon on vähintään oltava. Minimaalisen pituisia ehdon täyttäviä lukujonoja on toki monta.)

Lukujonon pituuden on selvästi oltava vähintään 10003.

Muodostetaan kolminumeroisista lukujonoista suunnattu verkko, jossa lukujonoa ABC vastaavasta solmusta on kaari jokaista lukujonoa BCD vastaavaan solmuun. Saatu verkko on yhtenäinen eli jokaisesta solmusta on reitti jokaiseen toiseen solmuun (reittiä voi seurata näppäilemällä jälkimmäisen solmun lukujonon). Jokaisen solmun tuloaste eli siihen tulevien kaarten lukumäärä on 10, samoin jokaisen solmun lähtöaste eli siitä lähtevien kaarten lukumäärä.

Siten verkossa on suunnattu Eulerin kehä eli sellainen reitti kaaria pitkin, että jokainen kaari tulee käydyksi tasan kerran ja lopuksi päädytään aloitussolmuun. Kun näppäillään aluksi aloitussolmun numerot ja sitten tällaisen kehän kaaria vastaavat numerot, tullaan näppäilleeksi jokainen mahdollinen nelinumeroinen koodi. Koska kaaria on 10000, näppäilyjä tarvitaan 10003.

(Eulerin kehän olemassaolon voi todistaa esim. seuraavasti. Aloitetaan ensin etsimällä verkosta jonkinlainen kehä, esim. 000 → 001 →010 → 100 →000. Poistetaan tämän kehän kulkemat kaaret verkosta, jolloin solmujen tulo- ja lähtöasteet pienenevät, mutta jokaisen solmun tulo- ja lähtöaste ovat edelleen yhtäsuuret. Sitten toistetaan seuraavaa operaatiota: valitaan kehältä jokin solmu, jonka lähtö- (ja siten myös tulo-) aste on nollaa suurempi.

Etsitään jäljellä olevasta verkosta kehä, joka kulkee tämän solmun kautta; tämä on mahdollista, koska kun seurataan valitusta solmusta lähtien kaaria ja merkitään niitä käytetyiksi, jokaisen kuljetun solmun tulo- ja lähtöaste pienenevät molemmat yhdellä, eli umpikujaan ei voida joutua ennen kuin palataan aloitussolmuun. Lopulta ollaan tilanteessa, jossa kehän jokaisen solmun lähtöaste on nolla. Tällöin alkuperäisen verkon jokaisen kaaren on oltava osana kehää, koska yhtenäisyyden takia jokaiseen kaareen on reitti aloitussolmusta.)

5. Olkoota≤b≤csuorakulmaisen kolmion sivut. Todista, että a >2(c−b).

Ratkaisu. Pythagoraan lauseen mukaana²=c²−b². Koskab≥ajac > a (tasasivuinen kolmio ei ole suorakul- mainen), ona²= (c+b)(c−b)>2a(c−b)elia >2(c−b).

6. OlkoonABC tasakylkinen kolmio, jossa∠A= 90^◦. OlkoonM sivunAB keskipiste. PisteenAkautta suoraaCM vastaan kohtisuoraan piirretty suora leikkaa sivunBC pisteessäP. Osoita, että ∠AM C=∠BM P.

Ratkaisu. Täydennetään kolmio neliöksiABKC. Olkoon suoranAP ja sivunBKleikkauspisteN. KolmiotAM C ja BN A ovat yhdenmuotoiset, koska niiden vastinsivut ovat kohtisuorassa toisiaan vastaan, ja yhtenevät, kos- ka AC = BA. Siten BM = AM = BN ja ∠AM C = ∠BN A. Kolmiot BP M ja BP N ovat yhtenevät (sks), joten∠BM P =∠BN P =∠BN A=∠AM C.

7. Olkoot x, y ja z positiivisia kokonaislukuja, joille ¹_x −_y¹ = ¹_z. Olkoon h lukujen suurin yhteinen tekijä. Todista, ettähxyzon kokonaisluvun neliö.

Ratkaisu. Olkoon x=ha, y =hb jaz =hc. Silloin syt(a, b, c) = 1, ja tehtävän yhtälöstä seuraac(b−a) =ab.

Silloinhxyz=h⁴abc=h⁴c²(b−a), joten riittää todistaa, ettäb−aon neliöluku. Riittää todistaa, että luvunb−a tekijöihinjaossa jokaisen alkuluvun eksponentti on parillinen. Olkoonp|b−a. Koskac(b−a) =ab, onp|ab, joten jokop|ataip|b. Koskap|b−a, kummassakin tapauksessapjakaa molemmat luvutajab. Koska syt(a, b, c) = 1, p-c.

Riittää todistaa, että alkuluvunpeksponentti luvunab tekijöihinjaossa on parillinen. Osoitetaan, että p:n ekspo- nentit lukujen aja b tekijöihinjaoissa ovat yhtäsuuret. Olkoona=sp^t,b =up^v, missäp-s, p-u. Jos esimerkik- siv > t≥1, olisi b−a=p^t(up^v−t−s), missä p-up^v−t−s. Siten suurinp:n potenssi, joka jakaa luvunc(b−a), olisip^t, mikä on ristiriidassa sen kanssa, että luvun ab=c(b−a) jakaap^v+t. Tapaust > v≥1 on symmetrinen.

Siis t=v.

8. Olkoon n positiivinen kokonaisluku ja s= (a1, a2, . . . , a2ⁿ)jono ei-negatiivisia kokonaislukuja. Asetetaan f(s) = (|a1−a2|,|a2−a3|, . . . ,|a2ⁿ−a1|). Merkitäänfk:lla funktiotaf sovellettunakkertaa, siisf1(s) =f(s)jafk+1(s) = f(fk(s)), kun k = 1,2, . . .. Osoita, että näillä oletuksilla fk(s) = (0,0, . . . ,0) jollain k, mutta vastaava tulos ei välttämättä päde, jos jononspituus ei ole kahden potenssi.

Ratkaisu. Todistetaan, että jonossaf2ⁿ(s)jokainen luku on parillinen, jonossaf2ⁿ⁺¹(s)jokainen luku on neljällä jaollinen, jne. Koska jonon f(s) suurin alkio on aina enintään yhtä suuri kuin jonon s suurin alkio, tästä seuraa että jono nollautuu lopulta. Toinen väittämä on helppo todeta tarkastelemalla, miten f kuvaa jonon (0,1,1):

(0,1,1)7→(1,0,1)7→(1,1,0)7→(0,1,1).

Todistetaan luvattu väittämä. Tarkastellaan jonoja modulo 2 ja määritellään niille yhteenlasku alkioittain: kun s= (a1, . . . , a2ⁿ) jat= (b1, . . . , b2ⁿ), jonos+ton(a1+b1, . . . , a2ⁿ+b2ⁿ). Silloinf(s+t)≡f(s) +f(t) (mod 2) (kun kongruenssi tulkitaan samoin alkioittain).

Koska jokaisen jononsvoi esittää modulo 2 summana joukosta jonoja, joista kussakin on yksi 1 ja muuten nollia, ja koskaf on kierron suhteen symmetrinen, riittää osoittaa, ettäf₂n(1,0, . . . ,0) = (0,0, . . . ,0). Mutta

f(1,0, . . . ,0) = (1,0, . . . ,0,1),

f2(1,0, . . . ,0) =f(1,0, . . . ,0) +f(0,0, . . . ,0,1)

= (1,0, . . . ,1) + (0,0, . . . ,1,1)≡(1,0, . . . ,0,1,0) f₄(1,0, . . . ,0) =f₂(1,0, . . . ,0) +f₂(0,0, . . . ,0,1,0)

≡(1,0, . . . ,1,0) + (0,0, . . . ,0,1,0,1,0)≡(1,0, . . . ,0,1,0,0,0)

jne. Induktiolla voidaan osoittaa, ettäf₂k(1,0,0, . . . ,0)≡(1,0,0, . . . ,0,1,0,0, . . . ,0), missä loppunollien lukumäärä on2^k−1. Siten f2ⁿ≡(1,0, . . . ,0) + (1,0, . . . ,0)≡(0,0, . . . ,0).

9. Mille positiivisille kokonaisluvuilleajab on

a³+b³ 11 alkuluvun potenssi?

Ratkaisu. Oletetaan, että a³+b³

11 on alkuluvunppotenssi. Oletetaan ensin, ettäajabovat suhteelliset alkuluvut, ja kirjoitetaan

a³+b³= (a+b) (a+b)²−3ab . Koskaajabovat suhteelliset alkuluvut,

syt a+b, (a+b)²−3ab

=syt(a+b,3ab)∈ {1,3}. (1)

Siten 11 on täsmälleen yhden luvuistaa+b ja (a+b)²−3ab tekijä. Siten 11 ei voi olla kummankaan luvuistaa ja b tekijä, koska muuten se olisi molempien tekijä. Siisa¹⁰ ≡b¹⁰ ≡1 (mod 11). Koska11| a³+b³ eli a³≡ −b³ (mod 11), on myösa⁹≡ −b⁹ja edellisen nojallaa¹⁰a⁻⁹≡b¹⁰(−b)⁻⁹elia≡ −b (mod 11); jakolasku on mahdollinen, koska syt(a,11) =syt(b,11) = 1. Siis 11 jakaa luvuna+b eikä jaa lukua(a+b)²−3ab.

Tarkastellaan tapausta, jossa 3 | a+b, jolloin p = 3 ja a+b ∈ {33,99,297, . . .} = {11·3^u, u = 1,2,3, . . .} ja(a+b)²−3ab= 3^t,t= 1,2,3, . . .. Josa+b= 33, saadaan3ab= (a+b)²−3^teliab= 363−3^t−1. Yhtälöparilla

(a+b= 33, ab= 363−3^t−1

ei ole ratkaisua: tapauksett= 1,2,3,4,5on tarkastettava erikseen, ja suuremmillat:n arvoillaabolisi negatiivinen.

Josa+b∈ {99,297, . . .}, ehdon (1) takia on oltava(a+b)²−3ab≤3, mutta(a+b)²−3ab= (a−b)²+ab≥ab, eikä voi ollaab≤3, jos33|a+b.

Siten3-a+b, ja syt a+b, (a+b)²−3ab

= 1. Koska(a+b)²−3ab= (a−b)²+ab≥ab >1, on oltavaa+b= 11 ja(a+b)²−3ab=p^t. Tutkimalla kaikki tapaukset löydetään ratkaisut

(a, b)∈ {(2,9),(3,8),(4,7),(5,6),(6,5),(7,4),(8,3),(9,2)}, joillep= 67,7,37,31,31,37,7,67.

Jos ei oleteta, että syt(a, b) = 1, luvulla syt(a, b)on silti oltava enintään yksi alkutekijä, joten syt(a, b) =p^k jollain kokonaisluvullak. Olkoona=a⁰p^k jab=b⁰p^k, jolloin saadaan

a³+b³

11 =p^3ka⁰³+b⁰³ 11 .

Taas on luvun a⁰³+b⁰³

11 oltava alkuluvun potenssi, joten tämä tapaus palautuu jo käsiteltyyn. Ratkaisut ovat siis (a, b)∈ {(2·67^k,9·67^k),(3·7^k,8·7^k),(4·37^k,7·37^k),(5·31^k,6·31^k),

(6·31^k,5·31^k),(7·37^k,4·37^k),(8·7^k,3·7^k),(9·67^k,2·67^k)}, missäk= 0,1,2, . . ..

10. Etsi kaikki kokonaisluvutn >1, joilla on seuraava ominaisuus: luvunn⁶−1 jokainen alkutekijä jakaa luvunn²−1 tain³−1.

Ratkaisu. Luku2 on selvästi tällainen: luvun2⁶−1 = 63alkutekijät ovat3 = 2²−1 ja7 = 2³−1. Osoitetaan, että muita ratkaisuja ei ole.

Tehdään oletus, ettäntoteuttaa tehtävän ehdon. Käytetään tekijöihinjakoa n⁶−1 = (n²−n+ 1)(n+ 1)(n³−1).

Luvulla n² −n+ 1 = n(n−1) + 1 on selvästi pariton alkutekijä p. Silloin p | (n²−n+ 1)(n+ 1) = n³+ 1, jotenp-n³−1. On siis oltavap|n²−1. Sitenp|(n³+ 1) + (n²−1) =n²(n+ 1). Koskap-n, on oltavap|n+ 1.

Myösp|(n²−1)−(n²−n+ 1) =n−2, joten on oltavap= 3. Siisn²−n+ 1 = 3^r(koska jokainen sen alkutekijä on 3), joten toisen asteen yhtälön n²−n+ (1−3^r)diskriminantti 1−4(1−3^r) = 4·3^r−3 = 3(4·3^r−1−1) on neliöluku. Kunr >1, diskriminantti on jaollinen kolmella vain yhden kerran, joten on oltavar= 1 ja siisn= 2.

Kotitehtävät, joulukuu 2011 Vaikeampi sarja

1. (Helpompi sarja, t. 3)

2. Paroni von Münchhausen väittää keksineensä likimääräisen kaavan neliöjuurten laskemiseen. Kaavassa on joitakin vakioita ja yksi muuttuja (juurrettava), mutta erikoisinta on, että vakioille ja muuttujalle tehdään vain kaksi lasku- toimitusta: yksi yhteenlasku ja yksi kertolasku. ”Jokaiselle reaaliluvulle välillä[1000,2000]kaavani virhe on alle1/2”, ylpeilee von Münchhausen. Voitko osoittaa, että paroni valehtelee?

Ratkaisu. Paroni ei jää kiinni valheesta. Kaava voi olla esimerkiksi f(x) = 45−31

45²−31²(x−31²) + 31 +1 3 = 1

76x+4261 228 .

Tämän funktion kuvaaja on suora, jota on siirretty hieman ylöspäin sekantista, joka leikkaa neliöjuurifunktion kuvaajan pisteissä(31²,31)ja(45²,45). Virhe mainitun välin päätepisteissä on sallituissa rajoissa,

f(961) =f(31²) = 311

3, ja f(2025) =f(45²) = 451 3,

joten jos pystytään osoittamaan, että maksimaalinen virhe välin sisällä on tarpeeksi pieni, kaava on osoitettu riittäväksi. Etsitään piste, jossa neliöjuurifunktion tangentti on suorany=f(x)suuntainen. Tangentin kulmakerroin on(√

x)⁰ = 1 2√

x, joten on ratkaistava

1 2√

x = 1 76, mistä saadaanx= 38²= 1444. Kaava antaa tässä pisteessä tuloksen

f(1444) = 37157 228, jonka virhe on alle1/2.

3. Todista epäyhtälö

sin⁴(x−y) + cos⁴(x+y)≤1 + sin²2xsin²2y reaaliluvuillex, y.

Ratkaisu. Käyttämällä trigonometrisia identiteettejä

sin²(x−y) =1−cos(2x−2y)

2 ,

cos²(x+y) =1 + cos(2x+ 2y)

2 ,

cos(2x±2y) = cos 2xcos 2y∓sin 2xsin 2y saadaan epäyhtälön vasen puoli muotoon

sin⁴(x−y) + cos⁴(x+y) =1 4 −1

2cos(2x−2y) +1

4cos²(2x−2y) +1 4 +1

2cos(2x+ 2y) +1

4cos²(2x+ 2y)

= 1

2 −sin 2xsin 2y+1

2(cos²2xcos²2y+ sin²2xsin²2y).

On siis todistettava 1

2−sin 2xsin 2y+1

2(cos²2xcos²2y+ sin²2xsin²2y)≤1 + sin²2xsin²2y

mistä termejä järjestämällä ja kahdella kertomalla saadaan

cos²2xcos²2y≤1 + 2 sin 2xsin 2y+ sin²2xsin²2y eli

(cos 2xcos 2y)²≤(1 + sin 2xsin 2y)². Kirjoitetaan tämä lausekkeiden neliöjuurien vertailuksi:

−1−sin 2xsin 2y≤cos 2xcos 2y≤1 + sin 2xsin 2y.

Tämä saadaan tehtävän alkupuolella käytetyllä identiteetillä muotoiltua epäyhtälöiksi

−1≤cos(2x−2y), 1≥cos(2x+ 2y) jotka seuraavat kosinin määritelmästä.

4. Etsi kaikki funktiotf :R→R, joille

f(x+y) =f(x)f(y+ 1) +f(x+ 1)f(y)−1 kaikilla x, y∈R.

Ratkaisu. Olkoon a = f(0) ja b = f(1). Sijoittamalla x = y = 0 saadaan a = 2ab−1, mistä seuraa a 6= 0 jab6= 1/2. Sijoittamallax=y= 1saadaanf(2) = 2bf(2)−1, mistä seuraaf(2) = 1/(2b−1) =a. Sijoittamallax= 0 jay= 2saadaan af(3) = 1 +a−ab=ab, mistä seuraaf(3) =b. Sijoittamallay= 2 saadaan

f(x+ 2) =f(3)f(x) +f(2)f(x+ 1)−1 =f(1)f(x) +f(0)f(x+ 1)−1 =f(x).

Sijoittamalla y =xsaadaan f(2x) = 2f(x)f(x+ 1)−1 ja sijoittamalla y =x+ 1 saadaan f(2x+ 1) = f(x)²+ f(x+ 1)²−1, joista seuraa

f(2x+ 1)−f(2x) = f(x)−f(x+ 1)²

≥0 kaikilla reaalisillax. Siten

f(x) =f(x+ 2) =f 2x+ 1

2 + 1

≥f(x+ 1) =f 2x

2 + 1

≥f(x),

joten f(x) = f(x+ 1) kaikilla reaalisilla x. Erityisesti a = b, jolloin a = 2a² −1 eli a = 1 tai a = −1/2.

Sijoittamalla y = 0 saadaan f(x) = 2af(x)−1, mistä seuraa että f(x) = 1/(2a−1) =a on vakio. Siis ratkaisut ovatf(x)≡1 jaf(x)≡ −1/2.

5. (Helpompi sarja, t. 8)

6. KolmiossaABCon∠B6=∠C. Kolmion sisään piirretyn ympyrän keskipiste onIja kulmanAvastaisen sivuympy- rän¹ keskipisteJ. Piste O on kulmanA sisäisen puolittajan ja sivunBC keskinormaalin leikkauspiste, ja piste P on suoranBO leikkauspiste pisteenC kautta piirretyn suoranBC normaalin kanssa. Todista, ettäIP kBJ.

Ratkaisu. Ensinnäkin |OB| = |OP|, koska pisteiden projektioilla suoralle BC on sama ominaisuus. Kulman sisäinen ja ulkoinen puolittaja ovat toisiinsa nähden suorassa kulmassa, joten kulmat∠J BI ja∠ICJ ovat suoria.

SitenBJ CI on jännenelikulmio jaIJ tämän ympäri piirretyn ympyrän halkaisija. Myös jänteenBC keskinormaali on halkaisija, joten pisteen O on oltava ympyrän keskipiste. Siis |OP| = |OB| = |OJ| = |OI|, joten BJ P I on suunnikas (ja itse asiassa suorakulmio), jotenIP kBJ.

1Jon siis kulmanAsisäisen puolittajan ja kulmienBjaCulkoisten puolittajien leikkauspiste. Nämä ulkoiset puolittajat puolittavat ne kulmat, jotka sivuBCmuodostaa sivujenABjaACjatkeiden kanssa.

A

B C

I

J O

P

A

B D C

P

K Q

7. KolmionABC sivuillaBC,CAjaAB on tässä järjestyksessä pisteetD,E jaF. JanatAD,BE jaCF leikkaavat pisteessäP. Todista, että

|AP|

|P D|· |BP|

|P E| ·|CP|

|P F|− |AP|

|P D| +|BP|

|P E|+|CP|

|P F|

= 2.

Ratkaisu. OlkoonAK kolmion korkeusjana jaQsellainen piste tällä janalla, ettäQPkBC. Silloin

|P D|

|AD| =|QK|

|AK| = SP BC

S_ABC,

missäSXY Z tarkoittaa kolmionXY Z alaa. Vastaava pätee symmetrisesti muillekin pisteille, joten

|P D|

|AD| +|P E|

|BE|+|P F|

|CF| = S_{P BC} SABC

+S_{P CA} SABC

+S_{P AB} SABC

= S_ABC SABC

= 1.

Merkitään

x= |AP|

|P D|, y= |BP|

|P E|, z= |CP|

|P F|. Silloin

|P D|

|AD| = |P D|

|AP|+|P D| = 1

|AP|

|P D|+ 1 = 1 x+ 1 ja symmetrisesti muille suhteille. Siis

1

x+ 1+ 1

y+ 1 + 1 z+ 1 = 1, mistä seuraa tehtävän väite

xyz−(x+y+z) = 2.

8. (Helpompi sarja, t. 9)

9. (Helpompi kirje, t. 10)

10. Todista, että lukujono

2002 2002

, 2003

2002

, 2004

2002

, . . .

on jaksollinen modulo2002ja selvitä sen jakson pituus.

Ratkaisu. Koska2002 = 2·7·11·13, riittää selvittää jakso modulo kukin näistä alkuluvuista. Todistetaan, että jonon

n m

,

n+ 1 m

,

n+ 2 m

, . . . (mod p) jakso onp^blogpmc+1, kunn≥m.

Käytetään Lucas’n lausetta², jonka mukaan m

n

≡

k

Y

j=0

mj

nj

(modp),

kun pon alkuluku ja lukujenmjan p-kantaiset esitykset ovat

m=m_kp^k+m_k−1p^k−1+m_k−2p^k−2+· · ·+m₀, n=n_kp^k+n_k−1p^k−1+n_k−2p^k−2+· · ·+n₀.

Kun lukumesitetään kannassap, suurinp:n potenssi onblog_pmc; merkitäänJ =blog_pmc+ 1. OlkootN1, N2≥m sellaiset luvut, ettäN1≡N2 (mod p^J), jolloin niillä on p-kantaiset esitykset

N1=n⁽¹⁾_J+kp^J+k+· · ·+n⁽¹⁾_J+1p^J+1+n⁽¹⁾_J p^J+nJ−1p^J−1+· · ·+n0, N2=n⁽²⁾_J+kp^J+k+· · ·+n⁽²⁾_J+1p^J+1+n⁽²⁾_J p^J+n_J−1p^J−1+· · ·+n0, joissa matalimmatJ jakojäännöstä ovat siis samat. Silloin

N1

m

≡ n⁽¹⁾_J+k

0

· · · n⁽¹⁾_J+1

0

· n⁽¹⁾_J

0

· n_J−1

m_J−1

· · · n0

m0

(mod p), N2

m

≡ n⁽²⁾_J+k

0

· · · n⁽²⁾_J+1

0

· n⁽²⁾_J

0

· nJ

m_J−1

· · · n0

m0

(mod p).

Siten N1

m

≡ N2

m

(mod p), joten lukujonolla on jaksollinen ainakin jaksollap^J. Lukujonon jakso (eli lyhyimmän jakson pituus) on sitenp^J:n tekijä.

Oletetaan, että jakso onp^K, missäK < J. Välttämättäp^K|p^J−1. Olkoot

N3=p^J+m_J−1p^J−1+m_J−2p^J−2+· · ·+m1p¹+m0=p^J+m, N4=p^J+ +m_J−2p^J−2+· · ·+m1p¹+m0.

SelvästiN₃−N₄ on jaollinenp^J−1:llä, joten N₃

m

≡ N₄

m

(modp). Toisaalta Lucas’n lauseesta seuraa N₃

m

≡ 1

0

· m_J−1

m_J−1

·

m_J−2 m_J−2

· · · m₁

m1

· m₀

m0

≡1 (modp), N₄

m

≡ 1

0

· 0

mJ−1

·

m_J−2 mJ−2

· · · m₁

m1

· m₀

m0

≡0 (modp),

mikä on ristiriita, joten jakson on oltavap^J.

Koska 2¹⁰ = 1024 ≤ 2002 < 2048 = 2¹², blog₂2012c = 10, joten jakson pituus, kun lukujonoa tarkastellaan modulo 2, on2¹¹. Samaan tapaan saadaan 2002:n muita alkutekijöitä vastaavien jaksojen pituuksiksi7⁴,11⁴ja13³. Siis kysytty jakson pituus on2¹¹7⁴11⁴13³.

2Esim.http://en.wikipedia.org/wiki/Lucas’_theorem