Problem assets/proof/fakcik/numbertheory/relationship-gcd-lcm.tex

← Back
Proof. Aby udowodnić równość \( \text{lcm}(x, y) = \frac{x \cdot y}{\gcd(x, y)} \), przypomnijmy definicje funkcji LCM (najmniejszej wspólnej wielokrotności) oraz GCD (największego wspólnego dzielnika):
  • Największy wspólny dzielnik \( \gcd(x, y) \) to największa liczba, która dzieli zarówno \( x \), jak i \( y \).
  • Najmniejsza wspólna wielokrotność \( \text{lcm}(x, y) \) to najmniejsza liczba, która jest podzielna zarówno przez \( x \), jak i \( y \).
Rozkładając \( x \) i \( y \) na czynniki pierwsze: \[ x = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}, \quad y = p_1^{f_1} p_2^{f_2} \dots p_k^{f_k}, \] gdzie \( p_1, p_2, \dots, p_k \) to różne liczby pierwsze, a \( e_1, e_2, \dots, e_k \) oraz \( f_1, f_2, \dots, f_k \) to wykładniki tych liczb w rozkładach na czynniki pierwsze.
Wówczas: \[ \gcd(x, y) = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \dots p_k^{\min(e_k, f_k)}, \] oraz \[ \text{lcm}(x, y) = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \dots p_k^{\max(e_k, f_k)}. \]
Iloczyn \( x \cdot y \) to: \[ x \cdot y = p_1^{e_1 + f_1} p_2^{e_2 + f_2} \dots p_k^{e_k + f_k}. \]
Teraz obliczmy \( \frac{x \cdot y}{\gcd(x, y)} \): \[ \frac{x \cdot y}{\gcd(x, y)} = \frac{p_1^{e_1 + f_1} p_2^{e_2 + f_2} \dots p_k^{e_k + f_k}}{p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \dots p_k^{\min(e_k, f_k)}}. \] Po uproszczeniu, otrzymujemy: \[ \frac{x \cdot y}{\gcd(x, y)} = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \dots p_k^{\max(e_k, f_k)} = \text{lcm}(x, y). \]
Stąd udowodniliśmy, że: \[ \text{lcm}(x, y) = \frac{x \cdot y}{\gcd(x, y)}. \] ■
\begin{redbox}{Dowód fakciku \ref{fakcik:relationship-gcd-lcm}}
\begin{proof}
    Aby udowodnić równość \( \text{lcm}(x, y) = \frac{x \cdot y}{\gcd(x, y)} \), przypomnijmy definicje funkcji LCM (najmniejszej wspólnej wielokrotności) oraz GCD (największego wspólnego dzielnika):
    
    \begin{itemize}
        \item Największy wspólny dzielnik \( \gcd(x, y) \) to największa liczba, która dzieli zarówno \( x \), jak i \( y \).
        \item Najmniejsza wspólna wielokrotność \( \text{lcm}(x, y) \) to najmniejsza liczba, która jest podzielna zarówno przez \( x \), jak i \( y \).
    \end{itemize}
    
    Rozkładając \( x \) i \( y \) na czynniki pierwsze:
    \[
    x = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}, \quad y = p_1^{f_1} p_2^{f_2} \dots p_k^{f_k},
    \]
    gdzie \( p_1, p_2, \dots, p_k \) to różne liczby pierwsze, a \( e_1, e_2, \dots, e_k \) oraz \( f_1, f_2, \dots, f_k \) to wykładniki tych liczb w rozkładach na czynniki pierwsze.
    
    Wówczas:
    \[
    \gcd(x, y) = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \dots p_k^{\min(e_k, f_k)},
    \]
    oraz
    \[
    \text{lcm}(x, y) = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \dots p_k^{\max(e_k, f_k)}.
    \]
    
    Iloczyn \( x \cdot y \) to:
    \[
    x \cdot y = p_1^{e_1 + f_1} p_2^{e_2 + f_2} \dots p_k^{e_k + f_k}.
    \]
    
    Teraz obliczmy \( \frac{x \cdot y}{\gcd(x, y)} \):
    \[
    \frac{x \cdot y}{\gcd(x, y)} = \frac{p_1^{e_1 + f_1} p_2^{e_2 + f_2} \dots p_k^{e_k + f_k}}{p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \dots p_k^{\min(e_k, f_k)}}.
    \]
    Po uproszczeniu, otrzymujemy:
    \[
    \frac{x \cdot y}{\gcd(x, y)} = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \dots p_k^{\max(e_k, f_k)} = \text{lcm}(x, y).
    \]
    
    Stąd udowodniliśmy, że:
    \[
    \text{lcm}(x, y) = \frac{x \cdot y}{\gcd(x, y)}.
    \]
\end{proof}
\end{redbox}
Generated from: ./assets/proof/fakcik/numbertheory/relationship-gcd-lcm.tex