Valaki meg tudná oldani, és le tudná vezetni ide ezeket a feladatokat?

Az ilyen oszthatósági szabályos feladatokat rendszerint teljes indukcióval kell megoldani. Van, amikor nem kell ehhez folyamodnunk, mert egyszerűbb máshogy okoskodni.

A teljes indukció lényege az, hogy korábbi ismeretekre épít. Egy egyszerű példa;

Ha tudjuk, hogy 2|4, akkor mutassuk meg, hogy 2|8.

A 8-at fel tudjuk bontani úgy, hogy 4+4, tehát azt kell belátnunk, hogy 2|4+4. Az összegre vonatkozó oszthatósági szabály alapján ha be tudjuk látni, hogy a tagok külön-külön oszthatóak, akkor készen vagyunk (ha meg nem, akkor mást kell keresni), tehát ha 2|4 és 2|4, akkor jók vagyunk. Mivel a 2|4 gyakorlatilag az indukciós feltevés volt, ezért amiket be kell látnunk, mindenképp igaz lesz, tehát 2|8 igaz.

Itt is ugyanez lesz a helyzet;

a)

Először nézzük meg, hogy honnantól lesz igaz az állítás;

n=1-re 5^(2*1+1)+4^(1+2) = 5^3 + 4^3 = 189, ez osztható 21-gyel.

n=2-re 5^(2*2+1)+4^(2+2) = 5^5 + 4^4 = 3381, ez is osztható 21-gyel.

Azt sejtjük, hogy ez továbbra is igaz lesz. Tehát tegyük fel, hogy az állításról tudjuk, hogy egy konkrét n-ig igaz. A különböző szakirodalmak innentől kétfelé szoktak menni; vagy n+1-re nézik meg az indukciót, vagy azt mondják, hogy a konkrét szám legyen n=k, és k+1-re nézik meg az indukciót. Én jobb szeretem az n+1-es leírást, ezért én azt választom.

Tehát azt tudjuk, hogy 21|5^(2n+1)+4^(n+2), most nézzük, hogy n+1 esetén is igaz lesz-e az állítás, vagyis hogy 21|5^(2*(n+1)+1)+4^((n+1)+2) igaz.

Végezzük el a műveleteket:

5^(2*(n+1)+1) + 4^((n+1)+2) = 5^(2n+3) + 4^(n+3)

Most próbáljuk meg ezt a kifejezést úgy átvariálni, hogy az indukciós feltevés megjelenjen:

5^(2n+3) + 4^(n+3) = 5^(2n+1+2) + 4^(n+2+1) = 5^2*5^(2n+1) + 4*4^(n+2) = 25*5^(2n+1) + 4*4^(n+2)

Már majdnem a végén vagyunk:

25*5^(2n+1) + 4*4^(n+2) = 21*5^(2n+1) + 4*5^(2n+1) + 4*4^(n+2) = 21*5^(2n+1) + 4*[(5^(2n+1) + 4^(n+2))]

Ha az összeg tagjairól külön-külön be tudjuk látni, hogy az oszthatóság igaz, akkor az egész összegről belátjuk, hogy osztható. Az első tag a 21* miatt mindenképp osztható lesz 21-gyel, a második tagban a szögletes zárójelben lévő kifejezés az indukciós feltevés miatt osztható 21-gyel, ezen a 4* nem változtat. Tehát az összeg osztható 21-gyel, tehát bizonyítottuk, hogy ha n-ig igaz az álíltás, akkor n+1-re is biztosan igaz lesz.

Az indukciós bizonyításban azt kell tudni elsajátítani (gyakorlatilag az a kulcs), hogy a kapott kifejezést addig kell gyűrni, amíg az indukciós feltevés meg nem jelenik. Vannak persze olyan feladatok, amik pont emiatt nem megoldhatóak teljes indukcióval, de ezt általában nehéz előre látni.

A b,c ezzel a módszerrel megoldható. A másik négy feladatnál egyszerűbben is lehet okoskodni;

d) 6|n^3 + 5n

A kifejezésből emeljünk ki n-et: n^3 + 5n = n*(n^2+5)

Egy szám akkor osztható 6-tal, hogyha osztható 2-vel és 3-mal. A 2-vel oszthatóságot ránézésre meg lehet mondani; ha n páros, akkor kész vagyunk, ha n páratlan, akkor n^2+5=páratlan+páratlan=páros, ekkor a másik tényező lesz osztható 2-vel.

A 3-mal oszthatóság kicsit macerásabb, de nem megoldhatatlan. Az biztos, hogy minden pozitív egész szám felírható vagy 3*k, vagy 3*k+1 vagy 3*k+2 alakban, ahol k nemnegatív egész. Azért ezt választjuk, mert a 3-mal való oszthatóságot akarjuk belátni.

-Ha n=3*k, akkor 3*k*((3*k)^2+5), és itt meg is állhatunk, mert a 3* miatt osztható lesz 3-mal.

-Ha n=3*k+1, akkor (3*k+1)*((3*k+1)^2+5) = (3*k+1)*(9k^2+6k+1+5) = (3*k+1)*(9k^2+6k+6), a második tányező biztosan osztható 3-mal, tehát jók vagyunk.

-Ha n=3k+2, akkor (3*k+2)*((3*k+2)^2+5) = (3*k+2)*(9k^2+12k+4+5) = (3*k+2)*(9k^2+12k+9), itt is osztható a második tényező 3-mal.

Tehát minden esetben osztható a szám 2-vel és 3-mal, így pedig 6-tal is.

Ennél a példánál egyébként macerásabb lett volna a teljes indukciós bizonyítást használni, mivel 3. hatványra kellett volna emelni, az meg nem egy kényelmes dolog.

Az e) feladat azért érdekes, mert felbontható így: n^3+11n = n^3+5n+6n. Azt az előbb beláttuk, hogy n^3+5n osztható 6-tal, tehát az biztos. A 6n is szemmel láthatóan osztható 6-tal, tehát az egész is. Ebben az esetben megúsztuk a fölösleges számolást.

f) 17|2^16 - 1 akár manuálisan is kiszámolható nem olyan nagy szám. Egyébként az a^2-b^2=(a-b)*(a+b) azonosságot kell használni, többszörösen:

2^16 - 1 = (2^8 - 1) * (2^8 + 1) = (2^4 - 1) * (2^4 + 1) * (2^8 + 1)

Namost a 2^4 + 1 értéke 17, tehát megtaláltuk a 17-es tényezőt.