Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Geordnete Mengen/Abbildung/Antimonoton/Definition/Begriff
2. Multinomialkoeffizient/Definition/Begriff
3. Der Grad eines Punktes ${\displaystyle {}v\in V}$ in einem Graphen ${\displaystyle {}G=(V,E)}$.
4. Ungerichteter Graph/Zusammenhängend/Definition/Begriff
5. Ungerichteter Graph/Bipartit/Definition/Begriff
6. Ungerichter Graph/Paarung/Punktabdeckung/Definition/Begriff

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

Sei ${\displaystyle {}n\in \mathbb {N} }$ und ${\displaystyle {}\mathbb {Z} /(n)}$ der zugehörige Restklassenring. Zeige, dass ${\displaystyle {}a\in \mathbb {Z} }$ eine Einheit modulo ${\displaystyle {}n}$ genau dann ist, wenn ${\displaystyle {}a}$ und ${\displaystyle {}n}$ teilerfremd sind.

Sind ${\displaystyle {}a}$ und ${\displaystyle {}n}$ teilerfremd, so gibt es nach Fakt ***** eine Darstellung der ${\displaystyle {}1}$, es gibt also ganze Zahlen ${\displaystyle {}r,s}$ mit

${\displaystyle {}ra+sn=1\,.}$

Betrachtet man diese Gleichung modulo ${\displaystyle {}n}$, so ergibt sich ${\displaystyle {}ra=1}$ in ${\displaystyle {}\mathbb {Z} /(n)}$. Damit ist ${\displaystyle {}a}$ eine Einheit mit Inversem ${\displaystyle {}a^{-1}=r}$.

Ist umgekehrt ${\displaystyle {}a}$ eine Einheit in ${\displaystyle {}\mathbb {Z} /(n)}$, so gibt es ein ${\displaystyle {}r\in \mathbb {Z} /(n)}$ mit ${\displaystyle {}ar=1}$ in ${\displaystyle {}\mathbb {Z} /(n)}$. Das bedeutet aber, dass ${\displaystyle {}ar-1}$ ein Vielfaches von ${\displaystyle {}n}$ ist, so dass also

${\displaystyle {}ar-1=sn\,}$

gilt. Dann ist aber wieder ${\displaystyle {}ar-sn=1}$ und ${\displaystyle {}a}$ und ${\displaystyle {}n}$ sind teilerfremd.