Lösningar till tentamen i MAN011, Aritmetik och algebra, del 1, 98 10 30

3.

(b) Vi söker ett polynom med heltalskoefficienter som har talet som nollställe. Sätt $x=\sqrt{1+\sqrt{2}}-\sqrt{2},$ dvs $x+\sqrt{2}=\sqrt{1+\sqrt{2}}$. Kvadrering ger $x^{2}+2\sqrt{2}x+2=1+\sqrt{2},$ dvs $x^{2}+1=\sqrt{2}(1-2x)$. Kvadrering ger

$$x^{4}+2x^{2}+1=2(1-4x+4x^{2}),\mbox{ dvs }x^{4}-6x^{2}+8x -1=0.$$

Alltså är x⁴-6x²+8x-1 ett polynom med heltalskoefficienter som har $\sqrt{1+\sqrt{2}}-\sqrt{2}$ som nollställe. De enda möjliga rationella nollställena är $\pm 1$. Inget duger. Därmed är $\sqrt{1+\sqrt{2}}-\sqrt{2}$ irrationellt.

4.

Om vi lyckas visa att a_n<(1/5)(-2/3)ⁿ+1 har vi också visat att a_n<(1/5)(2/3)ⁿ+1 Vi bevisar att a_n<(1/5)(-2/3)ⁿ+1 med induktion. Vi kontrollerar först påståendet då n=0 och 1. (Vi kan bara använda formeln för a_n om $n\geq 2$.)

n=0. Vi har a₀=1 och (1/5)(-2/3)⁰+1=1+1/5. Alltså gäller påståendet då n=0.

n=1. Vi har a₁=2/3 och (1/5)(-2/3)¹+1=-2/15+1, så påståendet gäller även när n=1.

Antag nu att a_n<(1/5)(-2/3)ⁿ+1 om n<p, där $p\geq 2$.Vi får då

$$\begin{array} {rcl} a_{p}&=&\frac{1}{3}a_{p-1}+\frac{2}{3}a_... ...\frac{2}{3})=\\ &=& \frac{1}{5}(-\frac{2}{3})^{p}+1\end{array}$$

Enligt induktionsprincipen gäller nu påståendet för alla heltal $n\geq 0$.

5.

Kvadratkomplettering ger

0=z²-(5-i)z+8-i=(z-(5-i)/2)²-(25-10i-1)/4+8-i=(z-(5-i)/2)²+2+3i/2.

Vi sätter a+ib=z-(5-i)/2, där $a,\,b\in\mathbb R,$ och ska lösa (a+bi)²=-2-3i/2. Vi jämför längd, real- och imaginärdel av de båda leden och får ekvationssystemet

