Polecenie: Podać definicję relacji przystawania modulo oraz funkcji Eulera. Uzasadnij, że dla \( a, b, c, d \in \mathbb{Z} \) oraz \( m \in \mathbb{N} \) zachodzi: \[ (a \equiv b \mod m) \quad \text{oraz} \quad (c \equiv d \mod m) \Rightarrow ac \equiv bd \mod m. \]
Definicja relacji modulo:
Mówimy, że liczby całkowite \( a \) i \( b \) są przystające modulo \( m \) (zapisujemy \( a \equiv b \mod m \)),
jeśli \( m \) dzieli różnicę \( a - b \), czyli istnieje pewne \( k \in \mathbb{Z} \) takie, że:
\[
a - b = km.
\]
Funkcja Eulera \( \varphi(n) \):
Funkcja przypisuje każdej liczbie naturalnej \( n \) liczbę dodatnich liczb całkowitych mniejszych od \( n \),
które są z \( n \) względnie pierwsze. Formalnie:
\[
\varphi(n) = \Bigl|\{ k \in \mathbb{N} : 1 \leq k < n \text{ oraz } \gcd(k,n) = 1 \}\Bigr|.
\]
Zakładamy, że:
\[ \begin{aligned} a &\equiv b \mod m \quad \Longrightarrow\quad a = b + km,\quad k \in \mathbb{Z},\\[1mm] c &\equiv d \mod m \quad \Longrightarrow\quad c = d + lm,\quad l \in \mathbb{Z}. \end{aligned} \]Mnożymy obie równości:
\[ ac = (b + km)(d + lm) = bd + b(lm) + d(km) + (km)(lm). \]Zauważamy, że:
\[ ac = bd + m\Bigl(b\,l + d\,k + k\,l\,m\Bigr). \]Stąd \( ac - bd \) jest podzielne przez \( m \), czyli: \[ ac \equiv bd \mod m. \]
Polecenie: Sformułować i uzasadnić małe twierdzenie Fermata.
Twierdzenie:
Jeśli \( p \) jest liczbą pierwszą, a \( a \) jest liczbą całkowitą niepodzielną przez \( p \)
(czyli \(\gcd(a,p)=1\)), to:
\[
a^{p-1} \equiv 1 \mod p.
\]
Rozważmy zbiór reszt modulo \( p \): \( \{1,2,\dots,p-1\} \). Mnożąc każdy element przez \( a \) otrzymujemy zbiór:
\[ \{a\cdot1,\,a\cdot2,\,\dots,\,a\cdot(p-1)\}. \]Przy \(\gcd(a,p)=1\) mnożenie przez \( a \) jest bijekcją, więc: \[ a^{p-1}\,(p-1)! \equiv (p-1)! \mod p. \]
Skoro \( (p-1)! \) jest względnie pierwszy z \( p \), możemy „skracać” przez \( (p-1)! \) i uzyskujemy: \[ a^{p-1} \equiv 1 \mod p \quad \square. \]
Polecenie: Dla równania rekurencyjnego \( A_{n+2} = \alpha A_{n+1} + \beta A_n \) (dla \(\alpha \neq 0, \beta \neq 0\)) podać definicję równania charakterystycznego oraz sformułować i uzasadnić postać rozwiązania równania.
Równanie charakterystyczne:
Dla równania rekurencyjnego:
\[
A_{n+2} = \alpha A_{n+1} + \beta A_n,
\]
przyjmujemy rozwiązanie postaci \( A_n = r^n \). Po podstawieniu otrzymujemy:
\[
r^{n+2} = \alpha r^{n+1} + \beta r^n \quad \Longrightarrow \quad r^2 = \alpha r + \beta,
\]
czyli równanie charakterystyczne:
\[
r^2 - \alpha r - \beta = 0.
\]
Niech \( r_1 \) i \( r_2 \) będą pierwiastkami równania charakterystycznego.
Polecenie: Podać definicje wariacji, kombinacji i permutacji (z powtórzeniami i bez powtórzeń) oraz wskazać liczbę takich obiektów.
Bez powtórzeń:
Liczba wariacji:
\[
V(n,k) = \frac{n!}{(n-k)!}.
\]
Przykład: ustawienie 3 osób na 5 stanowiskach.
Z powtórzeniami:
Każdy z \( k \) elementów wybieramy spośród \( n \) możliwości:
\[
\overline{V}(n,k) = n^k.
\]
Przykład: 3-znakowe hasło z 10 cyfr.
Bez powtórzeń:
Liczba kombinacji:
\[
C(n,k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}.
\]
Przykład: wybór 3-osobowej komisji z 10 osób.
Z powtórzeniami:
Liczba kombinacji z powtórzeniami:
\[
\overline{C}(n,k) = \binom{n+k-1}{k}.
\]
Przykład: rozdanie 10 identycznych cukierków 4 dzieciom.
Bez powtórzeń:
Liczba permutacji:
\[
P(n) = n!.
\]
Przykład: ułożenie 5 książek na półce.
Z powtórzeniami:
Gdy mamy \( n \) elementów, gdzie \( k_1, k_2, \dots, k_m \) to liczby powtórzeń:
\[
P(n; k_1, k_2, \dots, k_m) = \frac{n!}{k_1!\,k_2!\,\cdots\,k_m!}.
\]
Przykład: anagramy słowa „MATEMATYKA”.
Polecenie: Podać definicje i przykłady grafów: a) pełnego, b) dwudzielnego pełnego, c) dwudzielnego, d) drzewa, e) cyklu Eulera.
a) Graf pełny \(K_4\): Każdy wierzchołek połączony z każdym innym.
b) Graf dwudzielny pełny \(K_{3,3}\): Wierzchołki podzielone na dwa zbiory; każda para wierzchołków z różnych zbiorów jest połączona krawędzią.
c) Graf dwudzielny (niepełny): Przykładowo, podzielone na dwa zbiory: \(X = \{A, B, C\}\) oraz \(Y = \{D, E\}\) z krawędziami: A-D, A-E, B-D, C-E.
d) Drzewo: Graf spójny bez cykli, w którym między dowolnymi dwoma wierzchołkami istnieje dokładnie jedna ścieżka.
e) Cykl Eulera: Cykl przechodzący każdą krawędź grafu dokładnie jeden raz. Warunek: graf spójny, a każdy wierzchołek ma parzysty stopień. Przykład: kwadratowy graf z wierzchołkami \(A, B, C, D\) oraz krawędziami \(A-B\), \(B-C\), \(C-D\), \(D-A\).