Det magiske tallet 3

[Maple]

Bevis følgende:

[tex]\frac{\sum_{n=0}^{N}a_n}{3} \in \mathbb{N} \Rightarrow \frac{\sum_{n=0}^{N}a_n10^n}{3} \in \mathbb{N} \forall N \in \mathbb{N}[/tex]

Er jeg bare skikkelig "dum", eller er dette faktisk vrient?

[Magnus]

Vil vel helst vise at hvis [tex]\sum_{n=0}^N a_n \equiv 0 \pmod{3}[/tex] så er [tex]\sum_{n=0}^Na_n10^n \equiv 0 \pmod{3}[/tex]

Ser at [tex]10^n \equiv 1^n \equiv 1 \pmod{3}[/tex]... Så er vi vel der.

[Maple]

Jeg forstår ikke beviset ditt. Men jeg har løst det (kanskje litt mindre elegant) selv.

Om vi ser for oss [tex]a_n10^n[/tex] som [tex]\frac{a_n*10*10*10*10*\cdots*10}{3}[/tex], så kan dette alltid skrives som [tex]\frac{a_n*10*10*10*10*\cdots*(9+1)}{3} = \frac{a_n*10*10*10*\cdots*10}{3}+\frac{a_n*10*10*10*10*\cdots*9}{3}[/tex]. Slik kan vi fortsette til vi sitter igjen med tall på formen [tex]\frac{a_n*10*10*10*10*\cdots*9}{3}[/tex] eller [tex]a_n[/tex], og dermed er vel saken løst.

Jeg har på følelsen at det er det samme du sier i beviset ditt, Magnus, men jeg forstår det likevel ikke helt... hvorfor er [tex]10^n \equiv 1^n[/tex]? Det er vel ikke det samme?

[mrcreosote]

Det er det som heter moduloregning. Kort og grovt: Når vi regner modulo 3 har vi bare 3 forskjellige tall (i motsetning til når vi regner med de naturlige tall - de er det uendelig mange av). Disse er 0, 1 og 2. Tallet 5 eksisterer derfor ikke modulo 3 skulle man tro, men det gjør det og det er lik 2. Dette fordi vi får 2 til rest når vi regner ut 5/3. Vanligvis teller vi sånn: 1,2,3,4,5,6,7,... Modulo 3 teller vi 1,2,0,1,2,0,1,...

Nå er 10 [symbol:identisk] 1. ( [symbol:identisk] er tegnet man bruker for indikere at noe er likt noe annet i moduloregning.) Så da er også 10^n [symbol:identisk] 1^n = 1.

Du regner forøvrig modulo 24 daglig: Når du har vært seint oppe en kveld, legger du deg ikke klokka 27, men 3.

Som sagt, dette var kort og ikke pinlig presist, men det forklarer omtrentlig åssen ting fungerer og hvordan man regner. Da henger du kanskje med på Magnus' tanker også?

[Maple]

Ja, nå gjør jeg det. Det er smart dette! Jeg vil vel lære mer av dette når jeg tar tallteori til høsten, antar jeg.

Uansett så er det jo det samme beviset som jeg gjorde, bare enklere og mer elegang.

[mrcreosote]

Ja, det vil være stoff i ethvert introkurs i tallteori.

Ny oppgave til deg: Vis at [tex]n^3+11n[/tex] er delelig med 6 for alle hele n. Det går sjølsagt an å bruke induksjon, men prøv med moduloregning også og se hva du foretrekker.

[Maple]

Dette var lett! Hehe.

Når man dividerer 11n på 6 vil man hele tiden ha tall i følgen {5,4,3,2,1,0} som rest. Det er lett å verifisere dette for de 6 første tallene. For større tall er det bare å sette u = n - 6, slik at vi får 11(u+6) = 66 + 11u, og siden 66 dividert på 6 åpenbart ikke har noen rest, vil 11n fortsette å ha tall i {5,4,3,2,1,0}, i ordnet rekkefølge.

Om man diverer n^3 på 6 får man for de første 6 tallene rester på {1,2,3,4,5,0}, og for større tall, er det bare å skrive n^3 om til (u + 6)^3 = u^3 + 3*u^2*6 + 3*u*6^2 + 6^3, som åpenbart vil "begynne fra begynnelsen" i den nevnte følga for restene.

Da er det lett å se [tex]n^3+11+n\equiv 0 \pmod {6}[/tex], og dermed er tallet delelig med 6 (selv for naturlige tall).

[Magnus]

Hvor skal du ta tallteori?

[Magnus]

Oppgaven kan vel også løses ved å skrive

[tex]n^3 + 11n \equiv n^3 - n \equiv n(n-1)(n+1) \pmod{6}[/tex]

Resultatet følger umiddelbart.

[mrcreosote]

Flott!

Du kan korte ned litt (lite her, men i andre eksempler meget mer) ved å observere at et tall er delelig med hvis og bare hvis det er delelig med både 2 og 3. Gitt at du skal vise at noe er delelig med 35, er det litt mer fristende å kun sjekke de 5+7 tilfellene du får om du faktoriserer.

Da kan vi også argumentere sånn: [tex]n^3+11n = n^3-n+12n = (n-1)n(n+1)+12n[/tex]. Av tre påfølgende heltall er alltid minst ett delelig med 2 og nøyaktig ett delelig med 3. Derfor er det hele delelig med 6.

Edit: Litt sein.

[Maple]

Hvor skal du ta tallteori?

Skal ta kurset MA1301 ved NTNU. Jeg gleder meg veldig faktisk, for det står i beskrivelsen av emnet at det vil bli gjennomgått bevis for Fermats teorem for n=4.

Jeg har lest et bevis på dette, men det var endel jeg ikke skjønte.

[Maple]

Oppgaven kan vel også løses ved å skrive

[tex]n^3 + 11n \equiv n^3 - n \equiv n(n-1)(n+1) \pmod{6}[/tex]

Resultatet følger umiddelbart.

Smart. Jeg tenkte faktisk på å faktorisere, for å forkorte beviset, men tenkte ikke på at 11n er det samme som -n i denne sammenheng. Og n^2+11 lar seg jo ikke faktoriseres reellt.

[Magnus]

Hvor skal du ta tallteori?

Skal ta kurset MA1301 ved NTNU. Jeg gleder meg veldig faktisk, for det står i beskrivelsen av emnet at det vil bli gjennomgått bevis for Fermats teorem for n=4.

Jeg har lest et bevis på dette, men det var endel jeg ikke skjønte.

Jeg tok det kurset forrige semester og da ble "Fermats Teorem"(antar du mener siste teorem..) byttet ut med Pells likning og kjedebrøker i steden.

[Maple]

Hvor skal du ta tallteori?

Skal ta kurset MA1301 ved NTNU. Jeg gleder meg veldig faktisk, for det står i beskrivelsen av emnet at det vil bli gjennomgått bevis for Fermats teorem for n=4.

Jeg har lest et bevis på dette, men det var endel jeg ikke skjønte.

Jeg tok det kurset forrige semester og da ble "Fermats Teorem"(antar du mener siste teorem..) byttet ut med Pells likning og kjedebrøker i steden.

Ja. Jeg leser nå at det (Fermats siste sats) går under "spesialstoff som kan variere fra år til år".