$$\left\{ \begin{array} {rcl} a^{2}+b^{2}&=&\sqrt{4+9/4}=5/2\\ a^{2}-b^{2}&=&-2\\ 2ab&=& -3/2. \end{array}\right.$$

Summan av de två första ekvationerna ger 2a²=1/2, dvs $a=\pm 1/2$. Deras skillnad ger 2b²=9/2, dvs $b=\pm 3/2$. Den tredje ekvationen ger nu att a och b ska ha olika tecken:

$$a+bi=\pm(1/2-3i/2)\mbox{ som ger }z=(5-i)/2\pm(1/2-3i/2)= \left\{ \begin{array} {r} 3-2i\\ 2+i \end{array} \right.$$

Svar: $z=3-2i,\,2+i$

6.

Den nedersta ekvationen har lösningarna x=7+37k₁, där k₁ är ett godtyckligt heltal. Vi sätter in dessa lösningar i den andra ekvationen och bestämmer k₁ så att denna stämmer:

$$7+37k_{1}\equiv 11\Leftrightarrow 14k_{1}\equiv 4\mbox{ mod }23.$$

Vi bestämmer en invers till 14 modulo 23 genom att använda Euklides algoritm för en största gemensam delare till talen:

$$\begin{array} {rcl} 23&=&1\cdot 14+9\\ 14&=&1\cdot 9+5\\ 9&=&1\cdot 5+4\\ 5&=&1\cdot 4+1\end{array}$$

Baklänges ger detta $1=5-4=5-(9-5)=2\cdot 5-9=2(14-9)-9=2\cdot 14-3\cdot 9=2\cdot 14-3(23-14)=5\cdot 14-3\cdot 23$. Vi får $5\cdot 14\equiv 1 \mbox{ mod }23.$ Detta ger

$$14k_{1}\equiv 4\Leftrightarrow k_{1}\equiv 20 \mbox{ mod }23.$$

Vi ska välja k₁=20+23k₂ där k₂ är ett godtyckligt heltal. Detta ger x=7+37k₁=7+37(20+23k₂). Vi sätter in detta i den översta ekvationen för att bestämma k₂.

$$7+37(20+23k_{2})\equiv 5\Leftrightarrow 7+(8-k_{2})\equiv 5\Leftrightarrow k_{2}\equiv 10 \mbox{ mod }12.$$

Vi måste alltsä välja k₂=10+12k₃, där k₃ är ett godtyckligt heltal. Detta ger $x=7+37(20+23k_{2})=7+37\cdot 20+37\cdot 23\cdot 10+37\cdot 23\cdot 12k_{3}$. Det minsta positiva talet fås när k₃=0, dvs x=2+740+8510=9257.

Svar: 9257.

7.

Elementen i $(\mathbb Z/22)^{\times}$ är alla tal $r,\,0\leq r<22,$som har största gemensam delare 1 med $22=2\cdot 11$. Vi har alltså

$$(\mathbb Z/22)^{\times}=\{1,3,5,7,9,13,15,17,19,21\}$$

så gruppen har ording 10. Enligt Lagrangesats har en delgrupp ordning som delar 10. Ordningen för en delgrupp är alltså $1,\,2,\,5$ eller 10. Vi börjar med att undersöka ordningen av elementen i $(\mathbb Z/22)^{\times}$.

$$\langle 3\rangle=\{3,3^{2}=9,3^{3}=27=5,3^{4}15,3^{5}=45=1\}$$

Så o(3)=5 och 9,5,15 har ordning som delar 5 (enligt Lagranges sats). Detta ger att 3,5,9,15 alla har ordning 5. Vi fortsätter med att beräkna ordnignen av 7 och får

$$\langle 7\rangle=\{7,7^{2}=49=5,7^{3}=35=13=-9,7^{4}=-63=3,7^{5}=21=-1,\ldots\}$$

Orndingen av 7 är alltså större än 5 och därför 10. Gruppen är alltså cyklisk:

$$\langle 7\rangle =(\mathbb Z/22)^{\times}.$$

En cyklisk grupp $\langle r\rangle$ av ordning 10 har precis en delgrupp av ordning d för varje delare d till 10. Gruppen av ordning d är $\langle r^{10/d}\rangle$. Delgrupperna till $(\mathbb Z/22)^{\times}$är alltså

$$\langle 7^{10}\rangle=\langle 1\rangle,\,\langle 7^{5}\rangl... ...ngle 7^{2}\rangle=\langle 5\rangle\mbox{ och }\langle 7\rangle$$

av ordning $1,\,2,\,5$ respektive 10.

Svar: $\{1\},\,\langle 22\rangle,\,\langle 5\rangle$ och $(\mathbb Z/22)^{\times}$ (av ordning $1,\,2,\,5$ respektive 10.)

8.

Vi delar in de n-siffriga talen med siffrorna $1,\,2,\,3$ och 4 i olika typer. Sätt

$$\begin{array} {rcl} a_{n}&=&\mbox{antalet $n$-siffriga tal m... ...a tal med udda antal $1$:or och udda antal $2$:or,}\end{array}$$

Vi försöker härleda samband mellan dessa tal och observerar först att

b_n=c_n,

ty om vi byter 1:or mot 2:or och vice versa ger ett tal av typ b ett av typ c och omvänt.

Om vi har ett (n-1)-siffrigt tal av typ c får vi ett n-siffrigt tal av typ c genom att lägga till en 3:a eller en 4:a på slutet. Å andra sidan kan vi få ett n-siffrigt tal av typ c genom att ta ett (n-1)-siffrigt tal av typ a och d genom att lägga till en 2:a respektive en 1:a på slutet. Detta ger

c_n=2c_n-1+a_n-1+d_n-1

Dett totala antalet (n-1)-siffriga tal är 4^n-1 enligt multiplikationsprincipen. Vi har alltså också

4^n-1=a_n-1+b_n-1+c_n-1+d_n-1

så

a_n-1+d_n-1=4^n-1-b_n-1-c_n-1=4^n-1-2c_n-1

Detta ger nu

c_n=2c_n-1+4^n-1-2c_n-1=4^n-1

Svar: 4^n-1.