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

\begin{redbox}{Dowód algorytmu \ref{a:algorytm-euklidesa}}
\begin{proof}
    Załóżmy, że \( x \) i \( y \) są dwoma liczbami całkowitymi, przy czym \( y > x \). Chcemy udowodnić, że:
    \[
    \gcd(x, y) = \gcd(x, y - x).
    \]
    
    Rozpocznijmy dowód. Niech \( d = \gcd(x, y) \). Oznacza to, że \( d \) jest największym wspólnym dzielnikiem obu liczb \( x \) i \( y \), czyli \( d \) dzieli zarówno \( x \), jak i \( y \). Zatem istnieją liczby całkowite \( q_1 \) i \( q_2 \), takie że:
    \[
    x = d q_1 \quad \text{oraz} \quad y = d q_2.
    \]
    Oznacza to, że \( d \) dzieli również \( y - x \), ponieważ:
    \[
    y - x = d q_2 - d q_1 = d (q_2 - q_1).
    \]
    Zatem \( d \) dzieli \( y - x \), co implikuje, że \( d \) jest wspólnym dzielnikiem \( x \) i \( y - x \).
    
    Teraz, niech \( d' = \gcd(x, y - x) \). Oznacza to, że \( d' \) jest największym wspólnym dzielnikiem \( x \) i \( y - x \), czyli \( d' \) dzieli zarówno \( x \), jak i \( y - x \). Ponieważ \( d \) dzieli \( x \) i \( y - x \), to \( d \) jest także dzielnikiem \( d' \). Zatem \( d' \leq d \).
    
    Z drugiej strony, \( d' \) dzieli \( x \) i \( y - x \), a ponieważ \( y = x + (y - x) \), to \( d' \) dzieli także \( y \). Zatem \( d' \) jest dzielnikiem \( y \), co oznacza, że \( d' \leq d \). Zatem \( d' = d \).
    
    W ten sposób udowodniliśmy, że:
    \[
    \gcd(x, y) = \gcd(x, y - x).
    \]
\end{proof}
\end{redbox}