Problem OM 2.1.1

% NumberTheory, Algebra, Induction

\documentclass[a4paper,12pt]{article}

\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot,
    headheight=50pt]{geometry}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{float}
\usepackage[most]{tcolorbox}
\usepackage{enumitem}
\usepackage{graphicx}

\usepackage{amsmath, amsthm}

\usepackage{fontspec}
\usepackage{unicode-math}

\setmainfont{Linux Libertine O}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]

\newcommand{\Name}{Hostek}
\newcommand{\Email}{your.email@example.com}
\newcommand{\ProblemNumber}{II OM, etap 1, zadanie 1}

\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\Name \\ \Email}
\fancyhead[C]{\ProblemNumber}
\fancyfoot[C]{\thepage/\pageref{LastPage}}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\begin{document}

\fontsize{15}{18}\selectfont

\section*{Problem Statement}

Dowieść, że iloczyn dwóch czynników, z których każdy jest sumą kwadratów dwóch liczb całkowitych, jest również sumą kwadratów dwóch liczb całkowitych.

\bigskip

\noindent\textbf{Solution:}

\textbf{Sposób 1: (algebraiczny)}

Czyli mamy dowieść, że:
\begin{equation}
    \label{e1}
    (a^2 + b^2)(c^2 + d^2)
\end{equation}

jest sumą kwadratów dwóch liczb całkowitych. Przy czym $a,b,c,d \in \mathbb{Z}$.

Spróbujmy rozpisać:
\begin{align*}
    (a^2 + b^2)(c^2 + d^2) &= a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2 \\
    &= a^2c^2 + b^2d^2 + a^2d^2 + b^2c^2 \\
    &= (a^2c^2 + 2abcd + b^2d^2) + (a^2d^2 - 2abcd + b^2c^2) \\
    &= (ac + bd)^2 + (ad - bc)^2
\end{align*}

Zauważmy, że zarówno $ac + bd$ jak i $ad - bc$ są liczbami całkowitymi!

Zatem przedstawiliśmy \eqref{e1} jako sumę dwóch kwadratów liczb całkowitych. 
Co należało dowieść. \qed

\textbf{Sposób 2: (indukcja)}

Sformułujmy następujące twierdzenie:
\begin{theorem}
    \label{t1}
    Iloczyn $n$ czynników, z których każdy jest sumą kwadratów dwóch liczb całkowitych,
    jest również sumą kwadratów dwóch liczb całkowitych.

    Innymi słowy: jeśli liczby $a_1, b_1, a_2, b_2, \ldots , a_n, b_n \in \mathbb{Z}$, to iloczyn:
    \[
    1\cdot(a_1^2 + b_1^2)(a_2^2 + b_2^2)\cdot\ldots\cdot(a_n^2 + b_n^2)
    \]
    równa się sumie kwadratów dwóch liczb całkowitych. 
    (jedynka z przodu została dodana jedynie dla wygody dowodu)
\end{theorem}

Zauważmy, że teza z zadania jest tym twierdzeniem dla $n = 2$.
Zatem, jeśli udowodnimy to twierdzenie to również zrobimy zadanie!

By udowodnić powyższe twierdzenie użyjmy \textbf{indukcji zupełnej}

Krok pierwszy: sprawdźmy czy dla $n = 1$ twierdzonko działa:
\[
    1\cdot(a_1^2 + b_1^2) = a_1^2 + b_1^2
\]
jak widać, oczywiście działa.

Krok drugi: załóżmy, że dla pewnego $n = k$ nasze twierdzenie jest prawdzine,
czyli zachodzi takie coś:
\begin{equation}
    1\cdot(a_1^2 + b_1^2)(a_2^2 + b_2^2)\cdot\ldots\cdot(a_k^2 + b_k^2) = A^2 + B^2
\end{equation}
gdzie $A,B \in \mathbb{Z}$.

Krok trzeci: udowodnijmy, że przy tym założeniu nasze twierdzenie jest dobre również dla $n = k + 1$.

Rozpiszmy:
\[
    1\cdot(a_1^2 + b_1^2)(a_2^2 + b_2^2)\cdot\ldots\cdot(a_k^2 + b_k^2)(a_{k+1}^2 + b_{k+1}^2) =
\]
\begin{align*}
    &= (A^2 + B^2)(a_{k+1}^2 + b_{k+1}^2) \\
    &= A^2a_{k+1}^2 + A^2b_{k+1}^2 + B^2a_{k+1}^2 + B^2b_{k+1}^2 \\
    &= A^2a_{k+1}^2 + B^2b_{k+1}^2 + A^2b_{k+1}^2 + B^2a_{k+1}^2 \\
    &= (A^2a_{k+1}^2 + 2Aa_{k+1}Bb_{k+1} + B^2b_{k+1}^2) + (A^2b_{k+1}^2 - 2Aa_{k+1}Bb_{k+1} + B^2a_{k+1}^2) \\
    &= (Aa_{k+1} + Bb_{k+1})^2 + (Ab_{k+1} - Ba_{k+1})^2
