Ukryta treść:
Podzielność w ciągu
- mol_ksiazkowy
- Użytkownik
- Posty: 11372
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Podzielność w ciągu
Dany jest ciąg \(\displaystyle{ a_0=4 ; a_{n+1} =a_n^2 - 2}\). Udowodnić, że jeśli liczba pierwsza \(\displaystyle{ p>2}\) dzieli \(\displaystyle{ a_n}\), to \(\displaystyle{ 2^{n+2} }\) dzieli \(\displaystyle{ p^2-1.}\)
Ostatnio zmieniony 13 sty 2023, o 20:52 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Interpunkcja.
Powód: Interpunkcja.
- arek1357
- Użytkownik
- Posty: 5745
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Podzielność w ciągu
\(\displaystyle{ a_{n+2}=4a_{n+1}-a_{n} , a_{0}=2, a_{1}=4}\)
Taki mniej więcej warunek spełniają wyrazy ciągu, możliwe nawet, że podciągu po rozpisaniu tak mi wyszło kilku pierwszych wyrazów
Dodano po 42 sekundach:
I teraz nietrudno poszukać wzoru jawnego:
Dodano po 22 godzinach 11 minutach 13 sekundach:
Który jak wyliczę z szeregów wyjdzie taki:
\(\displaystyle{ a_{n}=\left( 2+ \sqrt{3} \right)^n+ \left( 2- \sqrt{3} \right)^n}\)
funkcja tworząca to:
\(\displaystyle{ f(x)= \frac{2-4x}{x^2-4x+1} }\)
I teraz co ciekawe ciąg, który wygenerowałem to nie do końca ciag zadany zadaniem bo mamy takie wyrazy:
2,4,14,52,194,724,2702,10084,37634,...
Kolorem czerwonym zaznaczyłem te wyrazy który generuje ciąg z zadania czyli:
\(\displaystyle{ a_{n+1}=a_{n}^2-2}\)
Co ciekawe one stoją na miejscach:
\(\displaystyle{ 1,2,4,8,16,...,2^n,...}\)
Czyli kolejne potęgi dwójki...
Jest to ciekawe spostrzeżenie i uważam najciekawsza część zadania, gdzie ciąg zadany kwadratową rekurencją a więc niejednorodną i nie klasyczną
daje się "ucywilizować" do postaci jawnej bo teraz widać, że nasz ciąg ma wzór:
\(\displaystyle{ a_{n}=\left( 2+ \sqrt{3} \right)^{2^n}+ \left( 2- \sqrt{3} \right)^{2^n}, n=0,1,2,3,...}\)
Dalej to prawdopodobnie mamy zabawę w ciele:
\(\displaystyle{ \ZZ_{p^2}}\)
gdzie trójka jest lub nie jest resztą kwadratową...
Dodano po 10 godzinach 48 minutach 17 sekundach:
To się pobawmy
Jak wiadomo pewna liczba pierwsza p dzieli wyraz ciągu \(\displaystyle{ a_{n}}\)
Mamy więc:
\(\displaystyle{ 2+ \sqrt{3} = \frac{1}{2- \sqrt{3} } }\)
\(\displaystyle{ \left( 2+ \sqrt{3} \right)^{2^n}+ \left( 2- \sqrt{3} \right)^{2^n}=0 \mod p / \cdot \left( 2+ \sqrt{3} \right)^{2^n} }\)
\(\displaystyle{ \left( 2+ \sqrt{3} \right)^{2^{n+1}}=-1 /^2}\)
Ostatecznie mamy:
\(\displaystyle{ \left( 2+ \sqrt{3} \right)^{2^{n+2}}=1 \mod p}\)
Wynika stąd, że rząd elementu
\(\displaystyle{ 2+ \sqrt{3} }\)
W grupie multiplikatywnej ciała \(\displaystyle{ \ZZ_{p^2}}\) wynosi \(\displaystyle{ 2^{n+2}}\)
Grupa ta ma \(\displaystyle{ p^2-1}\) elementów
Co znaczy, że:
\(\displaystyle{ 2^{n+2}| p^2-1}\)
Przykład na przykład:
Taki mniej więcej warunek spełniają wyrazy ciągu, możliwe nawet, że podciągu po rozpisaniu tak mi wyszło kilku pierwszych wyrazów
Dodano po 42 sekundach:
I teraz nietrudno poszukać wzoru jawnego:
Dodano po 22 godzinach 11 minutach 13 sekundach:
Który jak wyliczę z szeregów wyjdzie taki:
\(\displaystyle{ a_{n}=\left( 2+ \sqrt{3} \right)^n+ \left( 2- \sqrt{3} \right)^n}\)
funkcja tworząca to:
\(\displaystyle{ f(x)= \frac{2-4x}{x^2-4x+1} }\)
I teraz co ciekawe ciąg, który wygenerowałem to nie do końca ciag zadany zadaniem bo mamy takie wyrazy:
2,4,14,52,194,724,2702,10084,37634,...
Kolorem czerwonym zaznaczyłem te wyrazy który generuje ciąg z zadania czyli:
\(\displaystyle{ a_{n+1}=a_{n}^2-2}\)
Co ciekawe one stoją na miejscach:
\(\displaystyle{ 1,2,4,8,16,...,2^n,...}\)
Czyli kolejne potęgi dwójki...
Jest to ciekawe spostrzeżenie i uważam najciekawsza część zadania, gdzie ciąg zadany kwadratową rekurencją a więc niejednorodną i nie klasyczną
daje się "ucywilizować" do postaci jawnej bo teraz widać, że nasz ciąg ma wzór:
\(\displaystyle{ a_{n}=\left( 2+ \sqrt{3} \right)^{2^n}+ \left( 2- \sqrt{3} \right)^{2^n}, n=0,1,2,3,...}\)
Dalej to prawdopodobnie mamy zabawę w ciele:
\(\displaystyle{ \ZZ_{p^2}}\)
gdzie trójka jest lub nie jest resztą kwadratową...
Dodano po 10 godzinach 48 minutach 17 sekundach:
To się pobawmy
Jak wiadomo pewna liczba pierwsza p dzieli wyraz ciągu \(\displaystyle{ a_{n}}\)
Mamy więc:
\(\displaystyle{ 2+ \sqrt{3} = \frac{1}{2- \sqrt{3} } }\)
\(\displaystyle{ \left( 2+ \sqrt{3} \right)^{2^n}+ \left( 2- \sqrt{3} \right)^{2^n}=0 \mod p / \cdot \left( 2+ \sqrt{3} \right)^{2^n} }\)
\(\displaystyle{ \left( 2+ \sqrt{3} \right)^{2^{n+1}}=-1 /^2}\)
Ostatecznie mamy:
\(\displaystyle{ \left( 2+ \sqrt{3} \right)^{2^{n+2}}=1 \mod p}\)
Wynika stąd, że rząd elementu
\(\displaystyle{ 2+ \sqrt{3} }\)
W grupie multiplikatywnej ciała \(\displaystyle{ \ZZ_{p^2}}\) wynosi \(\displaystyle{ 2^{n+2}}\)
Grupa ta ma \(\displaystyle{ p^2-1}\) elementów
Co znaczy, że:
\(\displaystyle{ 2^{n+2}| p^2-1}\)
Przykład na przykład:
Ukryta treść:
Ostatnio zmieniony 22 sty 2023, o 13:32 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.