Hogyan mutatjuk meg, hogy 5^ (2n) -6n+8 osztható 9-el minden természetes n esetén?

tipikus teljes indukciós feladat.

n=1 esetén: 5^2-6+8=27

vagyis igaz az oszthatóság

innen az van, hogy az n=k eset igaz mivoltából következik-e az n=k+1 eset igazsága

felírjuk (k+1)-gyel, és megkeressük benne az n=k esetet:

5^(2(k+1))-6(k+1)+8=

25*5^(2k)-6k+2=

itt beleerőszakoljuk a k esetét, és korrigáljuk a "hibát":

25*[5^(2k)-6k+8]+25*6k-25*8-6k+2=

25*[5^(2k)-6k+8]+144k-198=

tehát ha n=k esetben igaz az oszthatóság, akkor annak 25-szöröse is osztható 9-cel, továbbá a 144k is és a 198 is

így k-ból a (k+1)-es eset következik, és n=1 eset igaz, emiatt az összes poz. egész szám esetében is igaz

5^(2n)=\left(5^2\right)^n=25^n

a mod9 maradékok: 7, 4, 1. A hat többszöröseinak maradékai 6, 3, 0, éppen 3 van, mint a hatványokból. A végtelen sok esetet leredukáltuk tehát háromra. Nézzük, ezekre a kifejezést:

7-6+8=9

4-3+8=9

1-0+8=9

Mindegyik osztható kilenccel. QED

Köszönöm. Pontosan.

Ugyan ez jön ki, csak kisebb számokkal fejben könnyebb számolni, ha picit trükközünk: 25 kongruens -2 mod 9 => 25^n kongruens -2^n mod 9 => n=0..8ig ezt 1,-2,4 ismétlődve. -6n kongruens 3n mod 9 => n=0..8ig 0,3,6 ismétlődve. 8 kongruens -1 mod 9. Összegezve 0,0,9 ismétlődve, mind osztható 9el, ezért az állítás igaz. Három sor, némi fejszámolás.

2 hatványai nem jelentenek gondot, 3*(0..8) szintén fejben megvan. Ezeket osztva 9el, szintén nem bonyolult fejben.

Nekem ez a modulós módszer jobban tetszik, mivel könnyebben programozható :) (Akár az előző mudolós számítással is, mert csak aprósággal tér el. Ez utóbbi csak fejszámolás miatt módosított.)

Mondjuk érdemes hozzá tudni a modulós azonosságokat [link] 2.16-os tétel.