XLV OM - II - Zadanie 6

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Dana jest liczba pierwsza p. Wykazać równoważność zdań:

(a) Istnieje taka liczba całkowita $n$ , że liczba $n^2 - n + 3$ jest podzielna przez $p$ .

(b) Istnieje taka liczba całkowita $m$ , że liczba $m^2 - m +25$ jest podzielna przez $p$ .

Rozwiązanie

Żądana równoważność wynika nietrudno ze spostrzeżenia, że

$ (1) \qquad \textrm{jeśli } m = 3n-1, \textrm{ to } m^2-m + 25 = 9(n^2-n + 3). $

Implikację (a) $\Longrightarrow$ (b) dostajemy stąd natychmiast: jeżeli (dla pewnego $n$ ) liczba $n^2 -n + 3$ dzieli się przez $p$ , to wystarczy przyjąć $m = 3n-1$ : zgodnie z (1), liczba $m^2 -m + 25$ także dzieli się przez $p$ .

Dowód implikacji (b) $\Longrightarrow$ (a) poprowadzimy najpierw przy założeniu, że $p\neq 3$ . Zakładamy słuszność (b): niech $m$ będzie liczbą całkowitą, dla której liczba $m^2-m + 25$ dzieli się przez $p$ . Skoro $p \neq 3$ , zatem liczby $m$ , $m + p$ , $m-p$ dają przy dzieleniu przez $3$ różne reszty, a więc jedna z tych trzech liczb daje resztę $2$ . Oznaczmy tę liczbę przez $k$ ; to znaczy, przyjmijmy

$ k=\left\{\begin{array}{lrll} m&\textrm{jeśli}& m\equiv 2 & \pmod 3,\\ m+p&\textrm{jeśli}& m\equiv 0, p\equiv 2 &\\ &\textrm{lub}& m\equiv 1, p \equiv 1 & \pmod 3,\\ m-p&\textrm{jeśli}& m\equiv 0, p\equiv 1 \\ &\textrm{lub}& m\equiv 1, p \equiv 2 & \pmod 3; \end{array}\right. $

w każdym przypadku, tak zdefiniowana liczba $k$ istotnie spełnia warunek $k \equiv 2 \pmod 3$ . Określamy liczbę całkowitą $n$ wzorem

$ (2) \qquad n=\frac{k+1}{3}. $

Ponieważ $k - m \in \{0,p,-p\}$ oraz (z założenia) $p$ jest dzielnikiem liczby $m^2-m +25$ , zatem $p$ jest też dzielnikiem liczby $k^2 -k + 25$ . Liczby $k$ i $n$ są związane równością $k = 3n-1$ . Wobec tego, na mocy spostrzeżenia (1) (z $m$ zastąpionym przez $k$ ), liczba $p$ jest dzielnikiem iloczynu $9(n^2-n + 3)$ , i to dzielnikiem pierwszym, różnym od $3$ ; jest więc dzielnikiem czynnika $(n^2 - n + 3)$ . To znaczy, że liczba $n$ , określona wzorem (2), spełnia warunek (a).

Pozostaje do udowodnienia implikacja (b) $\Longrightarrow$ (a) w przypadku, gdy $p = 3$ . Otóż dla $p = 3$ oba zdania, (a) i (b), są prawdziwe. Istotnie: wystarczy przyjąć $n = 3$ (w warunku (a)) oraz $m = 2$ (w warunku (b)). Obie rozważane w tych zdaniach liczby ( $n^2-n + 3$ oraz $m^2 -m + 25$ , czyli $9$ oraz $27$ ) są wówczas podzielne przez $3$ , a tym samym oba warunki, (a) i (b), są spełnione.