II OM - I - Zadanie 1

Zawody matematyczne:

II OM, 1950-1951

Etap:

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.

Rozwiązanie

Zastosujemy przekształcenie

$ \begin{split} (a^2 + b^2) (c^2 + d^2) &= a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2 = \\ &=(a^2c^2 + 2abcd + b^2d^2) + (a^2d^2 - 2abcd + b^2c^2) =\\ &= (ac + bd)^2 + (ad - bc)^2. \end{split} $

Jeśli $a$ , $b$ , $c$ , $d$ są liczbami całkowitymi, to $ac + bd$ i $ad - bc$ są też liczbami całkowitymi; twierdzenie zostało więc udowodnione.

Zauważmy, że zachodzi twierdzenie ogólniejsze:

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.

Twierdzenie to udowodnimy stosując zasadę indukcji zupełnej. Przypomnimy krótko, jak można sformułować tę zasadę:

Niech $T_n$ oznacza twierdzenie wypowiadające jakąś własność liczby naturalnej $n$ i niech będzie przy tym wiadomo, że:

1° Twierdzenie $T_1$ jest prawdziwe, tzn. liczba $1$ ma tę własność.

2° Jeśli dla którejś liczby $k$ twierdzenie $T_k$ jest prawdziwe, to prawdziwe jest również twierdzenie $T_{k+1}$ , tzn. jeśli któraś liczba naturalna $k$ ma ową własność, to ma ją również następna liczba naturalna $k + 1$ .

Wówczas twierdzenie $T_n$ jest prawdziwe dla każdej liczby naturalnej $n$ , tzn. każda liczba naturalna ma ową własność. (Na tym wniosku polega właśnie zasada indukcji).

Przystępując do dowodu zapowiedzianego wyżej twierdzenia nadamy mu nieco dogodniejsze brzmienie:

Twierdzenie ( $T_n$ ). Jeśli liczby $a_1, b_1, a_2, b_2, \ldots, a_n, b_n$ są całkowite, to iloczyn

$ 1 \cdot (a_1^2 + b_1^2 ) \cdot (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.

(Napisaliśmy na początku jedynkę w tym celu, by powyższe wyrażenie również w przypadku $n = 1$ miało postać iloczynu).

Dowód polegać będzie na stwierdzeniu, że spełnione są warunki 1°-2°, występujące w zasadzie indukcji. Otóż:

1° Twierdzenie $T_1$ jest prawdziwe, gdyż

$ 1 \cdot (a^2 + b^2) = a^2 + b^2. $

2° Przypuśćmy, że dla pewnego $k$ twierdzenie $T_k$ jest prawdziwe, tzn. że

$ 1 \cdot (a_1^2 + b_1^2 ) \cdot (a_2^2 + b_2^2 ) \cdot \ldots \cdot (a_k^2 + b_k^2 ) = A^2 + B^2, $

gdzie $A$ i $B$ są liczbami całkowitymi. Udowodnimy, że przy tym założeniu prawdziwe jest też twierdzenie $T_{k+1}$ .

Istotnie

$ \begin{split} 1 \cdot (a_1^2 + b_1^2 ) \cdot (a_2^2 +& b_2^2 ) \cdot \ldots \cdot (a_k^2 + b_k^2 ) \cdot (a_{k+1}^2 + b_{k+1}^2 ) = (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^2 b_{k+1}^2 =\\ &=(Aa_{k+1} + Bb_{k+1})^2 + (Ab_{k+1} - Ba_{k+1})^2. \end{split} $

Na podstawie zasady indukcji wnosimy z przesłanek 1° i 2°, że twierdzenie $T_n$ jest prawdziwe dla każdego naturalnego $n$ .

Uwaga. Można udowodnić, że zasada indukcji zupełnej jest równoważna następującemu twierdzeniu:

W każdym zbiorze liczb naturalnych (zawierającym przynajmniej jedną liczbę) istnieje liczba najmniejsza. Zastrzeżenie, że rozważany zbiór liczb naturalnych zawiera przynajmniej jedną liczbę, jest potrzebne dlatego, że w matematyce do zbiorów liczb lub innych przedmiotów (zwanych elementami zbioru) zalicza się także tzw. zbiór pusty, tj. zbiór nie zawierający żadnego elementu. Jest to bardzo dogodne w niektórych rozumowaniach.

Przeprowadzimy dowód poprzedniego twierdzenia $T_n$ oparty na twierdzeniu powyższym.

Przypuśćmy, że istnieją takie liczby naturalne, dla których twierdzenie $T_n$ nie jest prawdziwe. W zbiorze tych liczb istnieje liczba najmniejsza $k$ . Istnieją więc takie liczby całkowite $a_1, b_1, a_2, b_2, \ldots, a_k, b_k$ , że iloczyn

$ (1) \qquad 1 \cdot (a_1^2 + b_1^2) \cdot (a_2^2 + b_2^2) \cdot \ldots \cdot (a_k^2 + b_k^2) $

nie równa się sumie kwadratów dwóch liczb całkowitych, a jednocześnie

$ 1 \cdot (a_1^2 + b_1^2) \cdot (a_2^2 + b_2^2) \cdot \ldots \cdot (a_{k-1}^2 + b_{k-1}^2) = A^2 + B^2, $

gdzie $A$ i $B$ są liczbami całkowitymi. Ale wtedy możemy napisać:

$ \begin{split} 1 \cdot (a_1^2 & + b_1^2) \cdot (a_2^2 + b_2^2) \cdot \ldots \cdot (a_{k-1}^2 + b_{k-1}^2)(a_{k}^2 + b_{k}^2) = (A^2 + B^2)(a_{k}^2 + b_{k}^2) = \\ & = A^2a_k^2 + B^2a_k^2 + A^2b_k^2 + B^2b_k^2 = (Aa_k + Bb_k)^2 + (Ab_k - Ba_k)^2 \end{split} $

Według tej równości iloczyn (1) równa się sumie kwadratów dwóch liczb całkowitych, co jest sprzeczne z wnioskiem poprzednim. Przypuszczenie, że istnieją takie wartości $n$ , dla których twierdzenie $T_n$ jest fałszywe - doprowadziło do sprzeczności; zatem twierdzenie $T_n$ jest prawdziwe dla każdego naturalnego $n$ .