XLVIII OM - I - Zadanie 4

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

Udowodnić, że liczba naturalna $n \geq 2$ jest złożona wtedy i tylko wtedy, gdy istnieją liczby naturalne $a,b,x,y \geq 1$ spełniające warunki: $a+b=n$ , $\frac{x}{a}+\frac{y}{b}=1$ .

Rozwiązanie

Niech $n$ będzie liczbą złożoną: $n = qr$ , $q \geq 2$ , $r \geq 2$ . Przyjmijmy:

$ a = r, \qquad b=(q-1)r, \qquad x = 1, \qquad y = (q-1)(r-1); $

są to dodatnie liczby całkowite o własnościach:

$ \qquad (1) a + b = n, \qquad \frac{x}{a}+\frac{y}{b}=1. $

Wykazaliśmy więc, że jeżeli $n\geq 2$ jest liczbą złożoną, to istnieją liczby całkowite $a,b,x,y\geq 1$ spełniające warunki (1).

Pozostała do dowodu implikacja przeciwna. Załóżmy, że dla pewnej liczby całkowitej $n \geq 2$ istnieje czwórka liczb całkowitych $a,b,x,y\geq 1$ spełniających równania (1). Z drugiego z tych równań wynika, że $x < a$ , $y<b$ oraz

$ \qquad (2) ay = b(a-x). $

Oznaczmy przez $d$ największy wspólny dzielnik liczb $a$ i $b$ oraz przyjmijmy: $a = \alpha d$ , $b = \beta d$ . Liczby $\alpha$ i $\beta$ są względnie pierwsze. Pierwsze równanie (1) daje zależność: $n = (\alpha + \beta )d$ . Czynnik $\alpha + \beta$ jest większy od $1$ . Aby uzyskać wymaganą konkluzję, że $n$ jest liczbą złożoną, wystarczy wobec tego wykazać, że $d > 1$ .

Równanie (2) po podzieleniu przez $d$ przybiera postać $\alpha y = \beta (a-x)$ . Zatem liczba $\beta$ , jako względnie pierwsza z $\alpha$ , musi być dzielnikiem liczby $y$ . Stąd $\beta \leq y$ . Skoro zaś $y<b$ , dostajemy nierówność $\beta<b$ , iw konsekwencji $d = b/\beta>1$ .

Wniosek: Z istnienia liczb $a,b,x,y\geq 1$ spełniających warunki (1) wynika, że $n$ jest liczbą złożoną. W połączeniu z udowodnioną wcześniej implikacją przeciwną daje to tezę zadania.