talteori – Sida 2 – Mattebloggen

Nians tabell

Rekommenderad från: 15 år

[kkratings]

På en rad står tal, som är delbara med 9, i stigande ordning: 9, 18, 27, 36 och så vidare. Under varje tal står dess siffersumma.

(a) På vilken plats i andra raden ser vi först talet 81?

(b) Vad kommer stå först på andra raden: fyra stycken 27 i rad eller en gång talet 36?

Visa lösningen

Tvåpotensens sista siffra

Rekommenderad från: 15 år

[kkratings]

Det finns ett naturligt tal m, sådant att talet 2^m har siffersumma 8. Kan sista siffran i talet 2^m vara lika med 6?

Visa lösningen

Svar:

Det kan den inte! Jag har fått in tre stycken olika lösningar, så det är bara att välja och vraka.

För att kunna förstå lösningarna är det bra att kunna:

moduloräkning

Om två tal har lika rester vid division med ett och samma tal n, så säger man att de talen är kongruenta modulo n.

Till exempel så är talen 3 och 11 kongruenta modulo 4 eftersom båda ger rest 3 när man dividerar med 4. Även talet -1 är kongruent med 3 modulo 4.
Man kan också skriva 3 $\equiv$ 11 (mod 4)

delbarthetsprincipen för 3

Ett heltal är delbart med 3 om och endast om dess siffersumma är delbar med 3. Man kan också vara fancy och säga att ett tal är delbart med 3 om och endast om talets siffersumma är kongruent med 0 modulo 3.

Till exempel så är talet 450072456 inte delbart med 3, eftersom siffersumman är 4+5+0+0+7+2+4+5+7=34 och det talet går inte att dela jämnt på 3.

delbarthetsprincipen för 9

Liknar faktiskt delbarthetsprincipen för 3. Ett heltal är delbart med 9 om och endast om dess siffersumma är delbar med 9.

Till exempel så är talet 1111000011111 delbart med 9, eftersom siffersumman är lika med 9.

Det är även så att ett godtyckligt tal och dess siffersumma alltid ger samma rest vid division med 9, det vill säga det är kongruenta modulo 9.

Lösning 1 (den officiella):

Vi konstaterar att de första tvåpotenserna är 2, 4, 8, 16 och 32, samt att inget av dessa uppfyller kriterierna. Dock måste alla kandidater vara jämnt delbara med dessa tal.

Om ett tal har siffersumman 8 och slutar på 6 finns två möjligheter:

a) Talet har formen 2*10^k + 6 för något k>=1 (dvs 26, 206, 2006, osv.)

26 (=2*13) är inte en tvåpotens, alltså måste k>=2, men alla andra tal på formen
2*10^k är delbara med 8, medan 6 inte är delbart med 8. Således blir talet som
helhet (2*10^k + 6) ej delbart med 8. Vi kan alltså helt utesluta denna möjlighet.

b) Talet har formen 1*10^k + 1*10ⁿ + 6 för något k>n>=1 (dvs på formen 100..0100…06)

6 är inte delbart med 4, så resten får inte heller vara det, om summan skall vara delbart med 4. Det enda n sådant att 10ⁿ inte är delbart med 4 är n=1 (k kan inte vara så litet). Alltså måste talet ha formen 1*10^k + 16.

Vi ser dock på samma sätt att 16 inte är delbart med 32, så det får inte 10^k heller vara. För alla k>=5 är 10^k jämnt delbart med 32, så dessa förkastas.

Man kan nu pröva de återstående lösningarna (10016, 1016, 116) var och en, men närmare bestämt är 16 $\equiv$ 16 i modulo 32, så 10^k måste vara lika med 32-16 $\equiv$ 16 (mod 32). Det enda k som uppfyller detta är k=4, vilket ger 10016 = 2⁵ * 313, som på intet vis är en tvåpotens. För säkerhets skull kan konstateras att 1016=2³*127 och 116=2²*29.

Lösning 2 (den med perioder):

Att siffersumman av 2^m 8, kräver att 2^m är kongruent med 8 modulo 9.

Att 2^m slutar på 6, kräver att 4|m. Detta ser man genom att helt enkelt
göra en tabell av potenser av 2, och ser att den har period 4, om man bara
betraktar sista siffran.
2, 4, 8 (1)6, (3)2,(6)4, (12)8, (25)6,…

Så, vi undrar egentligen om det finns heltal k, så att 2^4k $\equiv$ 8 (mod 9).
Ekvivalent med att
16^k $\equiv$ 8 (mod 9)<=>
7^k $\equiv$ 8 (mod 9) (*)

Nu,
7¹ $\equiv$ 7 (mod 9)
7² $\equiv$ 4 (mod 9)
7³ $\equiv$ 1 (mod 9)
och nu har vi nått 1, så denna sekvens kommer upprepa sig om och om igen.

