[Teoria liczb] Suma potęg

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 7088
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2625 razy
Pomógł: 687 razy

[Teoria liczb] Suma potęg

Post autor: mol_ksiazkowy » 2 wrz 2007, o 04:34

Tym razem niech \(\displaystyle{ x_1, x_2}\) będą pierwiastkami (możliwe że zespolonymi) równania kwadratowego (R) gdzie p i q są to liczby całkowite. Wykaż, że jeśli k>2 jest naturalna, i dzieli ona \(\displaystyle{ p+1}\) jak i \(\displaystyle{ q-1}\), to wtedy przy n=1,2,..., \(\displaystyle{ S_n}\) jest niepodzielna przez k, i dalej wyznacz wzór rekurencyjny na ten ciąg:
\(\displaystyle{ S_n=x_1^n +x_2^n Z}\)
\(\displaystyle{ (R)}\): \(\displaystyle{ x^2=-px-q}\)

[ Dodano: 28 Września 2008, 18:14 ]
dalej wyznacz wzór rekurencyjny na ten ciąg
Tu akurat łatwo:
\(\displaystyle{ x_1^{n+2}+ px_1^{n+1} +qx_1^n =x_1^n (x_1^{2}+ px_1 +q)=0}\)
\(\displaystyle{ x_2^{n+2}+ px_2^{n+1} +qx_2^n =x_2^n (x_2^{2}+ px_2 +q)=0}\)
no i po dodaniu stronami
\(\displaystyle{ S_{n+2}+ pS_{n+1}+qS_n =0}\)
oraz
\(\displaystyle{ S_{1}=-p}\)
\(\displaystyle{ S_{2}=p^2-2q}\)
Ostatnio zmieniony 15 wrz 2008, o 21:16 przez mol_ksiazkowy, łącznie zmieniany 2 razy.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

[Teoria liczb] Suma potęg

Post autor: Sylwek » 1 paź 2008, o 00:12

Z danych zadania:\(\displaystyle{ p+1=sk, q-1 =lk}\), inaczej: \(\displaystyle{ p \equiv -1 (mod \ k) \ \wedge \ q \equiv 1 (mod \ k)}\).

Czyli:
\(\displaystyle{ S_1 = -p \equiv -(-1) \equiv 1 \ (mod \ p) \\ S_2 = p^2 - 2q \equiv (-1)^2-2 \cdot 1 \equiv -1 \ (mod \ k) \\ S_3=-pS_2-qS_1 \equiv -(-1) \cdot (-1) - 1 \cdot 1 \equiv -2 \ (mod \ k)}\)

Ogólnie dla n>0: \(\displaystyle{ S_{n+2} =-pS_{n+1}-qS_{n} \equiv S_{n+1}-S_{n} \ (mod k)}\).

Zatem dalej:
\(\displaystyle{ S_{4} \equiv S_3 - S_2 = -2 + 1 = -1 \ (mod \ k) \\
S_5 \equiv S_4 - S_3 = -1 + 2 = 1 \ (mod \ k) \\
S_6 \equiv S_5 - S_4 = 1 + 1 = 2 \ (mod \ k) \\
S_7 \equiv S_6 - S_5 = 2 - 1 = 1 \ (mod \ k) \\
S_8 \equiv S_7 - S_6 = 1-2=-1 \ (mod \ k)}\)


I prosto zauważyć (uściślić można indukcją bądź ogólniejszymi kongruencjami), że \(\displaystyle{ S_{n+6} \equiv S_n \ (mod \ k)}\), a ponieważ \(\displaystyle{ S_1,S_2,S_3,S_4,S_5,S_6}\) nie były podzielne przez k (bo przystawały modulo k liczbom, których wartość bezwzględna jest mniejsza niż k), toteż dla żadnego i \(\displaystyle{ S_i}\) nie jest podzielna przez k.

ODPOWIEDZ