Diskret matematik · 2026-08-11
Blandade frågor.
Finn $\operatorname{SGD}(240,154)$ med Euklides algoritm.
Beräkna resten då $5^{40}$ delas med 11.
Ge exempel på en mängd $A$ sådan att $\lvert A\times A\rvert=9$, där mängden $A\times A$ består av alla ordnade par av element ur mängden $A$.
(a) Euklides algoritm ger
$$
\begin{aligned}
240&=1\cdot154+86,&154&=1\cdot86+68,\\
86&=1\cdot68+18,&68&=3\cdot18+14,\\
18&=1\cdot14+4,&14&=3\cdot4+2,\\
4&=2\cdot2.
\end{aligned}
$$
Den sista icke-nollresten är $2$. Alltså är $\operatorname{SGD}(240,154)=2$.
(b) Vi räknar modulo $11$. Eftersom $5^5=3125\equiv1\pmod{11}$ får vi
$$
5^{40}=(5^5)^8\equiv1^8\equiv1\pmod{11}.
$$
Resten är alltså $1$.
(c) För en ändlig mängd gäller $|A\times A|=|A|^2$. Vi behöver därför $|A|=3$. Ett exempel är $A=\{1,2,3\}$. Då har $A\times A$ precis $3\cdot3=9$ element.