Förslag till lösning av Inlämningsuppgifter II

1.

Vi beräknar den största gemensamma delaren till 273 och 104 med hjälp av Euklides algoritm:

$$\begin{array} {rcl}273&=&2\cdot 104+65\\ 104&=&1\cdot 65+39... ...1\cdot 39 +26\\ 39&=&1\cdot 26+13\\ 26&=&2\cdot 13\end{array}$$

Den störtsta gemensamma delaren är alltså 13. Vi dividerar ekvationen med detta och får 8x-21y=121. Vi löser hjälpekvationen

8x-21y=1

med Euklides algoritm för största gemensamma delaren till 21 och 8 baklänges:

$$\begin{array} {rcl} 21&=&2\cdot 8+5\\ 8&=&1\cdot 5+3\\ 5&=&1\cdot 3+2\\ 3&=&1\cdot 2+1\end{array}$$

Vi får

$$\begin{array} {rcl} 1&=&3-2=3-(5-3)=2\cdot 3-5=2(8-5)-5=2\cd... ...&=&2\cdot 8-3\cdot (21-2\cdot 8)=8\cdot 8-3\cdot 21.\end{array}$$

Ekvationen 8x-21y=1 har alltså lösningen $x=8,\,y=3$ och därmed har 8x-21y=121 lösningen $x=121\cdot 8=968,\,y=121\cdot 3=363$.Eftersom 8 och 21 är relativt prima ges samtliga lösningar av

