Zad. 1. Czy dla każdej dodatniej liczby naturalnej n istnieje wyraz ciągu Fibonacciego przez nią podzielny? Uzasadnij odpowiedź.
Zad. 2. Czy dwie kolejne potęgi dwójki mogą mieć równą sumę cyfr? Uzasadnij odpowiedź.
Zad. 3. Rozwiąż w liczbach całkowitych równanie 2xy+ 3x+y = -1.
W tym miesiącu 6 pkt. otrzymał Rafał Frankowski (SP 139 Warszawa).
Zad. 1. W poniższym rozwiązaniu wszystkie zmienne przyjmują wartości naturalne, a x≡y oznacza, że x i y mają taką samą resztę z dzielenia przez n.
Zauważmy, że ciąg reszt z dzielenia kolejnych wyrazów ciągu Fibonacciego przez n jest okresowy. Istotnie, par liczb naturalnych mniejszych od n jest skończenie wiele, zatem dla pewnych k i l musi zachodzić F(k) ≡ F(k+l) oraz F(k+1) ≡ F(k+l+1). Liczba l jest okresem tego ciągu. Co ważne, okres ten działa wstecz, tzn. jeśli dla pewnego a zachodzi F(a) ≡ F(a+l) i F(a+1) ≡ F(a+l+1), to także F(a–1) = F(a+1)–F(a) ≡ F(a+l+1)–F(a+l) = F(a–1+l). Stąd wynika, że ciąg reszt jest okresowy od początku, a nie tylko od pewnego miejsca. Przypomnijmy, że F(0) ≡ F(1) ≡ 1, czyli F(l) ≡ F(l+1) ≡ 1. To oznacza, że F(l–1) ≡ 0, innymi słowy jest podzielność tego wyrazu przez n.
Zad. 2. Gdyby dwie kolejne potęgi dwójki miały równą sumę cyfr, to dawałyby (na mocy uogólnionej cechy podzielności przez 9) tę samą resztę z dzielenia przez 9. Gdyby dwie kolejne potęgi dwójki miały taką samą resztę z dzielenia przez 9, ich różnica musiałaby być wielokrotnością dziewiątki. Ale różnica dwóch kolejnych potęg dwójki jest równa mniejszej z nich, więc dostajemy sprzeczność z twierdzeniem o jednoznaczności rozkładu liczby na czynniki pierwsze (żadna potęga dwójki nie dzieli się przez 9).
Zad. 3. Przekształćmy równanie równoważnie:
2xy+3x+y+1,5 = 0,5
2x(y+1,5)+(y+1,5) = 0,5
(2x+1)(y+1,5) = 0,5
(2x+1)(2y+3) = 1
Oba nawiasy muszą mieć wartość całkowitą. Wynika z tego, że albo oba są równe 1, albo -1. Po rozwiązaniu dwóch układów równań otrzymujemy spełniające je pary: (0, -1) i (-1, -2).