Matematyka.pl

modulo 9 dostajemy \(\displaystyle{ 5^y \equiv 2\pmod{9}}\) skąd łatwo dostać \(\displaystyle{ y=6t+5}\), jeżeli \(\displaystyle{ 2\mid x}\) to \(\displaystyle{ \pmod{5}}\) dostajemy \(\displaystyle{ (-1)^{\frac{x}{2}}+2 \equiv 0\pmod{5}}\) sprzeczność, więc \(\displaystyle{ x = 2k+1 \ , \ k \ge 1}\), czyli \(\displaystyle{ 3^{2k+1} + 2 \equiv 5^{6t+5} \pmod{7} \iff 3^{2k+1} \equiv (5^6)^t\cdot 5^5-2 \equiv 5^5-2 \equiv 1 \pmod{7}}\)

Jednak jak łatwo widzieć \(\displaystyle{ 3^n \equiv 1\pmod{7} \iff 6 \mid n}\), więc \(\displaystyle{ 6 \mid 2k+1}\) sprzeczność.

Dla dodatnich \(\displaystyle{ n}\):
\(\displaystyle{ a_{n}=3^{F_{n}}\cdot 2^{F_{n-1}+1}-2}\)
Nietrudno indukcją pokazać, że to prawda. Jak ktoś jest zainteresowany jak otrzymać taki no cóż... mocno nieoczywisty wzór, to pisać.
Zauważmy, że \(\displaystyle{ a_{0}-1=1}\), więc nie ma dzielników pierwszych. Mamy szukać dzielników pierwszych liczb postaci \(\displaystyle{ 3^{F_{n}}\cdot 2^{F_{n-1}+1}-2-1=3\cdot\left(3^{F_{n}-1}\cdot 2^{F_{n-1}+1}-1 \right)}\)
Jak widać, do zbioru szukanych liczb pierwszych nie należy \(\displaystyle{ 2}\), zaś należy z całą pewnością \(\displaystyle{ 3}\). Niech \(\displaystyle{ p \ge 5}\). Znanym faktem jest, że dla każdego \(\displaystyle{ k}\) istnieje takie \(\displaystyle{ m}\), że \(\displaystyle{ k\mid F_{m}}\). Tego się dowodzi jakoś zasadą szufladkową, pojawiało się to parę razy na forum, jak będzie trzeba to dowiodę. Niech więc \(\displaystyle{ k=p-1}\) i niech \(\displaystyle{ m}\) będzie taką liczbą, że \(\displaystyle{ k \mid F_{m}}\). Znanym faktem jest, że \(\displaystyle{ F_{m} \mid F_{lm}}\). Wtedy dla każdego dodatniego \(\displaystyle{ l}\) mamy \(\displaystyle{ F_{lm} \equiv 0 \pmod{k}}\). Niech \(\displaystyle{ F_{m+1} \equiv r \pmod{k}}\). Zauważmy, że gdy \(\displaystyle{ d=\left(r, \ k\right)}\), to \(\displaystyle{ d=1}\). W przeciwnym razie \(\displaystyle{ d \mid k \mid F_{m+1}-r \wedge d \mid r \Rightarrow d \mid F_{m+1}}\) i \(\displaystyle{ d \mid k \mid F_{m}}\) i mamy \(\displaystyle{ \left(F_{m}, \ F_{m+1}\right) \ge d >1}\), a znanym faktem jest, że nie może to być prawdą. Zauważmy, że \(\displaystyle{ F_{m+2} = F_{m+1}+F_{m} \equiv r+0 \equiv r \pmod{k}}\). Dalej \(\displaystyle{ F_{m+3} = F_{m+2}+F_{m+1}\equiv r+r\equiv 2r \pmod{k}}\), a to nam już dalej łatwo implikuje, że \(\displaystyle{ F_{m+i} \equiv F_{i} \cdot r \pmod{k}}\). W szczególności \(\displaystyle{ F_{2m+1} \equiv F_{m+1} \cdot r \equiv r^{2}}\). Powtarzając to rozumowanie uzyskujemy, że \(\displaystyle{ F_{2m+i}\equiv F_{i} \cdot r^{2} \pmod{k}}\), a w szczególności \(\displaystyle{ F_{3m+1} \equiv r^{3} \pmod{k}}\). To dalej indukuje nam, że \(\displaystyle{ F_{lm+i} \equiv F_{i} \cdot r^{l}}\), a w szczególności \(\displaystyle{ F_{lm+1} \equiv r^{l} \pmod{k}}\). Dla \(\displaystyle{ l=\lambda\left( k\right)}\), gdzie \(\displaystyle{ \lambda}\) jest funkcją Carmichaela mamy \(\displaystyle{ F_{ml+1}=F_{m\lambda \left( k\right) +1} \equiv r^{\lambda\left(k\right)} \equiv 1 \pmod{k}}\), co wynika z określenia funkcji Carmichaela. Wtedy \(\displaystyle{ F_{lm-1}=F_{lm+1}-F_{lm}\equiv 1-0 \pmod{k}}\) i dalej \(\displaystyle{ F_{lm-2}=F_{lm}-F_{lm-1} \equiv 0 -1 \equiv -1 \pmod{k}}\).
Dla każdej liczby pierwszej \(\displaystyle{ p \ge 5}\) wystarczy położyć \(\displaystyle{ n=m\lambda\left(p-1\right)-1}\), gdzie \(\displaystyle{ m}\) to taka liczba, że \(\displaystyle{ p-1 \mid F_{m}}\), mamy bowiem \(\displaystyle{ F_{n} \equiv 1 \pmod{p-1} \Leftrightarrow p-1\mid F_{n}-1}\) oraz \(\displaystyle{ F_{n-1} \equiv -1 \pmod{p-1} \Leftrightarrow p-1\mid F_{n-1}+1}\). Ostatecznie \(\displaystyle{ 3\cdot\left(3^{F_{n}-1}\cdot 2^{F_{n-1}+1}-1 \right) = 3\cdot\left(\left( 3^{x}\right)^{p-1}\cdot \left( 2^y\right)^{p-1}-1 \right)\equiv 3\cdot\left(1 \cdot 1-1 \right) \equiv 0 \pmod{p}}\) co wynika z małego twierdzenia Fermata. Zatem szukanym zbiorem jest zbiór nieparzystych liczb pierwszych.

