XLVII OM - I - Zadanie 6

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Dane są dwa ciągi liczb całkowitych dodatnich: ciąg arytmetyczny o różnicy $r > 0$ i ciąg geometryczny o ilorazie $q > 1$ ; liczby naturalne $r$ , $q$ są względnie pierwsze. Udowodnić, że jeśli te ciągi mają jeden wspólny wyraz, to mają nieskończenie wiele wspólnych wyrazów.

Rozwiązanie

Oznaczmy przez $r_i$ resztę z dzielenia liczby $q^i$ przez $r\ (i = 1,2,3,\ldots)$ . W nieskończonym ciągu $(r_1,r_2,r_3,\ldots)$ , którego wyrazy przybierają tylko skończenie wiele wartości, muszą wystąpić powtórzenia. Istnieją zatem różne numery $i$ , $j$ takie, że $r_i = r_j$ . Różnica $q^i-q^j$ jest wówczas podzielna przez $r$ . Przyjmując, że $i >j$ , możemy tę różnicę zapisać tak:

$<br /> q^i-q^j=q^j(q^{i-j} -1).<br />$

Liczba po prawej stronie ma się dzielić przez $r$ (bo lewa strona dzieli się przez $r$ ). Czynnik $q^j$ jest względnie pierwszy z $r$ (warunek zadania). Zatem czynnik $(q^{i-j}-1)$ musi dzielić się przez $r$ . Istnieje więc liczba całkowita $l$ taka, że $q^{i-j}-1=lr$ . Oznaczając różnicę $i-j$ przez $k$ mamy równość $q^k=1+lr$ .

Niech $(a_1,a_2,\ldots)$ będzie rozważanym ciągiem arytmetycznym, a $(b_1,b_2, \ldots)$ rozważanym ciągiem geometrycznym. Zakładamy, że mają one wspólny wyraz $a_m = b_n$ . Wówczas

$<br /> b_{n + k} =b_nq^k =b_n(1+lr) =a_m(1+lr) =a_m+r \cdot l a_m =a_{m+s},<br />$

gdzie $s=la_m$ . Znaleźliśmy w ten sposób nową parę wspólnych wyrazów rozpatrywanych ciągów (o numerach większych od $m$ i $n$ ). Powtarzając to rozuwanie znajdujemy nieskończenie wiele wspólnych wyrazów.