Problem assets/algorithms/extended-algorytm-euklidesa.tex

← Back
Algorytm 1% \caption{Rozszerzony algorytm Euklidesa}
Rozważmy dwie liczby całkowite \( a \) i \( b \). Celem jest znalezienie ich największego wspólnego dzielnika \( \gcd(a, b) \) oraz współczynników \( x \) i \( y \), takich że: \[ ax + by = \gcd(a, b) \]
Kroki algorytmu:
  1. Ustal początkowe wartości: \[ r_0 = a, \quad r_1 = b \] \[ s_0 = 1, \quad s_1 = 0 \] \[ t_0 = 0, \quad t_1 = 1 \]
  2. Powtarzaj kroki aż \( r_1 = 0 \):
    1. Oblicz iloraz \( q \) z dzielenia \( r_0 \) przez \( r_1 \): \[ q = \left\lfloor \frac{r_0}{r_1} \right\rfloor \]
    2. Oblicz resztę \( r_2 \): \[ r_2 = r_0 - q \cdot r_1 \] Zaktualizuj reszty: \[ r_0 \leftarrow r_1, \quad r_1 \leftarrow r_2 \]
    3. Zaktualizuj współczynniki \( s \) i \( t \): \[ s_2 = s_0 - q \cdot s_1 \] \[ s_0 \leftarrow s_1, \quad s_1 \leftarrow s_2 \] \[ t_2 = t_0 - q \cdot t_1 \] \[ t_0 \leftarrow t_1, \quad t_1 \leftarrow t_2 \]
  3. Gdy \( r_1 = 0 \), zwróć \( s_0 \) i \( t_0 \). Wtedy spełnione jest: \[ ax + by = \gcd(a, b) \] gdzie \( x = s_0 \) i \( y = t_0 \). 
\begin{orangebox}{Rozszerzony algorytm Euklidesa}
    \begin{algorithmic}
        % \caption{Rozszerzony algorytm Euklidesa}
        \label{a:extended-algorytm-euklidesa}
        Rozważmy dwie liczby całkowite \( a \) i \( b \). Celem jest znalezienie ich największego wspólnego dzielnika \( \gcd(a, b) \) oraz współczynników \( x \) i \( y \), takich że:
        \[
        ax + by = \gcd(a, b)
        \]
        
        \textbf{Kroki algorytmu:}
        \begin{enumerate}
            \item Ustal początkowe wartości:
            \[
            r_0 = a, \quad r_1 = b
            \]
            \[
            s_0 = 1, \quad s_1 = 0
            \]
            \[
            t_0 = 0, \quad t_1 = 1
            \]
            \item Powtarzaj kroki aż \( r_1 = 0 \):
            \begin{enumerate}
                \item Oblicz iloraz \( q \) z dzielenia \( r_0 \) przez \( r_1 \):
                \[
                q = \left\lfloor \frac{r_0}{r_1} \right\rfloor
                \]
                \item Oblicz resztę \( r_2 \):
                \[
                r_2 = r_0 - q \cdot r_1
                \]
                Zaktualizuj reszty:
                \[
                r_0 \leftarrow r_1, \quad r_1 \leftarrow r_2
                \]
                \item Zaktualizuj współczynniki \( s \) i \( t \):
                \[
                s_2 = s_0 - q \cdot s_1
                \]
                \[
                s_0 \leftarrow s_1, \quad s_1 \leftarrow s_2
                \]
                \[
                t_2 = t_0 - q \cdot t_1
                \]
                \[
                t_0 \leftarrow t_1, \quad t_1 \leftarrow t_2
                \]
            \end{enumerate}
            \item Gdy \( r_1 = 0 \), zwróć \( s_0 \) i \( t_0 \). Wtedy spełnione jest:
            \[
            ax + by = \gcd(a, b)
            \]
            gdzie \( x = s_0 \) i \( y = t_0 \).
        \end{enumerate}
    \end{algorithmic}
\end{orangebox}
Generated from: ./assets/algorithms/extended-algorytm-euklidesa.tex