Mając już do pokazania \(\displaystyle{ 2^{F_{n-1}+1}\cdot 3^{F_n-1} \equiv 1\pmod{p}}\), z mtfa wystarczy znaleźć takie \(\displaystyle{ t}\), że \(\displaystyle{ p-1 \mid F_{t-1}+1 \wedge p-1 \mid F_{t}-1}\)

Czyli patrząc na pary \(\displaystyle{ (F_k,F_{k+1})}\) modulo \(\displaystyle{ p-1}\) chcemy dostać parę \(\displaystyle{ (-1,1)}\), ale rozszerzając ciąg \(\displaystyle{ F_n}\) o parę wyrazów ujemnych dostajemy \(\displaystyle{ -1,1,0,1,1,2,3,...}\), skąd istnieje para \(\displaystyle{ (-1,1)}\), a ponieważ pary \(\displaystyle{ (F_k,F_{k+1}) \pmod{p-1}}\) w końcu nam się zapętlą (znany fakt, liczba różnych par jest skończona i każda para zależy tylko od poprzedniej pary), dostajemy, że istnieje (nawet nieskończenie wiele) taka dodatnia liczba \(\displaystyle{ t}\), że \(\displaystyle{ (F_t,F_{t+1}) = (-1,1)}\), cnd.

Sprowadzamy do postaci \(\displaystyle{ n^n(n^{n^3-n}-1)}\). Jako, że \(\displaystyle{ n^3-n=(n-1)n(n+1)}\), to z MTF otrzymujemy, że aby nasza liczba nie była podzielna przez \(\displaystyle{ 5}\), musi zachodzić \(\displaystyle{ n=4k+2}\). Bawiąc się trochę z przypadkami modulo 5, wychodzi że nie dzieli się przez 5 dla k dających w dzieleniu przez 5 resztę inną niż 1.

Dla \(\displaystyle{ n=10}\) lub \(\displaystyle{ 14}\) podzielność zachodzi.

Mamy rekurencję
\(\displaystyle{ \begin{cases} x_{0}=a \\ x_{1}=b \\ x_{n+1}=\frac{x_{n}x_{n-1}}{2}+x_{n}+x_{n-1} \text{ dla dodatnich } n\end{cases}}\)
Otóż należy zaobserwować, że \(\displaystyle{ x_{n+1}=\frac{1}{2}\left(x_{n}+2\right)\left(x_{n-1}+2\right)-2}\)
i tak o to \(\displaystyle{ x_{2}=\frac{1}{2}\left(a+2\right)\left(b+2\right)-2 \\
x_{3}=\frac{1}{2}\left(\frac{1}{2}\left(a+2\right)\left(b+2\right)-2+2\right)\left(a+2\right)-2=\left(\frac{1}{2}\right)^{2}\left(a+2\right)^{2}\left(b+2\right)-2 \\
x_{4}=\frac{1}{2}\left(\left(\frac{1}{2}\right)^{2}\left(a+2\right)^{2}\left(b+2\right)-2+2\right)\left(\frac{1}{2}\left(a+2\right)\left(b+2\right)-2+2\right)-2=\left(\frac{1}{2}\right)^{4}\left(a+2\right)^{3}\left(b+2\right)^{2}-2}\)
Nietrudno spostrzec, że wykładniki przy \(\displaystyle{ \left(a+2\right)}\) i \(\displaystyle{ \left(b+2\right)}\) zachowują się zupełnie jak kolejne wyrazy ciągu Fibonacciego, tzn. każdy z nich jest sumą dwóch poprzednich. Techniczną robotą jest ustalić szczegóły. Trochę inaczej jest z wykładnikiem przy \(\displaystyle{ \frac{1}{2}}\) - ten jest sumą dwóch poprzednich zwiększoną o jeden. Są dwa wyjścia z tej sytuacji - albo wypisać kilka początkowych wyrazów ciągu \(\displaystyle{ y_{n+1}=y_{n}+y_{n-1}+1}\) i zauważyć, że są to kolejne wyrazy ciągu Fibonacciego zmniejszone o jeden, albo wykorzystać funkcje tworzące (należy sparafrazować wyprowadzenie wzoru Bineta z ich użyciem).

