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


1.
Vi löser först hjälpekvationen

322x-347y=1

genom att använda Euklides algoritm:

\begin{displaymath} \begin{array} {rcl} 347&=&1\cdot 322+ 25\\ 322&=&12\cdot 25+22\\ 25&=&1\cdot22+3\\ 22&=&7\cdot 3+1\\ \end{array} \end{displaymath}

Detta ger

\begin{displaymath} \begin{array} {rcl} 1&=&22-7\cdot3=22-7(25-22)=8\cdot 22-7\... ...dot 322-103(347-322)= 111\cdot 322-103\cdot 347. \end{array} \end{displaymath}

Därmed är $x=3\cdot111=333$ och $y=3\cdot 103=309$ en lösning till ekvationen 322x-347y=3. Eftersom 322 och 347 är relativt prima ges samtliga lösningar av

\begin{displaymath} \begin{array} {rcl} x&=&333+347k\\ y&=&309+322k \end{array} \end{displaymath}

där k är ett godtyckligt heltal. Lösningarna är positiva om $k\geq 0$. Det gäller nu att bestämma det mista icke-negativa värdet på k så att $333+347k\equiv \mbox{ mod }5,$ d.v.s $3+2k\equiv 0,$ eller $2k\equiv -3\equiv 2$. Multiplikation med 3 (som är invers till 2 modulo 5) ger $k\equiv 1\mbox{ mod }5,$ så vi ska välja k=1.

Svar: x=680 och y=631.

2.
Eftersom $45=5\cdot 9$ och 5 och 9 är relativt prima räcker det att visa att 5 och 9 delar uttrycket. Vi kan visa detta genom att inse att uttrycket är modulo 5 och modulo 9.

Vi räknar först modulo 5 och får

\begin{displaymath} 10^{n}+26^{2n+1}+54\equiv 0+1^{2n+1}-1\equiv 0\mbox{ mod } 5. \end{displaymath}

Vi räknar sedan modulo 9 och får

\begin{displaymath} 10^{n}+26^{2n+1}+54\equiv 1^{n}+(-1)^{2n}(-1)+0\equiv 1-1\equiv 0 \mbox{ mod } 9. \end{displaymath}

Detta ger nu att $45=5\cdot 9$ delar uttrycket, eftersom 5 och 9 har 1 som största gemensam delare.

3.
Den nedersta ekvationen ger x=7+33k. Insatt i den andra ger detta

\begin{displaymath} 7+2k\equiv 5 \mbox{ mod } 31\mbox{ eller }2k\equiv -2\mbox{ mod }31. \end{displaymath}

Multiplikation med 15 ger $30k\equiv -30$ eller $-k\equiv 1$ mod 31. Vi ska alltså ha x=7+33(-1+31k1), för att de två nedersta ekvationerna ska gälla. Vi sätter in detta i den översta ekvationen och får

\begin{displaymath} 7+4(-1+2k_{1})\equiv 3\mbox{ mod }29 \mbox{ eller }8k_{1}\equiv 0\mbox{ mod }29. \end{displaymath}

Eftersom 8 är relativt prima med 29 är det inverterbart modulo 29. Multiplikation med en invers till 8 ger nu $k_{1}\equiv 0\mbox{ mod }29,$ eller k1=29k2, där k2 är godtyckligt.

Vi får alltså att $x=7+33(-1+31\cdot29k_{2}),$ där k2 är godtyckligt löser ekvationssystemet.

Den minsta positiva lösningen får vi om vi väljer k2=1 och då blir $x=7-33+29\cdot 31\cdot 28=29641$.

Svar: 29641.

4.
(a)
Vi gör en tabell:
n primtal <n produkten av dessa m faktorisering
2 2 2 3 3
3 2, 3 6 7 7
4 2, 3 6 7 7
5 2, 3, 5 30 31 31
6 2, 3, 5 30 31 31
7 2, 3, 5, 7 210 211 211
8 2, 3, 5, 7 210 211 211
9 2, 3, 5, 7 210 211 211
10 2, 3, 5, 7 210 211 211
11 2, 3, 5, 7, 11 2310 2311 2311
12 2, 3, 5, 7, 11 2310 2311 2311
13 2, 3, 5, 7, 11, 13 30030 30031 $59\cdot 509$

(b)
Nej! När n=13 är $m=59\cdot 509$.