\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}
\begin{document}
{\sf KTH Matematik}
\begin{center} 
 {\bf 5B1118 Diskret Matematik \\
Kontrollskrivning 1 \\
M{\aa}ndagen den 15 Mars, 2004 \\
L\"osning}
\end{center}

\vspace{.3in}


\begin{enumerate}
\item (3p) Betrakta f\"oljande delm\"angderna av $\zed^+$:
$$A=\{n\in\zed^+|n\leq 1000 \text{ och }n=k^2\text{, d\"ar }k\in\zed^+\}$$
$$B=\{n\in\zed^+|n\leq 1000 \text{ och }n=h^3\text{, d\"ar }h\in\zed^+\}$$
Ber\"akna $|A\cup B|$.

$A=\{1^2,2^2,..., 31^2\}$ och $\{1^3, 2^3,...,10^3\}$. S{\aa} $|A|=31$ och $|B|=10$. Enligt inklusion-exklusionsprincipen \"ar:
$$|A\cup B|=|A|+|B|-|A\cap B|$$
Vi ska ber\"akna kardinalitaten av $A\cap B=\{n\in\zed^+|n\leq 1000 \text{ och }n=k^2=h^3\text{, d\"ar }k,h\in\zed^+\}$. Men om $k^2=h^3$ s{\aa} $k=m^3$ och $h=i^2$ d\"ar $i,m\in\zed^+$. Vi ska hitta vilka elemnt in $B$ \"ar p{\aa} formen $i^6$. Del finns bara $1,64,729$ s{\aa} $|A\cap B|=3$ och $|A\cup B|=31+10-3=38$.

Svaret \"ar ${\bf 38}$.
\vspace{.7in}

\item(3p) L\aa t $m\in\zed^+$. Visa, med hj\"alp av induktion, att
$$\text{Om }a\equiv_m b\text{ \hspace{.2in}d{\aa}\hspace{.2in} }a^n\equiv_m b^n\text{\hspace{.2in} f\"or }n\geq 1$$

Detta \"ar sant f\"or $n=1$. Antag att $a^n\equiv_m b^n$ g\"aller f\"or $n\leq k$. Vi ska visa att $a^{k+1}\equiv_m b^{k+1}$.

$$a^{k+1}=a\cdot a^k\equiv_m b\cdot b^k=b^{k+1}$$

eller:

$a\equiv_m b$ betyder att $a=mt+b$, d\"ar $t\in\zed$, och $a^{k}\equiv_m b^{k}$ betyder att $a^k=hm+b^k$, d\"ar $h\in\zed$.

$$a^{k+1}=a^k\cdot a= (hm+b^k)(mt+b)=m(mht+hb+tb^k)+b^{k+1}$$

S{\aa} $a^{k+1}\equiv_m b^{k+1}$.
\vspace{.7in}

\item(3p) L\"os f\"oljande diofantiska eknation:
$$10x+36y=8$$

\[ \begin{array}{lllll}
36&=&10\cdot 3& + & 6\\
10&=&6 & + & 4\\
6&=&4&+&{\bf 2}\\
4&=&2\cdot 2&
\end{array}\]
S{\aa} $sgd(36,10)=2$ och:
$$2=6-4=6-(10-6)=2\cdot (36-3\cdot 10)-10=2\cdot 26-7\cdot 10$$
Par $(-7,2)$ \"ar EN l\"osning till $10x+36y=2$ s{\aa} par  $(-28,8)$ \"ar EN l\"osning till $10x+36y=8$. Nu ska man hitta den allm\"anna l\"osning med hj\"alp av $lcd$. Vi vet att:
 $$lsd(10, 36)=2^2\cdot 3^2\cdot 5=10\cdot 18=36\cdot 5$$
S{\aa} vi har att:
$$10\cdot (-28)+36\cdot 8+(10\cdot 18-36\cdot 5)k=(-28+18k)\cdot 10+(8-5k)\cdot 36=8$$
Del alm\"anna l\"osning \"ar $x=-28+18k, y=8-5k$.


 
\end{enumerate}



\end{document}