LIX OM - III -Zadanie 6

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

III

Niech $S$ będzie zbiorem wszystkich dodatnich liczb całkowitych, które można przedstawić w postaci $a^2 +5b^2$
dla pewnych względnie pierwszych liczb całkowitych $a$ i $b$ . Niech ponadto $p$ będzie liczbą pierwszą dającą resztę
3 z dzielenia przez 4. Wykazać, że jeżeli pewna dodatnia wielokrotność liczby $p$ należy do zbioru $S$ , to również liczba
$2p$ należy do zbioru $S$ .

Rozwiązanie

Na mocy warunków zadania liczba $a^2 +5b^2$ jest podzielna przez $p$ dla pewnych względnie pierwszych liczb całkowitych $a$ i $b$ .

Liczba $b$ nie jest podzielna przez $p$ ; w przeciwnym przypadku z podzielności $p|b$ oraz $p|a^2 +5b^2$ uzyskalibyśmy bowiem
$p|a$ , wbrew względnej pierwszości liczb $a$ i $b$ .

Zatem żadna z $p - 1$ liczb: $b,2b, \dots ,(p - 1)b$ nie jest podzielna przez $p$ . Ponadto liczby te dają różne reszty
z dzielenia przez $p$ . Istotnie, jeżeli mamy $p| ib-jb=(i-j)b$ dla pewnych wskaźników $1\leqslant i,j \leqslant p-1$ , to liczba
pierwsza $p$ jest dzielnikiem różnicy $i - j$ , skąd wynika, że $i = j$ . W konsekwencji jedna z rozpatrywanych liczb daje
resztę 1 z dzielenia przez $p$ . Przyjmijmy, że jest to liczba $kb$ (dla pewnej wartości $k \in\{1,2,\dots ,p- 1\}$ ). Wówczas
mamy

$ p| k^2(a^2 +5b^2)=(ak)^2 +5(bk)^2,\quad \text{czyli} \quad p| m^2 +5, \quad \text{gdzie} m = ak. $

Niech $z$ oznacza największą liczbę całkowitą nie przekraczającą $p$ . Rozpatrzmy zbiór reszt z dzielenia liczb
$0, m,2m, \dots , zm$ przez $p$ . Uporządkujmy te $z +1$ reszt w kolejności niemalejącej otrzymując ciąg
$r_1 \leqslant r_2 \leqslant \dots \leqslant r_z+1$ . Wtedy każda z $z +1$ liczb:

$ r_2 - r_1, \; r_3 - r_2,\; \dots , r_{z+1} - r_z,\; p- (r_{z+1} - r_1) $

jest nieujemna, a ich suma wynosi $p$ . Wynika stąd, że przynajmniej jedna z tych liczb jest nie większa niż

$ \frac{p}{z+1}=\frac{(z+(p-z))^2}{z+1}< \frac{(z+1)^2}{z+1} = z+1 $

Zatem wśród liczb $r_2 -r_1, r3 -r2, \dots , r_{z+1} -r_z , p-(r_{z+1} -r_1)$ można wskazać liczbę nie przekraczającą
$z$ . To zaś oznacza, że pewne dwie różne liczby, powiedzmy $cm$ i $dm$ ( $0 \leqslant c,d \leqslant z$ ), dają przy dzieleniu
przez $p$ reszty różniące się nie więcej niż o $z$ , albo różniące się przynajmniej o $p - z$ . Przyjmijmy $y = |c - d|$ ;
wówczas jedna z liczb $ym, -ym$ daje resztę $x \leqslant z$ z dzielenia przez $p$ . Ponieważ $p | m^2 +5$ , więc liczby

$ x^2 +5y^2 \text{ i } x^2 - m^2y^2 =(x - my)(x +my) $

dają taką samą resztę z dzielenia przez $p$ . Jeden z czynników $x - my, x+my$ jest jednak podzielny przez $p$ .
W efekcie $p | x^2 +5y^2$ . Ponadto $0 \leqslant x \leqslant z$ oraz $0 \leqslant y \leqslant z$ , co w połączeniu
z nierównością $z< p$ daje

$ x^2 +5y^2 \leqslant 6z^2 < 6( \sqrt{p})2 =6p. $

Stąd wniosek, że $x^2 +5y^2$ jest jedną z liczb $p,2p,3p,4p$ lub $5p$ .

Równość $x^2 +5y^2= p$ oznaczałaby, że liczba $x^2 +5y^2$ daje resztę 3 z dzielenia przez 4. To jednak nie jest możliwe,
gdyż liczby $x$ i $5y^2$ dają reszty 0 lub 1 z dzielenia przez 4. Zatem $x^2 +5y^2 = p$ . To dowodzi także, że nie mogą mieć
miejsca równości $x^2 +5y^2=4p$ ani $x^2 +5y^2=5p$ . Pierwsza z tych równości oznaczałaby bowiem, że liczby
$x$ i $y$ są parzyste (w żadnym innym przypadku liczba $x^2 +5y^2$ nie jest podzielna przez 4) oraz
$(\frac{1}{2}x)^2 +5(\frac{1}{2}y)^2 = p$ ; druga równość prowadzi natomiast do wniosku, że $5|x$ oraz
$y^2 +5(\frac{1}{2}x)^2 = p$ . W obu przypadkach dochodzimy do sprzeczności z udowodnionym wcześniej faktem, że liczba postaci
$^2 +5f^2$ jest różna od $p$ dla dowolnych całkowitych wartości $e$ i $f$ .

Stwierdziliśmy w ten sposób, że $x^2 +5y^2=2p$ lub $x^2 +5y^2=3p$ .

Przypuśćmy, że $x^2 +5y^2 =3p$ . Wówczas liczby $x$ i $y$ nie są podzielne przez 3 (w przeciwnym razie mielibyśmy
$3|x$ oraz $3|y$ , jednakże wówczas $3^2| x^2 +5y^2=3p$ ; co może się zdarzyć jedynie w przypadku $p = 3$ , ale wtedy
uzyskujemy następującą sprzeczność: $9=3p =x^2 +5y^2 \geqslant 3^2 +5\cdot 3^2 =54$ ). Zmieniając ewentualnie znaki
liczb $x$ i $y$ możemy przyjąć, że $x$ i $y$ są liczbami całkowitymi dającymi resztę 1 z dzielenia przez 3. Ponadto

$ 18p =6\cdot 3p = 6(x^2 +5y^2 )=(x +5y)^2 +5(x - y)^2. $

Liczby $x+5y$ i $x-y$ są podzielne przez 3; jeżeli więc $x+5y =3g$ oraz $x-y =3h$ , to z powyższej równości wnioskujemy,
że $2p = g^2 +5h^2$ .

Ostatecznie udowodniliśmy, że liczba $2p$ daje się przedstawić w postaci $s^2 +5t^2$ dla pewnych liczb całkowitych
$s$ i $t$ . Pozostaje zauważyć, że w takiej sytuacji liczby $s$ i $t$ są względnie pierwsze; gdyby bowiem miały one
wspólny dzielnik pierwszy $q$ , to uzyskalibyśmy $q^2 | s^2 +5t^2 =2p$ , co prowadzi do sprzeczności, gdyż
$p$ jest nieparzystą liczbą pierwszą. Zatem dowód relacji $2p \in S$ jest zakończony.