Tallteori: Delelig med 4

[Ice]

Delelig med 4: Bevis at [tex]f(n) = 3^{n} - (-1)^n[/tex] er delelig med 4 for alle naturlige n

Ser at det er sant for [tex] n=1[/tex]

Antar at [tex]3^{n} - (-1)^n = 4k[/tex]

Vi må nå vise at dette gjelder for alle tall; n+1

[tex] f(n+1)=3^{n+1} - (-1)^{n+1}= 3\cdot3^{n}-((-1)^{1}(-1)^{n})[/tex]
[tex] = 3\cdot3^{n}+(-1)^{n}= 3\cdot3^{n}+4(-1)^{n}-3(-1)^{n}[/tex]
[tex]= 3(3^{n}-(-1)^{n})+4(-1)^{n} = 3(4k)+4(-1)^{n}[/tex]
[tex]= 4(3k+(-1)^{n})[/tex]

Og vi er i mål

[daofeishi]

Kjempeflott! Det stemmer. Der var formodningen bevist ved matematisk induksjon. Nå er det åpent for andre å komme med flere beviser.

[Magnus]

Legg merke til at 3 == -1 (mod 4)!

[fbhdif]

Denne løser seg vel strengt tatt selv?

3==3==-1 mod 4

3^n==(-1^n) mod 4
3^n-(-1^n)= 0mod 4 => 4|(3^n-(-1)^n)

?

[Magnus]

Ja

[daofeishi]

Jada, null problem med modulær aritmetikk, men et slikt tallteoretisk verktøy er det jo ikke alle som kjenner til. Nok en løsning følger fra faktorisering:

[tex]3^n - (-1)^n = (3 - (-1))(3^{n-1} + 3^{n-2}(-1) + ... + (-1)^{n-1}) = 4k[/tex]

[Magnus]

Når folk er våkne i Kina, bør det vel bli på tide å komme seg i seng i Norge, eller?;)

[daofeishi]

Ja, hvis ikke døgnrytmen din i utgangspunktet befinner seg i kinesisk tidssone. Det kjenner jeg godt til, som det B-mennesket jeg er.