$$\left\{\begin{array} {rcl} x&=&968+21k\\ y&=&363+8k\end{array}\right.$$

där k är ett godtyckligt heltal. Genom att ersätta k med k-45 får vi istället följande uttryck för lösningarna

$$\left\{\begin{array} {rcl} x&=&23+21k\\ y&=&3+8k\end{array}\right.$$

där k är ett godtyckligt heltal.

Svar: $x=23+21k,\, y=3+8k$ där k är ett godtyckligt heltal. De positiva lösningarna fås när $k\geq 0$.

2.

Vi har att $19\equiv 8 \mbox{ mod }11$ och vi gör en tabell över potenser av 8 modulo 11:

$$\begin{array} {l\vert l\vert l\vert l\vert l\vert l} n&1&2&3... ...8^{n}&8&64\equiv 9&72\equiv 6&48\equiv 4&32\equiv -1\end{array}$$

Vi har alltså att $8^{5}\equiv -1 \mbox{ mod }11$ och att $6\equiv 8^{3}$. Med hjälp av detta får vi

$$19^{25}\equiv 8^{25}=(8^{5})^{5}\equiv -1\mbox{ och } 6^{34}... ...102}\equiv (8^{5})^{20}8^{2}\equiv 8^{2}\equiv 9 \mbox{ mod 11}$$

Detta ger nu

$$(19^{25}+6^{34})^{1001}\equiv (-1+9)^{1001}\equiv (8^{5})^{200}8\equiv 8\mbox{ mod }11.$$

Svar: 8.

3.

(a)

Enligt kinesiska restsatsen finns bara ett tal mindre än p_Ap_Bp_C(>n) som har resten $n_{A},\,n_{B}$ och n_C vid division med $p_{A},\,p_{B}$ respektive p_C. Detta är talet n. Om man bara känner t.ex. (n_A,p_A) och (n_B,p_B) ger kinesiska restsatsen att n är något av talen m+kp_Ap_B, där m är resten av n vid division med p_Ap_B och k är icke-negativt. Antag att p_A är det minsta av p_A och p_B.

Den enda ytterligare information vi har om n är att n<p_A³(<p_B³) Allt vi vet är att k ska väljas så att m+kp_Ap_B<p_A³, dvs

$$0\leq k<p_{A}^{2}/p_{B}-m/p_{A}p_{B}$$

Eftersom m<p_Ap_B och p_A och p_B är av samma storleksordning, ger detta ungefär p_A möjliga val för k. Eftersom n förutsätts vara stort kommer därför antalet möjligheter för k att vara så stort och det är i praktiken omöjligt att pröva alla möjligheter.

(b)

Vi ska lösa ekvationssystemet

$$\left\{ \begin{array} {rcrcr} n &\equiv& 54&\mbox{mod}& 89... ...{mod}& 97\\ n &\equiv& 45 &\mbox{mod}& 101 \end{array}\right.$$

Den nedersta ekvationen löses av n=45+101k₁, där k₁ kan väljas godtyckligt. För att även den andra ekvationen ska lösas krävs att (insättning av n=45+101k₁ i den andra ekvationen)

$$45+101k_{1}\equiv 1\mbox{ mod }97\mbox{ dvs }4k_{1}\equiv -44\mbox{ mod }97$$

Eftersom $\mbox{sgd(4,97)}=1$ är 4 inverterbart modulo 97 och multiplikation med en invers till 4 ger

$$k_{1}\equiv -11\mbox{ mod }97\mbox{ dvs }k_{1}=-11+97k_{2},$$

där k₂ är ett godtyckligt heltal. De två nedersta ekvationerna stämmer alltså om

n=45+101k₁=45+101(-11+97k₂)

Vi bestämmer k₂ så att öven den första ekvationen gäller. Insättning av n=45+101(-11+97k₂) ger (modulo 89)

$$\begin{array} {c} 45+101(-11+97k_{2})\equiv 54\\ \Leftri... ...t 8k_{2}\equiv 9+132\Leftrightarrow 7k_{2}\equiv 52.\end{array}$$

Vi ser att vi behöver bestämma en invers till 7 modulo 89. Vi gör detta med Euklides algoritm för största gemensamma delaren till 7 och 89:

$$\begin{array} {rcl} 89=12\cdot 7+5\\ 7=1\cdot 5+2\\ 5=2\cdot 2+1\end{array}$$

Vi får alltså $1=5-2\cdot 2=5-2\cdot(7-5)=3\cdot 5-2\cdot 7=3(89-12\cdot 7)-2\cdot 7$. Modulo 89 ger detta $1\equiv -38\cdot 7\equiv 51\cdot 7$.Detta ger nu

$$k_{2}\equiv 51\cdot 52\equiv 71\mbox{ mod }89\mbox{ dvs }k_{2}=71+89k_{3}$$

där k₃ är godtyckligt. Vi får alltså

$$n=45+101(-11+97k_{2})=45+101(-11)+101\cdot 97(71+89k_{3})$$

Det minsta icke-negativa talet bland dessa fås när k₃=0, dvs

$$n=45-1111+9797\cdot 71=694521$$

Översättning till bokstäver ger att lösenordet är fideba .

Svar: fideba

4.

Gruppen $(\mathbb Z/23)^{\times}$ består av alla rester vid division med 23 som är relativt prima med 23. Eftersom 23 är ett primtal gäller att

$$(\mathbb Z/23)^{\times}=\{1,2,3,4,5,\ldots ,20,21,22\}$$

är en grupp av ordning $22=2\cdot 11$. En delgrupp till $(\mathbb Z/23)^{\times}$ ha enligt Lagranges sats därför ordning $1,\,2,\,11$eller 22.

Dett finns bara en delgrupp av ordning 1 och 22. De är $\{1\}$respektive $(\mathbb Z/23)^{\times}.$

Eftersom 2 och 11 är primtal är (enligt Lagranges sats) grupper av dessa ordningar cykliska och alltså av formen $\langle a\rangle$ för något $a\in (\mathbb Z/23)^{\times}$.

Vi undersöker $\langle 2\rangle$ och får

$$\begin{array} {rcl} \langle 2\rangle &=&\{2,2^{2}=4,\,2^{3}=... ...{7}=13,2^{8}=3,\\ & &~~2^{9}=6,2^{10}=12,2^{11}=1\}\end{array}$$

Elementen i denna mängd har alla ordning som delar 11. Vi tar ett element som inte förekommer i mängden (t.ex. det minsta dvs 5) och undersöker

$$\begin{array} {rcl} \langle 5\rangle&=&\{5,5^{2}=2,5^{3}=10,... ...{8}=16,\\ & &~~5^{9}=11,5^{10}=9,5^{11}=22,\ldots\}\end{array}$$

Vi ser att ordningen av 5 är >11 och därför 22 enligt Lagranges sats. Detta ger att $(\mathbb Z/23)^{\times}$ är cyklisk. Den har därför precis en delgrupp av ordning d för varje delare till 22. Vi har redan sett att $\langle 2\rangle$ är en delgrupp av ordning 11. En delgrupp av ordning 2 ges av $\langle 22\rangle$ ty 22²=(-1)²=1.

Svar: Delgrupperna är $\{1\},\,\langle 22\rangle,\,\langle 2\rangle$ samt $(\mathbb Z/23)^{\times}(=\langle 5\rangle)$.