\end{align*}

Jak widać udało się dowieść, że dla $n = k + 1$ twierdzenie również jest prawdziwe.

Krok czwarty: na mocy zasady indukcji matematycznej twierdzenie \ref{t1} jest prawdziwe.

Podstawiamy $n = 2$ do twierdzenia \ref{t1} i mamy tezę. Co należało dowieść. \qed

\textbf{Sposób 3: (liczby zespolone)}

Tożsamość tę można wyprowadzić z własności modułu liczb zespolonych.
Niech $z_1 = a + bi$ oraz $z_2 = c + di$, gdzie $a,b,c,d \in \mathbb{Z}$.

Wiemy, że kwadrat modułu liczby zespolonej $z = x + yi$ wyraża się wzorem:
\[ |z|^2 = x^2 + y^2 \]

Skorzystajmy z własności mnożenia modułów:
\[ |z_1|^2 \cdot |z_2|^2 = |z_1 \cdot z_2|^2 \]

Lewa strona równania to dokładnie nasz iloczyn sum kwadratów:
\[ |z_1|^2 \cdot |z_2|^2 = (a^2 + b^2)(c^2 + d^2) \]

Obliczmy teraz prawą stronę, czyli iloczyn samych liczb zespolonych $z_1 \cdot z_2$:
\begin{align*}
    z_1 \cdot z_2 &= (a + bi)(c + di) \\
    &= ac + adi + bci + bdi^2 \\
    &= (ac - bd) + (ad + bc)i
\end{align*}
(pamiętając, że $i^2 = -1$).

Zatem kwadrat modułu tego iloczynu to suma kwadratów jego części rzeczywistej i urojonej:
\[ |z_1 \cdot z_2|^2 = (ac - bd)^2 + (ad + bc)^2 \]

Ostatecznie otrzymujemy:
\[ (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2 \]

Ponieważ $a,b,c,d$ są całkowite, to liczby $(ac-bd)$ oraz $(ad+bc)$ również są całkowite.
Tym samym wykazaliśmy, że iloczyn jest sumą kwadratów dwóch liczb całkowitych. \qed

\textit{Uwaga: Gdybyśmy zamiast $z_1 \cdot z_2$ policzyli $z_1 \cdot \overline{z_2}$ (mnożenie przez sprzężenie), otrzymalibyśmy drugi możliwy wynik: $(ac+bd)^2 + (ad-bc)^2$, który uzyskaliśmy w Sposobie 1.}

\textbf{Sposób 4: (macierze i wyznaczniki)}

Skorzystamy z własności wyznaczników macierzy kwadratowych, która mówi, że wyznacznik iloczynu macierzy jest równy iloczynowi ich wyznaczników:
\[ \det(A) \cdot \det(B) = \det(AB) \]

Przyporządkujmy parze liczb $(x, y)$ macierz postaci:
\[ M(x, y) = \begin{pmatrix} x & y \\ -y & x \end{pmatrix} \]
Zauważmy, że jej wyznacznik to dokładnie suma kwadratów:
\[ \det(M(x, y)) = x \cdot x - y \cdot (-y) = x^2 + y^2 \]

Niech teraz macierz $A$ odpowiada parze $(a, b)$, a macierz $B$ parze $(c, d)$:
\[ A = \begin{pmatrix} a & b \\ -b & a \end{pmatrix}, \quad B = \begin{pmatrix} c & d \\ -d & c \end{pmatrix} \]

Mamy więc:
\[ \det(A) = a^2 + b^2, \quad \det(B) = c^2 + d^2 \]

Obliczmy iloczyn tych macierzy $C = A \cdot B$:
\begin{align*}
    C &= \begin{pmatrix} a & b \\ -b & a \end{pmatrix} \begin{pmatrix} c & d \\ -d & c \end{pmatrix} \\
    &= \begin{pmatrix} a\cdot c + b\cdot(-d) & a\cdot d + b\cdot c \\ (-b)\cdot c + a\cdot(-d) & (-b)\cdot d + a\cdot c \end{pmatrix} \\
    &= \begin{pmatrix} ac - bd & ad + bc \\ -(ad + bc) & ac - bd \end{pmatrix}
\end{align*}

Otrzymana macierz $C$ ma tę samą strukturę, co macierze wyjściowe:
\[ C = M(ac - bd, \quad ad + bc) \]

Z własności wyznaczników wiemy, że $\det(A)\det(B) = \det(C)$. Podstawmy wartości:
\[ (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2 \]

Ponieważ $a,b,c,d$ są całkowite, to elementy nowej macierzy również są całkowite.
Teza została udowodniona. \qed

\end{document}