MM2001 · Diskret matematik
Grundläggande talteori och polynom.
Ge exempel på tre olika element i mängden $\{n\in\mathbb{Z}:n\equiv4\pmod 9\}$.
Bestäm resten då $2^{101}$ delas med 33.
Lista alla möjliga rationella rötter till polynomet $3x^4-7x^2+2$ enligt rationella rotsatsen.
(a) Vi söker heltal $n$ sådana att $n\equiv4\pmod 9$. Detta betyder att $n=4+9k$ för något $k\in\mathbb Z$. Exempel: $4$, $13$, $22$.
(b) Vi beräknar resten då $2^{101}$ delas med $33$. Notera att $33=3\cdot11$.
Modulo $3$ gäller $2\equiv-1\pmod3$, och därför
$$
2^{101}\equiv(-1)^{101}=-1\equiv2\pmod3.
$$
Modulo $11$ ger Eulers sats, eftersom $\varphi(11)=10$ och $\gcd(2,11)=1$, att $2^{10}\equiv1\pmod{11}$. Eftersom $101=10\cdot10+1$ får vi $2^{101}\equiv2^1\equiv2\pmod{11}$. Alltså är $x\equiv2\pmod3$ och $x\equiv2\pmod{11}$, vilket direkt ger $x\equiv2\pmod{33}$. Resten är alltså $2$.
(c) Polynomet är
$$
3x^4-7x^2+2.
$$
Enligt rationella rotsatsen är möjliga rationella rötter $\pm p/q$, där $p$ delar konstanttermen $2$ och $q$ delar den ledande koefficienten $3$. Alltså är $p=\pm1,\pm2$ och $q=\pm1,\pm3$, vilket ger de möjliga rationella rötterna
$$
\pm1,\ \pm2,\ \pm\frac13,\ \pm\frac23.
$$
Diofantiska ekvationer. Betrakta den diofantiska ekvationen $154x+198y=n$.
Beräkna $\operatorname{SGD}(154,198)$.
För $n=2026$, bestäm om ekvationen är lösbar. Motivera ditt svar.
Bestäm det minsta positiva heltalet $n$ för vilket ekvationen har heltalslösningar samt hitta alla lösningar till den.
Vi studerar ekvationen
$$
154x+198y=n.
$$
(a) Primtalsfaktorisering:
$$
154=2\cdot7\cdot11,\qquad 198=2\cdot3^2\cdot11.
$$
Alltså är $\gcd(154,198)=2\cdot11=22$.
(b) Ekvationen är lösbar om och endast om $22\mid n$. Eftersom
$$
2026=22\cdot92+2
$$
är $2026$ inte delbart med $22$. Ekvationen är därför inte lösbar.
(c) Minsta positiva $n$ är $\gcd(154,198)=22$. Dividera ekvationen med $22$:
$$
7x+9y=1.
$$
Med utvidgade Euklides algoritm får vi
$$
9=7\cdot1+2,\qquad 7=2\cdot3+1,
$$
och därmed
$$
1=7-2\cdot3=7-(9-7)\cdot3=4\cdot7-3\cdot9.
$$
Alltså kan vi välja $x_0=4$ och $y_0=-3$. Alla lösningar är
$$
x=4+9t,\qquad y=-3-7t,\qquad t\in\mathbb Z.
$$
Olikheter. Finn alla reella lösningar till olikheten $\frac{x^2-4}{x+1}\ge0$.
Vi har
$$
\frac{x^2-4}{x+1}=\frac{(x-2)(x+2)}{x+1}\ge0.
$$
De kritiska punkterna är $x=-2,-1,2$. Ett teckenschema ger lösningen
$$
[-2,-1)\cup[2,\infty).
$$
Komplexa tal. Lös ekvationen $z^2-(4+2i)z+(3+2i)=0$ för $z\in\mathbb{C}$.
Ekvationen är
$$
z^2-(4+2i)z+(3+2i)=0.
$$
Diskriminanten är
$$
\Delta=(4+2i)^2-4(3+2i)
=(16+16i+4i^2)-(12+8i)=8i.
$$
Vi söker en kvadratrot till $8i$. Eftersom
$$
8i=8e^{i\pi/2}
$$
får vi
$$
\sqrt{8i}=\sqrt8\,e^{i\pi/4}
=2\sqrt2\,\frac{1+i}{\sqrt2}=2(1+i).
$$
Alltså
$$
z=\frac{4+2i\pm2(1+i)}2.
$$
Med plustecknet blir $z_1=(6+4i)/2=3+2i$, och med minustecknet blir $z_2=2/2=1$. Svar: $z=3+2i$ eller $z=1$.
Kombinatorik. Vi har ordet TENTAMEN.
På hur många sätt kan bokstäverna i ordet permuteras?
På hur många av dessa sätt står de två E:na inte bredvid varandra?
Ordet är TENTAMEN, med bokstäverna $T,T,E,E,N,N,A,M$.
(a) Antalet permutationer är
$$
\frac{8!}{2!\,2!\,2!}=\frac{40320}{8}=5040.
$$
(b) För att räkna de permutationer där $E$ står bredvid $E$ behandlar vi $EE$ som en bokstav. Då har vi sju objekt, med upprepningarna $T,T,N,N$, och antalet blir
$$
\frac{7!}{2!\,2!}=\frac{5040}{4}=1260.
$$
Antalet där $E$ inte står bredvid varandra är därför
$$
5040-1260=3780.
$$
Induktion. Visa med induktion att $3^n>2^n+10$ för alla heltal $n\ge3$.
Vi ska visa att
$$
3^n>2^n+10\qquad\text{för }n\ge3.
$$
Basfall: för $n=3$ är $3^3=27$ och $2^3+10=18$, så påståendet är sant.
Antag att $3^k>2^k+10$ för något $k\ge3$. Då får vi
$$
3^{k+1}=3\cdot3^k>3(2^k+10)=3\cdot2^k+30.
$$
Vi vill visa att högerledet är större än $2^{k+1}+10$. Eftersom
$$
3\cdot2^k=2^{k+1}+2^k
$$
är
$$
3\cdot2^k+30=2^{k+1}+2^k+30>2^{k+1}+10,
$$
då $2^k\ge8$ för $k\ge3$. Alltså gäller påståendet för $k+1$, och därmed för alla $n\ge3$.