Alltså kan högerledet aldrig bli 8, och (*) kan ej lösas. Att (*) ej kan lösas
implicerar att 2^m ej kan sluta på 6 och samtidigt ha siffersumma 8.

Lösning 3 (den snygga):

Antag att ett sådant tal finns. Notera att 2^k endast slutar på 6 om k är jämnt (t.o.m delbart med 4, men jämnt räcker).
Då har 2^k-1 siffersumma 7 och är inte delbart med 3. Men k=2n så
2²ⁿ-1=(2ⁿ-1)(2ⁿ+1).
Märk att talen 2ⁿ-1, 2ⁿ och 2ⁿ+1 är tre stycken på varandra följande, så något utav dessa måste vara delbar med 3. Men det kan inte vara 2ⁿ, eftersom det är en tvåpotens.
Någon av faktorerna i uttrycket är således delbar med 3 och vi får motsägelse.

Sabbad multiplikation

Rekommenderad från: 12 år

[kkratings]

På tavlan skrev matteläraren Adam en uträkning. Men precis innan lektionen skulle börja, så busade någon utav eleverna och bytte ut två siffror mot nya. Därefter stod det:

$4\cdot5\cdot4\cdot5\cdot4=2247$

Men vilka var siffrorna från början? Förklara hur du kommer fram till svaret.

Visa lösningen

Klassiska bevis: roten ur 2 irrationellt

Flera av mina bekanta har berättat för mig vad deras första möte med riktiga matematiska bevis var. Och man märker kanske inte först att det man läser eller hör om är så kallade riktiga bevis, förrän man läser ordet ”bevis” explicit. De första sådana för var och en kunde ha varit bevis för Pythagoras sats, något induktionsbevis eller motsägelsebevis.

Här tänkte jag berätta om den mest klassiska klassikern av motsägelsebevis, nämligen att roten ur 2 är ett irrationellt tal.

Vad betyder irrationellt?

Ett irrationellt tal är ett tal som inte går att få med hjälp av naturliga tal 0, 1, 2, 3 …. och de aritmetiska operationerna +, -, * och /. Talen som däremot går att få på det sättet kallas rationella, till exempel $\frac{(5-10)}{3}=\frac{-5}{3}$ . Rationella tal kan alltså skrivas som bråk.

Irrationell och rationell är helt enkelt motsatser. På grund av den här negativa definitionen (det vill säga definiera något genom att använda ett ”inte”), är det naturligt med ett negativt bevis till påståendet (det vill säga motsägelsebevis).

Påstående: $\sqrt2$ är ett irrationellt tal.

Tankegång: Vi skall alltså bevisa att $\sqrt2$ inte är ett rationellt tal. Kan verka svårt först, vi kan ju inte riktigt testa alla möjligheter, alla bråk som överhuvudtaget går att få fram. T.ex. (bara ett exempel nu, helt onödigt för beviset!!!):

Är $\sqrt2=\frac{3}{2}?$ Nej, för då skulle deras kvadrater vara lika $2=\frac{9}{4}$ , vilket absolut inte är sant!

Men det finns oändligt många bråk, vi kan sitta och gissa bråk som är ungefär lika med roten ur 2 och sedan verifiera att de inte är exakt lika. Men bara för att vi inte kan hitta något bevisar inte att det inte finns!

Det är nu vi inser att det faktiskt skulle vara lättare att på något sätt testa alla möjligheter samtidigt. Med det menar jag att vi antar att det finns ett sådant bråk och vi sedan kommer fram till att det aldrig kan bli likhet med roten ur 2. Det är kärnan i alla så kallade motsägelsebevis: antag att det går (antag det positiva påståendet, det utan ”inte”) och kom fram till motsägelse.

Bevis: Antag att roten ur 2 är lika med något bråk. Förkorta bråket så långt det går, så att nämnaren och täljaren inte längre går att dela med samma heltal. Vi har alltså nu:

$\sqrt2=\frac{a}{b}$ och a och b är heltal som inte har någon gemensam delare.

Som förut försöker vi kontrollera likheten genom att kvadrera:

$2=\frac{a^2}{b^2}$ ,

så

$2{b^2}=a^2$ .

Varför är denna likhet omöjligt då? Vi tar hjälp av talteori, läran om heltal och delbarheter.

Vänsterledet $2b^2$ är ett jämnt tal, så högerledet, $a^2$ måste vara det också. Alltså går $a$ att dela med 2, dvs $a=2k$ , där $k$ är ett heltal. Skriv om likheten:

$2{b^2}=(2k)^2=4k^2$ .

MEN detta innebär ju att $b^2=2k^2$ så med samma resonemang som förut får vi att $b$ är ett jämnt tal. Men nu kommer vi fram till motsägelse, eftersom i situtationen då både $a$ och $b$ är jämna går det faktiskt att förkorta bråket (med 2). Nu är vi faktiskt klara.