Ostatecznie otrzymujemy \(\displaystyle{ x_{n}=\left( \frac{1}{2}\right)^{F_{n+1}-1}\cdot\left(a+2 \right)^{F_{n}}\cdot\left(b+2 \right)^{F_{n-1}}-2}\)
Gdy wstawimy \(\displaystyle{ a=4 \wedge b=2}\):

\(\displaystyle{ x_{n}=\left( \frac{1}{2}\right)^{F_{n+1}-1}\cdot 6^{F_{n}}\cdot 4^{F_{n-1}}-2=3^{F_{n}}\cdot 2^{1-F_{n+1}+F_{n}+2F_{n-1}}-2=3^{F_{n}}\cdot 2^{F_{n-1}+1}-2}\)

Popatrzmy co się dzieje dla \(\displaystyle{ n=k^2}\), wówczas \(\displaystyle{ u_n = k^2+\left[\sqrt{k^2+k}\right] = k^2+k}\) (gdyż \(\displaystyle{ k < \sqrt{k^2+k} < k+1}\))

Podstawmy \(\displaystyle{ n = k^2+r}\), gdzie \(\displaystyle{ 1 \le r \le k}\), wówczas:

\(\displaystyle{ u_n = k^2+r+\left[\sqrt{k^2+r+\left[\sqrt{k^2+r}\right]}\right] = k^2+r+\left[\sqrt{k^2+k+r}\right] = k^2+k+r}\)

Niech teraz \(\displaystyle{ k+1 \le r \le 2k}\), wówczas:

\(\displaystyle{ u_n = k^2+r+\left[\sqrt{k^2+r+\left[\sqrt{k^2+r}\right]}\right] = k^2+r+\left[\sqrt{k^2+k+r}\right] = k^2+k+r+1}\)

(gdyż dla \(\displaystyle{ 2k \ge r\ge k+1}\) jest \(\displaystyle{ k+1 \le \sqrt{k^2+k+r} < k+2}\))

Czyli dla każdego całkowitego dodatniego k mamy:

\(\displaystyle{ (u_{k^2},u_{k^2+1},...,u_{k^2+k},u_{k^2+k+1},...,u_{k^2+2k}) = (k^2+k , k^2+k+1 , ...,k^2+2k,k^2+2k+2,...,(k+1)^2 + (k+1)-1)}\)

Skąd istotnie występują w nim wszystkie liczby naturalne bez kwadratów.

Wbrew tezie załóżmy, że \(\displaystyle{ a+b=pq}\), gdzie \(\displaystyle{ p,q}\) są liczbami pierwszymi. Skoro \(\displaystyle{ a^3+b^3}\) jest kwadratem, to \(\displaystyle{ a^2-ab+b^2}\) musi być podzielne przez \(\displaystyle{ pq}\). Mamy także \(\displaystyle{ a \equiv -b \pmod{p}}\) i \(\displaystyle{ a \equiv -b \pmod{q}}\). Z tego, że \(\displaystyle{ a^2-ab+b^2 \equiv 0 \pmod{p}}\) otrzymujemy \(\displaystyle{ 3a^2 \equiv 3b^2 \equiv 0 \pmod{p}}\). Analogicznie \(\displaystyle{ 3a^2 \equiv 3b^2 \equiv 0 \pmod{q}}\). Stąd mamy dwie możliwości:
1) \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są podzielne zarówno przez \(\displaystyle{ p}\) jak i przez \(\displaystyle{ q}\). Stąd \(\displaystyle{ a=kpq \wedge b=lpq}\) dla pewnych całkowitych \(\displaystyle{ k,l \ge 1}\). Zatem \(\displaystyle{ a+b=(k+l)pq=pq}\), sprzeczność, gdyż \(\displaystyle{ k+l>1}\).
2) Jedna z liczb \(\displaystyle{ p,q}\) (niech to będzie \(\displaystyle{ p}\)) jest równa \(\displaystyle{ 3}\), a druga dzieli \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Wtedy dostajemy łatwo, że \(\displaystyle{ 3q=(k+l)q}\), ale to jest również sprzeczność, gdyż wtedy \(\displaystyle{ a^3+b^3=9q^3}\), co kwadratem na pewno nie jest.

Twierdzenie Dirichleta.