Igazoljuk hogy ha n pozitív egész, akkor 9/4^n+15n-1?

Inkább: 9 | 4^n+15n-1 (osztója)

4^n -nek 9-es maradékai periódikusan 4,7,1,4,7,1,...

Könnyen belátható: 4*4 mod 9 = 7, 7*4 mod 9 = 1 ...

15n 9-es maradékai pedig 6,3,0,6,3,0, ...

mert 15 mod 9 = -3

Páronként összeadva (4+6, 7+3, 1+0), -1, belátható az állítás.

Teljes indukcióval.

n=1 esetén 18 jön ki, ekkor igaz.

Tegyük fel, hogy n=k-ra igaz, vagyis 4^k +15k-1 osztható 9-el.

n=k+1-re:

4^(k+1) + 15*(k+1) -1 = 4*4^k + 15* k + 15 - 1

4*4^k = 4^k + 3*4^k

(4^k + 15*k-1 ) +3*4^k+15 =(4^k + 15*k-1 ) + 3*(4^k + 5)

Az első tag az indukciós feltevés szerint osztható 9-el.

A második tagban a 4^k 3-al osztva 1 maradékot ad, vagyis a zárójelben lévő szám osztható 3-al, így az egész kifejezés osztható 9-el.

Készen vagyunk.

"a 4^k 3-al osztva 1 maradékot ad"

Ezt tudjuk, vagy teljes indukcióval belátható? :D

Onnan tudjuk, hogy ez négyzetszám 4^n = (2^n)^2, amik 3-al osztva 0 vagy 1 maradékot adnak. Mivel ebben nincs 3-as prímtényező, így 1-et ad maradékul.

Vagy úgy is lehet okoskodni, hogy 4=3+1

4^n = (3+1)^n ezért ez ugyanannyi maradékot ad 3-al osztva, mint 1^n (kibontáskor az utolsó tag kivételével mind osztható 3-al)

Röviden könnyen látható az állítás, vagy akár nyilvánvalónak is nevezhetjük :)