XXXIII OM - I - Zadanie 8

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Dane są liczby naturalne $l, m, p, q, n$ spełniające warunki: $\frac{l}{m} < \frac{p}{q}$ i $m, q$ są względnie pierwsze. Udowodnić równoważność następujących warunków.
(1) Istnieje taka liczba naturalna $k$ , że

$ \frac{l}{m} < \frac{k}{n} < \frac{p}{q}. $

(2) Istnieją takie liczby naturalne $r, s$ , że ,

$ n=\frac{rm+sq}{pm-lq} $

Rozwiązanie

Załóżmy, że spełniony jest warunek (1). Ponieważ zachodzi nierówność $\frac{l}{m} < \frac{k}{n}$ , to $ln<km$ . Mamy przy pewnym naturalnym $s$ równość $km =ln+s$ . Możemy napisać.

$ \nr{i} \frac{k}{n} = \frac{km}{mn} = \frac{ln+s}{mn} = \frac{ln}{mn}+\frac{s}{mn} = \frac{l}{m}+\frac{s}{mn}. $

Analogicznie z nierówności $\frac{k}{n} < \frac{p}{q}$ wynika, że $kq <pn$ . Istnieje liczba naturalna $r$ , dla której $kq = pn - r$ . Zachodzą więc nierówności

$ \nr{ii} \frac{k}{n} = \frac{kq}{nq} = \frac{pn-r}{nq} = \frac{pn}{nq}-\frac{r}{nq} = \frac{p}{q}-\frac{r}{nq}. $

Z równości (i) i (ii) wynika

$ \frac{ln}{mn}+\frac{s}{mn} = \frac{pn}{nq}-\frac{r}{nq} , $

$ lnq + sq = pnm - rm, $

$ lnq - pnm = -rm - sq, $

$ n(lq - pm) = -rm - sq, $

$ n = \frac{rm+sq}{pm-lq}. $

Wykazaliśmy więc, że spełniony jest warunek (2).

Załóżmy teraz, że istnieją $r$ , $s$ naturalne, dla których

$ n = \frac{rm+sq}{pm-lq}. $

Szukamy liczby naturalnej $k$ , dla której zachodzi następująca równość

$ \frac{k}{n} = \frac{ln}{mn} + \frac{s}{mn} $

(z powyższych rachunków wynika, że wtedy będzie również $\frac{k}{n} = \frac{pn}{qn} - \frac{r}{qn}$ ).

Dla liczby $k$ musi zachodzić równość

$ k = \frac{ln}{m} + \frac{s}{m}. $

Stąd otrzymujemy

$ k = \frac{\frac{rm+sq}{pm-lq}l+s}{m}, $

$ k = \frac{rml+sql+spm-slq}{m(pm-lq)}, $

$ k = \frac{rl+sp}{pm-lq}. $

Wystarczy wykazać, że liczba $k$ określona tym wzorem jest liczbą całkowitą.

Ponieważ $n = \frac{rm+sq}{pm-lq}$ jest liczbą całkowitą, więc

$ pm - lq \mid rm + sq. $

Wobec tego, jeśli $t$ jest liczbą pierwszą i

$ t^a \mid pm - lq,\ \textrm{to} \ t^a \mid rm + sq. $

Mamy dla odpowiednich $a$ , $b$ równości

$ (*) \qquad pm - lq = at^a,\ rm + sq = bt^a. $

Otrzymamy następujące wyrażenia odejmując od pierwszego z równań (*) pomnożonego przez $r$ drugie pomnożone przez $p$ :

$ rpm - rlg - prm - psq = rat^a - pbt^a, $

$ -rlq - psq = rat^a - pbt^a, $

$ (sp + rl)q = (pb - ra)t^a. $

Stąd wynika, że $t^a \mid (sp + rl)q$ .

Gdyby było $t \mid q$ , to z równań (*) wynikałoby, że $t \mid m$ . Prowadzi to do sprzeczności z założeniem, że liczby $q$ , $m$ są względnie pierwsze. Wobec tego $t^a\mid sp + rl$ . Zatem istotnie każdy dzielnik pierwszy mianownika ułamka $\displaystyle \frac{rl+sp}{pm-lq}$ dzieli licznik tego ułamka w co najmniej takiej potędze, w jakiej dzieli mianownik. Wynika stąd, że $\displaystyle k =\frac{rl+sp}{pm-lq}$ jest liczbą całkowitą.