Hogy tudom ezt teljes indukcióval bizonyítani? (lsd. Lent)

Gondolkoztam a válaszon, de nem tudtam megoldást kicsiholni, csak részben. Annyi ötletem volt csak, hogy:

k = 1-re: 7 | 1^1 + 4^1 + 9^1 = 14 tehát igaz

k = 2-re: 7 | 1^2 + 4^2 + 9^2 = 98 tehát igaz

Mivel n nem osztható 3-mal, ezért

n=3k+1, vagy n=3k+2 alakú lehet.

Tehát feltesszük, hogy

k = n-re igaz 7 | 1^k + 4^k + 9^k

Azt kell bebizonyítani, hogy :

k=3n+1-re és k=3n+2-re igaz-e. Na itt akadtam el, hátha innentől tudja valaki.

A 4 és a 9 hatványai a 7-el való oszthatóságukat tekintve K=1 től felfelé haladva a következő maradékokat adják: 4: 4,2,1,4,2,1... 9: 2,4,1,2,4,1...

Az 1 tetszőleges k-ra 1 maradékot ad.

K=1-ről indulva tehát a maradékok összege így alakul: 0,0,3,0,0,3...

Bref a házban