Facit till rekommenderade uppgifter vecka 1

1.3.2

t₁=2, t_n=2t_n-1. (Finns svar i Biggs)

1.6.2

Om a=pc, b=qc så är xa+yb=(xp+yq)c. (Finns svar i Biggs)

1.6.4

(i) Enligt induktionsprincipen vill vi först kontrollera att det gäller för det minsta värdet på n, dvs n=0. För n=0 har vi att n²+3n=0+0=0. Eftersom noll är delbart med två är påståendet sant för n=0. Vi måste nu också visa induktionssteget, vilket i det här fallet är: Om n²+3n är delbart med två så är också (n+1)²+3(n+1) delbart med två. Eftersom (n+1)²+3(n+1)=n²+2n+1+3n+3=(n²+3n)+ 2n+4 och 2n+4 är delbart med två så kommer också (n+1)²+3(n+1) att vara delbart med två om n²+3n är delbart med två. Enligt induktionsprincipen kommer därmed n²+3n att vara delbart med två för alla icke-negativa heltal n.

1.7.1

gcd(721,448)=7. (Finns även i Biggs)

1.7.5

Största gemensamma delaren mellan 966 och 686 är 14 och en llsning ges av x=-110, y=155. Det finns oändligt många lösningar och dessa kan skrivas som x=-110+49k, y=155-69k, där k kan vara ett godtyckligt heltal.

1.8.1

Primtalen mellan 100 och 120 är 101, 103, 107, 109 och 113.

1.9.5

Vi kan skriva 1=191*725-314*441, eller mer allmänt 1=(191-441k) 725 +(725k-314) 441.

1.9.6

x=7-2k, y=-84+25k, där k är ett godtyckligt heltal.

1.9.10

Häll upp fyra omgångar från sjuliterskärlet och töm tre omgångar med nioliterskärlet. Kvar finns då 4*7-3*9=1 liter och sambandet med Sats 1.7 är att vi kan skriva den största gemensamma delaren mellan nio och sju som något heltal gånger nio plus något heltal gånger sju. Vi kan använda detta för att ta reda på hur många gånger vi ska fylla på med det ena kärlet och hur många gånger vi ska tömma med det andra.

1.9.18

Använd aritmetikens fundamentalsats för att skriva x, y och z som produkter av primtal. Eftersom x och y är relativt prima kan inte samma primtal förekomma i både x och y. När vi kvadrerar z kommer varje primtalsfaktor i z² att förekomma ett jämnt antal gånger. Eftersom xy=z² måste nu också primtalsfatorerna i x respektive y förekomma ett jämnt antal gånger. Om vi halverar alla dessa exponenter i primtalsfaktoriseringarna av x och y får vi nya heltal m och n som uppfyller x=n² och y=m².

2.1.1

Sammansättningen st ges av s(t(x))=t(x)+1=2x+1, medan sammansättningen ts ges av t(s(x))=2s(x)=2(x+1)=2x+2. Dessa två funktioner är inte lika, inte ens för något värde på x, eftersom ts(x)-st(x)=1, för alla x.

2.2.1

(i) Injektion. (ii) Bijektion. (iii) Injektion. (iv) Varken injektion eller surjektion. (Finns i Biggs.)

2.4.1

3 och 12. (Finns i Biggs.)

2.4.3

Två tal har en skillnad som är delbar med elva precis om resten vid division med elva är lika för båda talen. Det finns elva olika rester som kan uppkomma vid division med elva; , 1, ..., 10. Alltså måste det enligt duvslagsprincipen bland tolv heltal finnas två som har samma rest vid division med elva, och därmed kommer skillnaden mellan dessa två tal att vara delbar med elva.

2.5.3

Om vi antar att det bara finns k primtal p₁,p₂,...,p_k på formen 6m+5 kan vi bilda N=6p₁p₂...p_k-1. Nu ser vi att N inte kan vara delbart med p_i för något i=1,2,...,k, eftersom då skulle 1 vara delbart med detta primtal. Vi har också att varken 2 eller 3 delar N. Alltså måste primtalsfaktoriseringen enbart innehålla primtal på formen 6m+1. Produkten av två tal på denna form är fortfarande på denna form eftersom (6m+1)(6m'+1)=6(6mm'+m+m')+1. Därmed får vi att även N är på formen 6m+1, vilket ger en motsägelse, eftersom N ger resten 5 vid division med 6. Alltså kan inte antagandet om att det finns ett ändligt antal primtal på formen 6m+5 vara korrekt.

2.6.1

(i) Varken injektiv eller surjektiv. (Det finns inget x så att x²+1=0 och (-1)²+1=1²+1.) (ii) injektiv men inte surjektiv. (Det finns inget heltal x så att x³+1=3, men å andra sidan är funktionen strikt växande.) (iii) Varken injektiv eller surjektiv (Det finns inget heltal x så att h(x)=2 eftersom h är strikt växande för icke-negativa x och h(0)=1, h(1)=3. Dessutom är h(-1)=h(0)=1.

2.6.7

Dela in kvadraten i fyra delkvadrater med sidan 1. Enlig duvslagsprincipen kommer det att finnas en delkvadrat med minst två punkter i. Dessa två punkter måste ha ett inbördes avstånd som är högst roten ur två eftersom detta är diagonallängden hos delkvadraterna.

2.6.11

Enligt duvslagsprincipen kan inte ett heltal där alla siffror är olika ha fler än tio siffror. Det finns ett ändligt antal tal med högst tio siffror, närmare bestämt 8 877 690 stycken.