Vi blev klara så fort vi fick motsägelse i vår lösning. Det är därför det heter motsägelsebevis.

Blåröda tallinjen

Rekommenderad från: 15 år

Förkunskaper: intervall, tallinjen, delbarhet, potenser.

På reella tallinjen markerade Johan alla kvadrater på positiva heltal. Varje erhållet intervall delade han sedan i två lika stora delar, de vänstra halvorna målade han blått (inklusive vänstra änden), medan de högra målade han rött (exklusive högra änden).

1. Visa att för varje positivt heltal n kan han hitta ett blått tal som är delbart med talet n.

2. Visa att för varje positivt heltal n kan han hitta ett rött tal som är delbart med talet n.

3. Visa att Johan kan hitta 1000 olika positiva heltal, så att summan av vilka som helst 5 av dem är ett rött tal.

4. Visa att det finns oändligt många röda tal som är potenser av två.

Visa lösningen

1. Varje tal $n^2$ är ju blått, kvadraterna är alltid de vänstra ändarna av intervallen. Och $n^2$ är delbart med $n$ .

2. Varje tal $n^2-1$ är däremot rött. Även $(n+1)^2-1$ är rött. $(n+1)^2-1=(n+2)n$ som då är delbart med $n$ .

3. Vi ser att längderna på röda intervall ökar med tiden. Först är det 1,5, sedan 2,5 sedan 3,5 och så vidare. Det beror på att skillnaden mellan två på varandra följande kvadrater är ett udda tal och alla udda tal förekommer på det sättet. $(n+1)^2 - n^2 = 2n + 1$ . Huvudsaken är i vilket fall att röda intervall ökar till längden. Hitta ett jättestort rött intervall. Hitta sedan det första talet i det, som kan skrivas som $5x+15$ (alla stora tal delbara med 5 kan skrivas så). Det uttrycket är nämligen summan utav $x+1, x+2, x+3, x+4$ och $x+5$ .

Som våra tusen tal tar vi då $x+1, x+2, x+3, \ldots, x+999, x+1000$ . Vilka fem av dem vi än tar kommer deras summa vara större än eller lika med $5x+15$ och mindre än eller lika med $5x+996+997+998+999+1000=5x+5000-10 = 5x+4990$ . Väljer vi längden på det röda intervallet lika med 5000,5 så är vi säkra på att den största summan är röd.

Notera att vi här inte behövde lista just vilka tal vi valde. Det räcker att visa att det går, precis vad det frågas efter i uppgiften.

4. (Obs! Formlerna har försvunnit. Försök att fylla i själv :)) Vilka potenser av 2 kan vara röda? Inte de jämna i alla fall, för att [], det vill säga jämna tvåpotenser är kvadrat på naturliga tal, och alla kvadrater är ju blå. De enda vi kan hoppas på är udda potenser, []. För att de ska hamna i röda intervall måste de vara i den högra halvan av intervallet mellan [] och [] för något naturligt tal n.

Vänstra begränsningen är alltså mittpunkten på intervallet, som är [] och högra är []. Således måste []. Alla talen är positiva, alltså kan vi dra roten ur varje led. Notera att roten ur [] är mindre än [], så alla k som uppfyller [] är också k som passar oss. [] ska alltså befinna sig mellan två på varandra följande heltal och dess bråktalsdel (talet minus heltalsdelen) skall vara större än [].

Vi börjar alltså med [] och multiplicerar den med två k gånger. Vi ska bevisa att talen aldrig kommer fastna med bråkdelen mindre än eller lika med []. Notera att eftersom [] är ett irrationellt tal, så kommer vi aldrig att komma fram till ett heltal genom att dubbla, det vill säga bråktalsdelen kommer aldrig att bli 0. Antag att den någon gång blir mellan 0 och []. Då kommer den efter några dubbleringar att bli mellan [] och 1, eftersom den ökar hela tiden, och den kan inte ”hoppa över” de decimalerna vi vill åt: någonting, som är mindre än [], gånger 2 blir någonting, som är mindre 1. Därför kommer vi alltid att komma tillbaka till bra bråktalsdel. Vi har hittat oändligt många k som passar, och således också oändligt många (udda) tvåpotenser!

Etikett: talteori

Nians tabell

Rekommenderad från: 15 år

Tvåpotensens sista siffra

Rekommenderad från: 15 år

Svar:

moduloräkning

delbarthetsprincipen för 3

delbarthetsprincipen för 9

Lösning 1 (den officiella):

Lösning 2 (den med perioder):

Lösning 3 (den snygga):

Sabbad multiplikation

Rekommenderad från: 12 år

Lösning:

Klassiska bevis: roten ur 2 irrationellt

Blåröda tallinjen

Rekommenderad från: 15 år

Förkunskaper: intervall, tallinjen, delbarhet, potenser.