Matematyka.pl

Jeżeli nie zachodzi założenie \(\displaystyle{ 2a-1 \in \mathbb{P}}\), to przyjmując \(\displaystyle{ a=1}\) teza nie działa. Podobnie jeżeli \(\displaystyle{ 2b-1 \not\in \mathbb{P}}\) to biorąc \(\displaystyle{ b=1}\) dostajemy sprzeczność. Jeżeli nie zachodzi założenie \(\displaystyle{ a+b \in \mathbb{P}}\) to bierzemy \(\displaystyle{ a=b=2}\) i wówczas teza nie zachodzi. Pokażemy więc, że jeżeli \(\displaystyle{ a+b \ , \ 2a-1 \ , \ 2b-1 \in \mathbb{P}}\), to teza zachodzi. Istotnie, na początku zauważmy, że \(\displaystyle{ 2a-1 \ge 2 \Rightarrow a \ge 2}\), podobnie \(\displaystyle{ b \ge 2}\). Skoro \(\displaystyle{ a+b \in \mathbb{P}}\) to \(\displaystyle{ a,b}\) są różnej parzystości. Dodatkowo \(\displaystyle{ (a,b)=1}\), istotnie, jeżeli dla pewnego pierwszego \(\displaystyle{ t}\) mielibyśmy \(\displaystyle{ t \mid a \wedge t \mid b \Rightarrow t \mid a+b}\), ale \(\displaystyle{ a+b \in \mathbb{P} \wedge t < a+b \Rightarrow t=1}\) sprzeczność. Przyjmijmy bez straty ogólności \(\displaystyle{ 2 \nmid a \wedge 2 \mid b}\). Wówczas:

\(\displaystyle{ a^b+b^a \equiv (-b)^b+b^a \equiv b^a+b^b \pmod{a+b}}\)

Załóżmy, że \(\displaystyle{ a < b}\) (odwrotny przypadek rozpatrujemy analogiczne). Wówczas:

\(\displaystyle{ b^a+b^b \equiv b^a(b^{b-a}+1) \pmod{a+b}}\)

Załóżmy nie wprost, że:

\(\displaystyle{ a+b \mid a^b+b^a \iff b^a(b^{b-a}+1) \equiv 0\pmod{a+b} \Rightarrow b^{b-a} \equiv -1\pmod{a+b} \Rightarrow b^{2b-2a} \equiv 1\pmod{a+b}}\)

Niech \(\displaystyle{ k = ord_{a+b} b}\). Wówczas:

\(\displaystyle{ \begin{cases} k \mid 2b-2a \\ k \mid a+b-1 \\ k \nmid b-a \end{cases}}\)

Z 1 i 3 zależności wynika, że \(\displaystyle{ 2 \mid k}\). Jednak sumując 1 zależność i podwojoną drugą dostajemy \(\displaystyle{ k \mid 4b-2 = 2(2b-1)}\), ale \(\displaystyle{ 2b-1 \in \mathbb{P}}\) oraz \(\displaystyle{ 2 \mid k}\) więc może być jedynie \(\displaystyle{ k = 2 \vee k = 2(2b-1)}\). Jeżeli \(\displaystyle{ k=2}\) to \(\displaystyle{ a+b \mid b^2-1 = (b-1)(b+1)}\) sprzeczność, gdyż \(\displaystyle{ a+b > b+1}\). Więc \(\displaystyle{ k = 4b-2}\), ale wówczas \(\displaystyle{ 4b-2 \mid a+b-1 \Rightarrow 4b-2 \le a+b-1 \iff 3b \le a+1 < b+1 \Rightarrow 2b<1}\) sprzeczność.

Analogicznie dowodzimy \(\displaystyle{ a^a+b^b \not\equiv 0\pmod{a+b}}\)

Rozwiążemy to równanie od razu w całkowitych różnych od \(\displaystyle{ 1}\). Na początku załóżmy, że \(\displaystyle{ x,y \ge 2}\). Wówczas:

\(\displaystyle{ (x-1)(y-1) \mid 2xy-1 \iff xy-x-y+1 \mid 2xy-1-2(xy-x-y+1) = 2x+2y-3}\)

Dodatkowo musi być \(\displaystyle{ 2 \mid x,y}\). Istotnie, jeżeli któraś z \(\displaystyle{ x,y}\) byłaby nieparzysta to \(\displaystyle{ (x-1)(y-1)}\) byłoby parzyste, ale \(\displaystyle{ 2x+2y-3}\) dla dowolnych całkowitych x,y jest nieparzyste sprzeczność. Zauważmy, że \(\displaystyle{ x,y \ge 2 \Rightarrow 2x+2y-3 > 0}\), oraz \(\displaystyle{ xy-x-y+1 > 2x+2y-3 \iff (x-3)(y-3) > 5}\). Więc dla \(\displaystyle{ x,y \ge 6}\) dana podzielność nie zachodzi. Załóżmy bso, że \(\displaystyle{ 2 \le x \le 5}\), ale x jest parzyste, więc są możliwe tylko 2 przypadki, jeżeli \(\displaystyle{ x=2}\) otrzymujemy \(\displaystyle{ y-1 \mid 2y+1 - 2(y-1) = 3}\), co nam daje \(\displaystyle{ y=2 \vee y=4}\), jeżeli \(\displaystyle{ x=4}\) dostajemy \(\displaystyle{ 3y-3 \mid 2y+5}\), musi więc być \(\displaystyle{ 3y-3 \le 2y+5 \iff y \le 8}\), ale \(\displaystyle{ y}\) jest parzyste i po chwili dostajemy \(\displaystyle{ y = 2 \vee y = 8}\), więc dla \(\displaystyle{ x,y \ge 2}\) dostajemy pary \(\displaystyle{ (2,2),(2,4),(4,2),(4,8),(8,4)}\)
Załóżmy, że dokładnie jedna z \(\displaystyle{ x,y}\) jest niedodatnia. Bez straty ogólności \(\displaystyle{ y \le 0}\). Podstawmy \(\displaystyle{ y:=-y}\), dostajemy wówczas \(\displaystyle{ (x-1)(y+1) \mid 2x-2y-3}\), gdzie \(\displaystyle{ x\ge 2 \ , \ y \ge 0}\). Jeżeli \(\displaystyle{ y=0}\) to otrzymujemy \(\displaystyle{ x-1 \mid 2x-3-2(x-1) = -1}\) co nam daje parę \(\displaystyle{ (2,0)}\). Załóżmy, że \(\displaystyle{ y\ge 1}\), czyli \(\displaystyle{ (x-1)(y+1) \ge 2}\). Jeżeli \(\displaystyle{ x=y}\) podzielność przyjmuje postać \(\displaystyle{ (x-1)(x+1) \mid 3}\), więc w szczególności \(\displaystyle{ x-1 \mid 3}\) skąd \(\displaystyle{ x=2 \vee x=4}\), ale \(\displaystyle{ x=4}\) nie działa, więc otrzymujemy parę \(\displaystyle{ (2,-2)}\). Jeżeli \(\displaystyle{ x>y}\) to \(\displaystyle{ 2x-2y-3 \ge -1}\), jednak \(\displaystyle{ (x-1)(y+1) > 2x-2y-3 \iff (x+1)(y-1)+3 > 0}\) co przy naszych założeniach jest zawsze prawdziwe, więc w tym przypadku nie dostajemy żadnych nowych rozwiązań, jeżeli \(\displaystyle{ x<y}\) to mamy \(\displaystyle{ (x-1)(y+1) \mid 2y-2x+3}\), ale podobnie jak ostatnio \(\displaystyle{ (x-1)(y+1) > 2y-2x+3 \iff (x-3)(y+3) > -5}\), więc jeżeli \(\displaystyle{ x\ge 3}\) to dana podzielność nie zachodzi a \(\displaystyle{ x=2}\) sprawdzaliśmy wcześniej. Jeżeli obie niewiadome są niedodatnie, to podstawiając \(\displaystyle{ x:=-x , y:=-y}\) dostajemy \(\displaystyle{ (x+1)(y+1) \mid 2x+2y+3}\), ale \(\displaystyle{ (x+1)(y+1) > 2x+2y+3 \iff (x-1)(y-1) > 3}\), dla \(\displaystyle{ x,y \ge 3}\) nie dostajemy żadnych rozwiązań, jeżeli \(\displaystyle{ x \le 2}\), to dla \(\displaystyle{ x=0}\) dostajemy \(\displaystyle{ y+1 \mid 2y+3-2(y+1)=1}\) skąd otrzymujemy parę \(\displaystyle{ (0,0)}\), a gdy \(\displaystyle{ x=2}\) otrzymujemy \(\displaystyle{ 3y+3 \mid 2y+7}\) skąd łatwo dostajemy parę \(\displaystyle{ (-2,-4)}\), więc ostatecznie wszystkie pary spełniające daną podzielność to \(\displaystyle{ (x,y) = (-4,-2),(-2,-4),(-2,2),(0,0),(0,2),(2,-2),(2,0),(2,2),(2,4),(4,2),(4,8),(8,4)}\)

Na początku pokażemy, że każdy nieparzysty dzielnik liczby \(\displaystyle{ n^2+1}\) jest postaci \(\displaystyle{ 4l+1}\). Istotnie, załóżmy, że istnieje takie pierwsze \(\displaystyle{ p = 4k+3}\), że istnieje takie całkowite \(\displaystyle{ n}\), spełniające \(\displaystyle{ p \mid n^2+1 \iff n^2 \equiv -1 \pmod{4k+3}/^{2k+1} \Rightarrow n^{4k+2} \equiv -1\pmod{4k+3}}\) sprzeczność z małym twierdzeniem Fermata. Tak więc \(\displaystyle{ p = 4k+1}\). Jeżeli \(\displaystyle{ k = 3s+2}\), to \(\displaystyle{ p = 4(3s+2)+1 = 3(4s+3)}\), sprzeczność, gdyż wtedy \(\displaystyle{ 3 \mid p \wedge p \neq 3}\). Tak więc \(\displaystyle{ k = 3s \vee k = 3s+1}\) dla pewnego całkowitego \(\displaystyle{ s}\) co daje nam odpowiednio \(\displaystyle{ p = 12s+1 \vee p = 12s+5}\), cnd.

Z treści otrzymujemy, że \(\displaystyle{ q+1}\) jest nieparzyste. Rozważmy dowolną liczbę pierwszą \(\displaystyle{ p}\), taką, że \(\displaystyle{ p \mid q+1}\). Niech \(\displaystyle{ p^{\alpha} \parallel q+1}\). Na mocy \(\displaystyle{ \mathbb{LTE}}\)
\(\displaystyle{ v_{p}\left(q^{\left(q+1\right)^{n}}+1\right)=v_{p}\left(q^{\left(q+1\right)^{n}}+1^{\left(q+1\right)^{n}}\right)=v_{p}\left(q+1\right)+v_{p}\left(\left(q+1\right)^{n}\right)=\alpha+n\alpha=\left(n+1\right)\alpha}\)
co pociąga za sobą tezę zadania.

a) Teza jest nieprawdziwa, oto kontrprzykład:
\(\displaystyle{ 10^{3}-6^{3}=1000-216=784=28^{2} \\ 7^{1} \parallel 28}\)
a zatem taki rozkład jest niewykonalny
b) Co nie zmienia faktu, że da się wskazać przykłady. Sposób w jaki zapisano treść, sugeruje, że \(\displaystyle{ 0}\) także uznaje się za naturalne:
\(\displaystyle{ 4^{3}-0^{3}=\left(2^{2}+2^{2}\right)^{2} \\ 105^{3}-104^{3}=\left(9^{2}+10^{2}\right)^{2}}\)
c) Ponieważ teza jest nieprawdziwa, to pokażę jedynie, że równanie \(\displaystyle{ p^{3}-q^{3}=r^{2}}\) ma nieskończenie wiele rozwiązań w liczbach całkowitych. Pokażę nawet nieco więcej. Otóż równanie \(\displaystyle{ \left(n+1\right)^{3}-n^{3}=a^{2}}\) ma nieskończenie wiele rozwiązań w liczbach całkowitych.
Rozważmy równanie Pella \(\displaystyle{ x^{2}-3y^{2}=1}\). Ma ono nietrywialne rozwiązanie \(\displaystyle{ \left(2, \ 1\right)}\), które wyznacza pozostałe nietrywialne rozwiązania \(\displaystyle{ \left(x_{k}, \ y_{k}\right)}\) takie, że \(\displaystyle{ x_{k}+y_{k}\sqrt{3}=\left(2+\sqrt{3}\right)^{k}}\)
\(\displaystyle{ x_{2}+y_{2}\sqrt{3}=7 +4\sqrt{3}}\)
Dla dowolnego nieparzystego dodatniego \(\displaystyle{ k}\) stwierdzam, że \(\displaystyle{ x_{k}}\) jest parzyste. Istotnie dla \(\displaystyle{ k=1}\) jest to prawda. Niech będzie to prawdą, dla \(\displaystyle{ k=2l-1}\), czyli \(\displaystyle{ x_{2l-1}=2j}\), wówczas:
\(\displaystyle{ x_{2l+1}+y_{2l+1}\sqrt{3}=\left(2+\sqrt{3}\right)^{2l+1}=\left(2+\sqrt{3}\right)^{2l-1}\left(2+\sqrt{3}\right)^{2}=\left(x_{2l-1}+y_{2l-1}\sqrt{3}\right)\left(7+4\sqrt{3}\right)=\\=2\left(7j+6y_{2l-1}\right)+\left(8j+7y_{2l-1}\right)\sqrt{3}}\)
więc \(\displaystyle{ x_{2l+1}}\) jest parzyste, co kończy dowód indukcyjny. Zatem równanie \(\displaystyle{ x^{2}-3y^{2}=1}\) ma nieskończenie wiele całkowitych dodatnich rozwiązań postaci \(\displaystyle{ \left(2a, \ y\right)}\), gdzie \(\displaystyle{ a}\) jest całkowite dodatnie. A zatem nieskończenie wiele rozwiązań ma równanie \(\displaystyle{ 12a^{2}-9y^{2}=3}\). Oznaczmy \(\displaystyle{ b=3y}\). Nieskończenie wiele rozwiązań całkowitych dodatnich takich, że \(\displaystyle{ 3 \mid b}\) i \(\displaystyle{ 2 \nmid b}\) ma równanie \(\displaystyle{ 12a^{2}-b^{2}-3=0}\). Dla nieskończenie wielu \(\displaystyle{ a}\), wyrażenie \(\displaystyle{ 12a^{2}-3}\) jest kwadratem liczby całkowitej, podzielnym przez \(\displaystyle{ 3}\), a niepodzielnym przez \(\displaystyle{ 2}\). Ostatnie wyrażenie, to wyróżnik trójmianu \(\displaystyle{ 3n^{2}+3n+1-a^{2}}\) zmiennej \(\displaystyle{ n}\), który na mocy powyższych rozważań, dla nieskończenie wielu całkowitych \(\displaystyle{ a}\), ma rozwiązania całkowite dodatnie. Zatem równanie \(\displaystyle{ \left(n+1\right)^{3}-n^{3}=3n^{2}+3n+1=a^{2}}\) ma nieskończenie wiele rozwiązań w liczbach całkowitych co kończy dowód.

Z założenia \(\displaystyle{ a_{j} \in \mathbb{Z} \Rightarrow ja_{j} \in \mathbb{Z}}\). Układy wyjątkowe istnieją dla każdego \(\displaystyle{ k}\) i \(\displaystyle{ n}\). Wyznaczenie ich wszystkich nie jest możliwe. Ogólnie treść zadania nie ma sensu.

Oznaczmy \(\displaystyle{ ab+1=n^{2}}\). Uporządkujmy i oznaczmy elementy tego zbioru przez \(\displaystyle{ x_{1}, \ x_{2}, \ x_{3}, \ x_{4}}\) Mamy pokazać, że dla \(\displaystyle{ i \neq j}\) istnieje \(\displaystyle{ k \in \ZZ}\) takie, że \(\displaystyle{ x_{i}x_{j}+1=k^{2}}\). Musimy pokazać to dla sześciu par \(\displaystyle{ \left(i, \ j\right)}\): \(\displaystyle{ \left(1, \ 2\right), \ \left(1, \ 3\right), \ \left(1, \ 4\right), \ \left(2, \ 3\right), \ \left(2, \ 4\right), \ \left(3, \ 4\right)}\). Z uwagi na symetrię, możemy się ograniczyć, do czterech par: \(\displaystyle{ \left(1, \ 2\right), \ \left(1, \ 3\right), \ \left(1, \ 4\right), \ \left(3, \ 4\right)}\). Parę \(\displaystyle{ \left(1, \ 2\right)}\) mamy z założenia. Para \(\displaystyle{ \left(1, \ 3\right)}\):
\(\displaystyle{ a \cdot \left(a+b+2\sqrt{ab+1}\right)+1=a^{2}+ab+2an+1=a^{2}+n^{2}-1+2an+1=\left(a+n\right)^{2}}\)
Pozostałe dwie pary póki co są poza moim zasięgiem.
Oto przykład takiego zbioru:
\(\displaystyle{ \left\{2, \ 4, \ 12, \ 420\right\}}\)

Rozumiem, że suma dowolnych trzech, to suma dowolnych trzech niekoniecznie różnych?
Zakładam, że \(\displaystyle{ 0 \notin \NN}\), bo inaczej \(\displaystyle{ \mathbb{A}=\NN_{+} \wedge \mathbb{B}=\left\{ 0\right\}}\) spełniają warunki zadania. Bez straty ogólności niech \(\displaystyle{ 1 \in \mathbb{A}}\). Wówczas \(\displaystyle{ 1+1+1=3 \in \mathbb{A}, \ 3+1+1=5\in\mathbb{A}}\) i tak dalej każda liczba nieparzysta należy do \(\displaystyle{ \mathbb{A}}\). Niech \(\displaystyle{ a}\) będzie najmniejszą taką liczbą, że \(\displaystyle{ 2a\in\mathbb{A}}\). Wtedy \(\displaystyle{ 2a+1+1=2\left(a+1\right) \in \mathbb{A}}\) i w ten sposób wszystkie liczby parzyste \(\displaystyle{ \ge 2a}\) należą do \(\displaystyle{ \mathbb{A}}\). Skoro \(\displaystyle{ \mathbb{B}}\) ma być niepuste, to \(\displaystyle{ a\ge 2}\). Niech zatem \(\displaystyle{ b\ge 1}\) będzie największą taką liczbą, że \(\displaystyle{ 2b\in\mathbb{B}}\). Wówczas \(\displaystyle{ 2b+2b+2b=2(3b)\in\mathbb{B}}\), co jest sprzeczne z definicją \(\displaystyle{ b}\), bo \(\displaystyle{ 3b>b \Leftrightarrow b>0}\). A zatem taki podział nie istnieje.

a) Tu nie bardzo jest co dowodzić. No chyba, że nieświadomie prześlizguję się nad zasadniczą częścią dowodu. Niech \(\displaystyle{ m= \prod_{i=1}^{s}p_{i}^{\alpha_{i}} \wedge n= \prod_{i=1}^{t}q_{i}^{\beta_{i}} \wedge \left( m, \ n\right)=1 \Leftrightarrow p_{i}\neq q_{j}}\)
Wówczas:
\(\displaystyle{ \lambda\left(mn\right)= mn\prod_{p|mn}\left(1+\frac{1}{p}\right)=mn \prod_{i=1}^{s}\left(1+\frac{1}{p_{i}}\right) \prod_{i=1}^{t}\left(1+\frac{1}{q_{i}}\right)=mn \prod_{p|m}\left(1+\frac{1}{p}\right) \prod_{p|n}\left(1+\frac{1}{p}\right)=\lambda\left(m\right)\lambda\left(n\right)}\)
c)
\(\displaystyle{ 2=\prod_{p |n} \left( 1+\frac{1}{p} \right)= \prod_{p|n}\frac{p+1}{p} \Leftrightarrow L=2 \prod_{p|n}p= \prod_{p|n}\left(p+1\right)=P}\)
Niech \(\displaystyle{ 2\nmid n}\), wówczas \(\displaystyle{ v_{2}\left(L\right)=1=v_{2}\left(P\right)}\), co oznacza, że liczba \(\displaystyle{ n}\) ma jedynie jeden nieparzysty dzielnik pierwszy. Wstawienie tego pozwala uzyskać sprzeczność, bo \(\displaystyle{ 1}\) nie jest liczbą pierwszą. Zatem \(\displaystyle{ 2 \mid n}\).
\(\displaystyle{ v_{2}\left(L\right)=2=v_{2}\left(P\right)}\), co oznacza, że liczba \(\displaystyle{ n}\) ma co najwyżej dwa nieparzyste dzielniki pierwsze. Załóżmy, że ma dwa:
\(\displaystyle{ L=4pq=3\left(p+1\right)\left(q+1\right)=P}\)
\(\displaystyle{ 3|P \Leftrightarrow 3|L \Rightarrow p=3}\)
\(\displaystyle{ 12q=12\left(q+1\right) \Leftrightarrow 12=0}\)
więc sprzeczność. Niech zatem \(\displaystyle{ n}\) ma tylko jeden nieparzysty dzielnik pierwszy:
\(\displaystyle{ 4p=3\left(p+1\right) \Leftrightarrow p=3}\).
Co kończy dowód.

Jest to nic innego jak tylko .
Dla \(\displaystyle{ a=7 \wedge b=3}\)
są to:\(\displaystyle{ 1, \ 2, \ 4, \ 5, \ 8, \ 11}\)

Z twierdzenia Czebyszewa (postulatu Bertranda) mam jedną liczbę pierwszą w przedziale od \(\displaystyle{ \frac{n}{2}}\) do \(\displaystyle{ n}\). Ta liczba spełnia warunki zadania (bo już jej dwukrotność jest większa od \(\displaystyle{ n}\)).

Indukcja (gdy \(\displaystyle{ n=3}\) to \(\displaystyle{ (a_1, a_2. a_3)=(1, 2, 3)}\)). Mając \(\displaystyle{ (a_1, …, a_n)}\) określa się \(\displaystyle{ (b_1, ..., b_{n+1})}\):
\(\displaystyle{ \begin{cases} b_1= 1 \\ b_2 =n \\ b_j =(n+1)a_{j-1} \ n>2 \end{cases}}\).
(np. M 1854)

Pomysł (który nie musiał się udać) jest taki, żeby napisać rekurencję dla ciągu
\(\displaystyle{ a_n=\left( 3+\sqrt{p}\right)^{2n}+\left( 3-\sqrt{p}\right)^{2n}}\) i dobrać takie \(\displaystyle{ p}\), by \(\displaystyle{ |3-\sqrt{p}|<1}\), wówczas po ewentualnym sprawdzeniu paru trywialnych przypadków pozostałe części całkowite będą równe \(\displaystyle{ a_n}\) bądź \(\displaystyle{ a_n-1}\) (gdyż \(\displaystyle{ a_n}\) są całkowite, co w sposób trywialny można wykazać indukcyjnie), a to łatwiej kontrolować. Zauważmy bowiem, że gdy suma dwóch liczb jest liczbą całkowitą \(\displaystyle{ x}\), zaś jedna z tych liczb wpada do przedziału \(\displaystyle{ (0,1)}\), to część całkowita z tej drugiej wynosi \(\displaystyle{ x-1}\), natomiast jeśli suma dwóch liczb rzeczywistych daje liczbę całkowitą \(\displaystyle{ x}\) i jedna liczba wpada do przedziału \(\displaystyle{ (-1,0)}\), to część całkowita z tej drugiej liczby równa jest \(\displaystyle{ x}\).
Do dzieła:
chcielibyśmy znaleźć równanie kwadratowe postaci \(\displaystyle{ x^2+bx+c=0}\) takie, że liczby \(\displaystyle{ (3+\sqrt{p})^2}\) oraz \(\displaystyle{ (3-\sqrt{p})^2}\) są jego pierwiastkami. Ze wzorów Viete'a wynika wówczas, że \(\displaystyle{ -b=(3+\sqrt{p})^2+(3-\sqrt{p})^2=2p+18}\) oraz \(\displaystyle{ c=(9-p)^2}\),
czyli otrzymaliśmy współczynniki równania charakterystycznego, które możemy powiązać z rekurencją liniową jednorodną
\(\displaystyle{ a_{n+1}=(2p+18)a_{n}-(9-p)^2a_{n-1}, \ n\ge 1}\)
z warunkami początkowymi
\(\displaystyle{ a_0=2, \ a_1=2p+18}\)
(oczywiście więc \(\displaystyle{ a_n\in \NN^+}\) dla każdego \(\displaystyle{ n}\)).
Warunki zadania są spełnione dla \(\displaystyle{ p=5}\), oto dowód indukcyjny:
dla \(\displaystyle{ n=0}\) mamy \(\displaystyle{ 2^1|(1+1)}\), czyli OK, zaś dla \(\displaystyle{ n=1}\) mamy
\(\displaystyle{ 2^2|(27+1)}\), czyli też się zgadza. Tak w ogóle, to odnotujmy, że \(\displaystyle{ (3-\sqrt{5})^{2n}\in (0,1)}\) dla każdego \(\displaystyle{ n}\) całkowitego dodatniego, zatem
\(\displaystyle{ \left\lfloor (3+\sqrt{5})^{2n}\right\rfloor+1=a_n}\). Pokazujemy więc w zasadzie, że gdy \(\displaystyle{ p=5}\) w powyższym wzorze rekurencyjnym, to \(\displaystyle{ 2^{n+1}|a_n}\) dla każdego \(\displaystyle{ n}\).
Krok indukcyjny: jeśli \(\displaystyle{ 2^{n}|a_{n-1}}\) oraz \(\displaystyle{ 2^{n+1}|a_n}\), to
\(\displaystyle{ a_{n+1}=28a_n-16a_{n-1}=2^2(7a_{n}-4a_{n-1})}\)
i \(\displaystyle{ 2^{n}}\) dzieli tak liczbę \(\displaystyle{ 7a_n}\), jak i \(\displaystyle{ 4a_{n-1}}\), więc dzieli też ich różnicę, no i \(\displaystyle{ 2^{n+2}|2^2(7a_{n}-4a_{n-1})}\)

Zatem uzyskaliśmy \(\displaystyle{ p\le 5}\).
Zauważmy także, że dla \(\displaystyle{ p=2}\) mamy
\(\displaystyle{ a_{2}=22a_1-49a_0=22^2-98=386}\)
oraz \(\displaystyle{ 5<\left( \frac 3 2\right)^4 <(3-\sqrt{2})^4<\left( \frac 8 5\right)^4=\frac{4096}{625}<7}\), czyli
\(\displaystyle{ (3+\sqrt{2})^4\in(379, 381)}\), stąd
\(\displaystyle{ \left\lfloor(3+\sqrt{2})^4\right\rfloor+1\in \left\{ 380, 381\right\}}\), ale liczba \(\displaystyle{ 381}\) jest w ogóle nieparzysta, zaś \(\displaystyle{ 2^3\nmid 380}\), gdyż \(\displaystyle{ 380=4\cdot 95}\).
Czyli dla \(\displaystyle{ p=2}\) warunki zadania nie są spełnione.
Pozostaje sprawdzić możliwość \(\displaystyle{ p=3}\).
To jednak nie jest skomplikowane (choć znów rachunkowe), bo nie zgadza się już dla \(\displaystyle{ n=1}\).
Jeśli \(\displaystyle{ p=3}\), to mamy \(\displaystyle{ a_0=2, \ a_1=24=(3-\sqrt{3})^2+(3+\sqrt{3})^2}\), tymczasem
\(\displaystyle{ 1<(3-\sqrt{3})^2<2}\), więc
\(\displaystyle{ 23>(3+\sqrt{3})^2>22}\) i oczywiście w związku z tym \(\displaystyle{ 2^2\nmid \left\lfloor (3+\sqrt{3})^2\right\rfloor+1}\).

Odpowiedź: \(\displaystyle{ p=5}\).

33 OM - II - 5:

16 OM - III - 4:

Niech \(\displaystyle{ m = 13k + l}\), gdzie \(\displaystyle{ k, l}\) to liczby całkowite oraz \(\displaystyle{ 0 \le l \le 12}\). Wtedy
\(\displaystyle{ \left\lfloor \frac{3m + 4}{13}\right\rfloor - \left\lfloor \frac{m - 28 - \left\lfloor \frac{m - 7}{13}\right\rfloor}{4} \right\rfloor = \left\lfloor \frac{3(13k + l) + 4)}{13} \right\rfloor - \left\lfloor \frac{13k + l - 28 - \left\lfloor \frac{13k +l - 7}{13}\right\rfloor}{4} \right\rfloor = \left\lfloor \frac{39k + 3l + 4}{13}\right\rfloor - \left\lfloor \frac{13k + l - 28 - k - \left\lfloor \frac{l - 7}{13}\right\rfloor}{4}\right\rfloor = \left\lfloor 3k + \frac{3l + 4}{13}\right\rfloor - \left\lfloor \frac{12k + l - 28 - \left\lfloor \frac{l - 7}{13}\right\rfloor}{4}\right\rfloor = 3k + \left\lfloor \frac{3l + 4}{13} \right\rfloor - \left\lfloor 3k - 7 + \frac{l - \left\lfloor \frac{l - 7}{13} \right\rfloor}{4}\right\rfloor = 7 + \left\lfloor \frac{3l + 4}{13}\right\rfloor - \left\lfloor \frac{l - \left\lfloor \frac{l - 7}{13} \right\rfloor}{4}\right\rfloor}\)
Pozostaje pokazać, że \(\displaystyle{ \left\lfloor \frac{3l + 4}{13}\right\rfloor = \left\lfloor \frac{l - \left\lfloor \frac{l - 7}{13} \right\rfloor}{4}\right\rfloor}\).

Gdy \(\displaystyle{ 0 \le l \le 6}\) to \(\displaystyle{ \left\lfloor \frac{l - 7}{13} \right\rfloor = -1}\), czyli trzeba pokazać, że \(\displaystyle{ \left\lfloor \frac{3l + 4}{13}\right\rfloor = \left\lfloor \frac{l +1} {4}\right\rfloor}\).
Gdy \(\displaystyle{ 0 \le l \le 2}\) to \(\displaystyle{ \left\lfloor \frac{3l + 4}{13}\right\rfloor = \left\lfloor \frac{l +1} {4}\right\rfloor = 0}\).
Gdy \(\displaystyle{ 3 \le l \le 6}\) to \(\displaystyle{ \left\lfloor \frac{3l + 4}{13}\right\rfloor = \left\lfloor \frac{l +1} {4}\right\rfloor = 1}\).

Gdy \(\displaystyle{ 7 \le l \le 12}\) to \(\displaystyle{ \left\lfloor \frac{l - 7}{13} \right\rfloor = 0}\), czyli trzeba pokazać, że \(\displaystyle{ \left\lfloor \frac{3l + 4}{13}\right\rfloor = \left\lfloor \frac{l} {4}\right\rfloor}\).
Gdy \(\displaystyle{ l = 7}\) to \(\displaystyle{ \left\lfloor \frac{3l + 4}{13}\right\rfloor = \left\lfloor \frac{l} {4}\right\rfloor = 1}\).
Gdy \(\displaystyle{ 8 \le l \le 11}\) to \(\displaystyle{ \left\lfloor \frac{3l + 4}{13}\right\rfloor = \left\lfloor \frac{l} {4}\right\rfloor = 2}\).
Gdy \(\displaystyle{ l = 12}\) to \(\displaystyle{ \left\lfloor \frac{3l + 4}{13}\right\rfloor = \left\lfloor \frac{l} {4}\right\rfloor = 3}\).
cnd.

Można popatrzeć na ten ciąg, a w zasadzie na sumę jego pierwszych wyrazów na wykresie w układzie współrzędnych. Niech oś y odpowiada za sumę pierwszych wyrazów tego ciągu, a oś x to ostatnia pozycja do której liczymy sumę. To znaczy zaznaczamy punkty \(\displaystyle{ (x, \sum_{i = 1}^{x} x_i)}\) dla \(\displaystyle{ 0\le x \le 17}\) całkowitych i łączymy je. Szukamy liczby takich wykresów, które zaczynają się we współrzędnej \(\displaystyle{ (0, 0)}\) a kończą w \(\displaystyle{ (17, 11)}\) i nie schodzą poniżej osi x. Niech \(\displaystyle{ a_{x, y}}\) to liczba takich wykresów zaczynających się w \(\displaystyle{ (0, 0)}\) a kończących w \(\displaystyle{ (17, 11)}\) nie schodzących poniżej osi x. Wtedy piszemy równania rekurencyjne:
\(\displaystyle{ a_{0, y} = [y = 0]}\)
Do punktu możemy dojść na trzy sposoby z punktu o współrzędnej x o jeden mniejszej (dokładając \(\displaystyle{ -1}\) lub \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\)):
\(\displaystyle{ a_{x, y} = [y \ge 1] \cdot a_{x - 1, y - 1} + a_{x - 1, y} + a_{x - 1, y + 1}}\) dla \(\displaystyle{ x \ge 1, y \ge 0}\).
\(\displaystyle{ a_{17, 11} = ?}\)
Wrzucamy to w komputer (piszemy programowanie dynamiczne, w zewnętrznej pętli for idziemy po kolejnych x-ach a wewnętrznej po y-kach) i liczymy.

PEN Problems, A1: [url]https://artofproblemsolving.com/community/c146h150369p849187[/url], trudne

Pokażę, że \(\displaystyle{ p|F_{p+1}}\), to jest chyba istotnie łatwiejsza część. Wobec braku magicznego pomysłu skorzystam ze znanego wzoru Bineta:
\(\displaystyle{ F_n =\frac{1}{\sqrt{5}}\left( \frac 1 2+\frac{\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left( \frac 1 2-\frac{\sqrt{5}}{2}\right)^n}\)
Jak to rozwiniemy ze wzoru dwumianowego, to dużo się skróci i zostanie
\(\displaystyle{ \frac{1}{2^{n-1}} \sum_{2\nmid k}^{}{n \choose k}5^{ \frac{k-1}{2} }}\)
Interesuje więc nas dowód, że każda liczba pierwsza \(\displaystyle{ p}\) postaci \(\displaystyle{ 10l\pm 3}\) dzieli \(\displaystyle{ \sum_{2\nmid k}^{}{p+1 \choose k}5^{ \frac{k-1}{2} }}\), bo oczywiście dla każdej liczby pierwszej \(\displaystyle{ p>2}\) jest \(\displaystyle{ \NWD(2^i, p)=1}\).
Odnotujmy taką rzecz, że dla
\(\displaystyle{ k=2,3, \ldots p-1}\) mamy \(\displaystyle{ p|{p+1 \choose k}}\) (łatwe), w szczególności w naszej sumie badając podzielność przez \(\displaystyle{ p}\) wystarczy zająć się pierwszym i ostatnim wyrazem, tj. \(\displaystyle{ {p+1\choose 1}+{p+1\choose p}5^{\frac{p-1}{2}}}\)
Oczywiście \(\displaystyle{ {p+1\choose 1}=p+1\equiv 1\pmod{p}}\) i podobnie z \(\displaystyle{ {p+1\choose p}}\), chcemy więc wiedzieć, że gdy liczba pierwsza \(\displaystyle{ p}\) jest postaci \(\displaystyle{ p=10l\pm 3, \ k\in \NN^+}\), to \(\displaystyle{ 5^{\frac{p-1}{2}}\equiv -1\pmod{p}}\).
Niestety nie mam w tej chwili pomysłu na elementarne rozwiązanie, skorzystamy z własności symbolu Legendre'a:
wiadomo, że \(\displaystyle{ 5^{\frac{p-1}{2}}\pmod{p}=\left( \frac{5}{p}\right)}\), a to jest równe \(\displaystyle{ -1}\) dokładnie wtedy, gdy \(\displaystyle{ 5}\) jest nieresztą kwadratową modulo \(\displaystyle{ p}\). Pokażemy, że tutaj tak jest w istocie.
Odnotujmy, że wszystkie reszty kwadratowe modulo \(\displaystyle{ 5}\) to \(\displaystyle{ 0,1,4}\) (można sobie rozpisać z kongruencji w przypadkach).
Ponadto oczywiście \(\displaystyle{ 5\equiv 1\pmod{4}}\). Na mocy

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Prawo_wzajemno%C5%9Bci_reszt_kwadratowych

dostajemy, że
– dla \(\displaystyle{ p=10l+3}\) kongruencja \(\displaystyle{ x^2\equiv 5\pmod{p}}\) ma rozwiązanie wtedy i tylko wtedy, gdy istnieje rozwiązanie kongruencji \(\displaystyle{ y^2\equiv p\pmod{5}}\), no ale \(\displaystyle{ p=10l+3\equiv 3\pmod{5}}\) i jak wspomniałem \(\displaystyle{ 3}\) jest nieresztą kwadratową modulo \(\displaystyle{ 5}\);
– dla \(\displaystyle{ p=10l-3}\) kongruencja \(\displaystyle{ x^2\equiv 5\pmod{p}}\) znowuż ma rozwiązanie wtedy i tylko wtedy, gdy rozwiązanie ma kongruencja \(\displaystyle{ y^2\equiv p\pmod{5}}\), no ale
\(\displaystyle{ p=10l-3\equiv 2\pmod{5}}\) i \(\displaystyle{ 2}\) też jest nieresztą kwadratową modulo \(\displaystyle{ 5}\).
Zbierając to do kupy, widzimy, że gdy \(\displaystyle{ p=10l\pm 3}\), to \(\displaystyle{ \left( \frac{5}{p}\right) =-1}\), czyli \(\displaystyle{ 5^{ \frac{p-1}{2} }\equiv -1\pmod{p}}\),
a więc istotnie
\(\displaystyle{ p| \sum_{2\nmid k}^{}{p+1 \choose k}5^{ \frac{k-1}{2} }}\),
co kończy rozwiązanie pierwszej części zadania.

Co do \(\displaystyle{ p^2\nmid F_{p+1}}\), jak na razie się poddałem, długo nad tym siedziałem, ale nawet nie zbliżyłem się do rozwiązania. Może ktoś ruszy… Ja jestem za mało inteligentny niestety.
Wydaje mi się też, że to zadanie rozwiązywał gdzieś user Marcin7Cd, ale nie mogę teraz znaleźć.

a) Zacznijmy od dwóch tożsamości nietrudnych do udowodnienia:
1) \(\displaystyle{ \arcctg x=\arctg\left( \frac 1 x\right), \ x>0}\)
By ją udowodnić, wystarczy zauważyć, że dla \(\displaystyle{ x_0=1}\) jest równość, gdyż obie strony wynoszą \(\displaystyle{ \frac{\pi}{4}}\) oraz że pochodna funkcji
\(\displaystyle{ f(x)=\arcctg(x)-\arctg\left( \frac 1 x\right)}\) jest równa zero.
2) \(\displaystyle{ \arctg x+\arctg y=\arctg\left( \frac{x+y}{1-xy}\right)}\) dla \(\displaystyle{ |xy|<1}\).
Korzystając z tożsamości 1) i 2) przepisujemy tezę
\(\displaystyle{ \arcctg(F_{2n+1}) + \arcctg(F_{2n+2}) = \arcctg(F_{2n})}\)
w postaci
\(\displaystyle{ \arctg\left( \frac{ \frac{1}{F_{2n+1}}+\frac{1}{F_{2n+2}} }{1-\frac{1}{F_{2n+1}F_{2n+2}}} \right)=\arctg\left( \frac{1}{F_{2n}}\right)}\)
Ponieważ funkcja arcus tangens jest różnowartościowa, ma to miejsce
wtedy i tylko wtedy, gdy argumenty są równe, tj.
\(\displaystyle{ \frac{F_{2n+2}+F_{2n+1}}{F_{2n+2}F_{2n+1}-1}=\frac{1}{F_{2n}}\\F_{2n}F_{2n+3}=F_{2n+2}F_{2n+1}-1\\ F_{2n+2}F_{2n+1}-F_{2n}F_{2n+3}=1}\)
a to jest prawda i nietrudno udowodnić to indukcyjnie. Można to tak przekształcić:
\(\displaystyle{ F_{2n+2}F_{2n+1}-F_{2n}F_{2n+3}=\\=(F_{2n}+F_{2n+1})F_{2n+1}-F_{2n}(2F_{2n+1}+F_{2n})=\\=F_{2n+1}^2-F_{2n}^2-F_{2n}F_{2n+1}=\\=(F_{2n}+F_{2n-1})^2-F_{2n}^2-(F_{2n-1}+F_{2n-2})F_{2n+1}=\\=2F_{2n}F_{2n-1}+F_{2n-1}^2-F_{2n-1}F_{2n+1}-F_{2n-2}F_{2n+1}=\\=2F_{2n}F_{2n-1}+F_{2n-1}^2-F_{2n-1}(F_{2n}+F_{2n-1})-F_{2n-2}F_{2n+1}=\\=F_{2n}F_{2n-1}-F_{2n-2}F_{2n+1}}\)
i wystarczy sprawdzić, że \(\displaystyle{ F_4F_3-F_5F_2=6-5=1}\).

b) Mamy wykazać, że
\(\displaystyle{ F_{2n}|F_{3n}+(-1)^n F_n}\)
Udowodnimy najpierw tożsamość
\(\displaystyle{ F_{2n}=F_{n+1}^2-F_{n-1}^2}\)
W tym celu używamy indukcji o takim schemacie: z prawdziwości tezy dla \(\displaystyle{ k=1, \ k=2}\) i z własności \(\displaystyle{ T(k-1)\wedge T(k)\rightarrow T(k+1)}\), którą wykażemy, wnioskujemy, że teza zachodzi dla każdego \(\displaystyle{ n\in \NN^+}\).
Bazę indukcji pominę, sorry, w kroku indukcyjnym otrzymujemy, że
\(\displaystyle{ F_{2k+2}=F_{2k+1}+F_{2k}=2F_{2k}+F_{2k-1}=3F_{2k}-F_{2k-2}=\\=3(F_{k+1}^2-F_{k-1}^2)-(F_{k}^2-F_{k-2}^2)=\\=3F_k(F_{k+1}+F_{k-1})+F_{k-2}^2-F_k^2=\\=3F_k(F_{k+1}+F_{k-1})+(F_{k}-F_{k-1})^2-F_k^2=\\=F_{k-1}(F_k+F_{k-1})+3F_k F_{k+1}=\\=F_{k+1}(F_{k-1}+3F_k)=\\=F_{k+1}^2+2F_k F_{k+1}=\\=F_{k+1}F_{k+2}+F_{k}F_{k+1}=\\=F_{k+1}F_{k+2}+F_k(_{k+2}-F_k)=\\=F_{k+2}^2-F_k^2}\)
tak jak chcieliśmy.

Następnie podamy szkic dowodu tożsamości
\(\displaystyle{ F_{3n}=5F_{n}^3+3(-1)^n F_n}\),
dla odmiany nieindukcyjny, bo ile można.
Mamy:
\(\displaystyle{ a^3-b^3=(a-b)\left( a^2+ab+b^2\right) =\\=(a-b)\left( (a-b)^2+3ab\right) =\\=(a-b)^3+3ab(a-b)}\),
kładziemy \(\displaystyle{ a=\left( \frac{1+\sqrt{5}}{2}\right)^n, \ b= \left( \frac{1-\sqrt{5}}{2}\right)^n}\), zauważamy, że \(\displaystyle{ ab=(-1)^n}\), wstawiamy do powyższej równości
i patrzymy (por. wzór Bineta na \(\displaystyle{ F_n}\)), jak się mają nasze \(\displaystyle{ a, b}\) do \(\displaystyle{ F_n}\)(tj. \(\displaystyle{ F_n=\sqrt{5}a-\sqrt{5}b}\)).

Czyli sprowadziliśmy tezę do tego, że
\(\displaystyle{ F_{n+1}^2-F_{n-1}^2}\) dzieli liczbę \(\displaystyle{ 5F_n^3+4(-1)^n F_n}\),
a ponieważ oczywiście
\(\displaystyle{ F_{n+1}^2-F_{n-1}^2=F_n(F_{n+1}+F_{n-1})}\),
to należy udowodnić, że
\(\displaystyle{ F_{n+1}+F_{n-1}}\) dzieli \(\displaystyle{ 5F_n^2+4\cdot (-1)^n}\),
a to też lepiej robić bez indukcji.
Nasuwa się taki wzorek:
\(\displaystyle{ (a+b)^2=(a-b)^2+4ab}\)
Kładziemy w nim \(\displaystyle{ a=F_{n+1}, \ b=F_{n-1}}\)
i otrzymujemy:
\(\displaystyle{ (F_{n+1}+F_{n-1})^2=F_n^2+4F_{n-1}F_{n+1}}\)
Przekształcając teraz następującą tożsamość Cassiniego (znane, pozostawię bez dowodu, bo i tak post jest za długi; fajnie się to dowodzi z użyciem macierzy):
\(\displaystyle{ F_n^2=F_{n-1}F_{n+1}+(-1)^{n-1}}\)
możemy zapisać
\(\displaystyle{ 4F_{n-1}F_{n+1}=4F_n^2+4(-1)^n}\),
a zatem otrzymaliśmy:
\(\displaystyle{ 5F_n^2+4(-1)^n=(F_{n+1}+F_{n-1})^2}\),
co kończy dowód.

Warunek 1. spełniają układy zawierające :
a) 11 jedynek i 6 zer,
b) 12 jedynek, 4 zera i 1 minus jedynka,
c) 13 jedynek, 2 zera i 2 minus jedynki,
b) 14 jedynek i 3 minus jedynki.
Liczba przestawień powyższych układów które spełniają warunek 2. to:
a)
\(\displaystyle{ il_a= \frac{17!}{11!6!}}\)
b)
\(\displaystyle{ il_b= \blue{12} \cdot \frac{14 \cdot 15 \cdot 16 \cdot 17}{4!}}\)
Ustawiam jedynki w szereg. Dla -1 wybieram jedno z 11 miejsc miedzy jedynkami lub miejsce za nimi.. Potem wstawiam zera w miejsca między liczbami lub na końce szeregu.
c)
\(\displaystyle{ il_c= \blue{12} \cdot \frac{ 16 \cdot 17}{4!}+ \red{ \frac{ 12 \cdot 13}{2!}} \cdot \frac{ 16 \cdot 17}{2!}}\)
Ustawiam jedynki w szereg, a jedną z -1 wstawiam miedzy dwie pierwsze jedynki. Dla drugiej -1 wybieram jedno z 12 miejsc miedzy jedynkami (licząc od prawej strony drugiej jedyniki) lub miejsce za nimi.. Potem wstawiam zera w miejsca między liczbami lub na końce szeregu.
Obie -1 wstawiam na miejsca miedzy jedynkami (licząc od prawej strony drugiej jedynki) lub miejsce za nimi.. Potem wstawiam zera w miejsca między liczbami lub na końce szeregu.
d)
\(\displaystyle{ il_d= \blue{\frac{12!}{11!1!} }+ \red{ \frac{ 13!}{11!2!}}+ \green {\frac{ 12!}{11!1!}} + \frac{ 14!}{11!3!}}\)
ilość przestawień pozostałych elementów za początkowym układem 1,-1,1,-1,1,..
ilość przestawień pozostałych elementów za początkowym układem 1,-1,1,1,..
ilość przestawień pozostałych elementów za początkowym układem 1,1,-1,-1,1,..
ilość przestawień pozostałych elementów za początkowym układem 1,1,1,..

Istnieją naturalne a,b takie że:
\(\displaystyle{ \left( 6+ \sqrt{31} \right) ^{2009}=a+b \sqrt{31} \\
\left( 6- \sqrt{31} \right) ^{2009}=a-b \sqrt{31}}\)
Dodając równania stronami dostaję:
\(\displaystyle{ \left( 6+ \sqrt{31} \right) ^{2009}+\left( 6- \sqrt{31} \right) ^{2009}=2a}\)

Skoro \(\displaystyle{ 0<6- \sqrt{31}<1}\) to \(\displaystyle{ 0<\left( 6- \sqrt{31} \right) ^{2009}<1}\), więc
\(\displaystyle{ \lfloor\left( 6+ \sqrt{31} \right) ^{2009}\rfloor+1=2a=\\
=2\left[ {2009 \choose 0}6^{2009}+{2009 \choose 2}6^{2007}31 +{2009 \choose 4}6^{2005}31^2+...+{2009 \choose 2008}6^131^{1004} \right] =}\)
Ponieważ szukam tyko ostatniej cyfry wyrażenia które zawiera sumy i iloczyny, to wynik zależy tylko od ostatnich cyfr czynników i składników. Niech dowolną liczbą naturalną o cyfrze jedności x będzie \(\displaystyle{ \overline{??x}}\).
\(\displaystyle{ =2\left[ {2009 \choose 0}\overline{??6}+{2009 \choose 2}\overline{??6} +{2009 \choose 4}\overline{??6}+...+{2009 \choose 2008}\overline{??6}\right]=\\
=2\left[ {2009 \choose 0}\overline{??6}+{2009 \choose 1}\overline{??6} +{2009 \choose 2}\overline{??6}+...+{2009 \choose 1004}\overline{??6}\right]=}\)
Wszystkie symbole Newtona o \(\displaystyle{ k \ge 10}\) są podzielne przez 10 więc
\(\displaystyle{ =2\left[ {2009 \choose 0}\overline{??6}+{2009 \choose 1}\overline{??6} +{2009 \choose 2}\overline{??6}+...+{2009 \choose 9}\overline{??6}\right]=\\
=2\left[ \overline{??6}+\overline{??9} \ \overline{??6} +
\overline{??6} \ \overline{??6}+\overline{??4} \ \overline{??6} +\overline{??6} \ \overline{??6}+\overline{??6} \ \overline{??6} +\overline{??4} \ \overline{??6}+\overline{??6} \ \overline{??6} +
\overline{??9} \ \overline{??6}+\overline{??1} \ \overline{??6} \right]=\\
=2\left[ \ \overline{??2} \ \right]= \ \overline{??4}}\)
\(\displaystyle{ \lfloor\left( 6+ \sqrt{31} \right) ^{2009}\rfloor=\overline{??4}-1=\overline{??3}}\)
Ostatnią cyfrą jest trójka.

ilość cyfr \(\displaystyle{ \lfloor\left( 6+ \sqrt{31} \right) ^{2009}\rfloor}\) to:
\(\displaystyle{ \lfloor \log \left( 6+ \sqrt{31} \right) ^{2009}\rfloor +1=\lfloor 2009\log \left( 6+ \sqrt{31} \right) \rfloor +1=2137}\)

12480
12492
12495
12496
12501
12504
12510
12520
12525
12528
12532
12540
12544
12546
12558
12563
12564
12570
12582
12600
12610
12612
12614
12615
12618
12636

Udowodnimy najpierw indukcyjnie następującą nierówność dla \(\displaystyle{ n\ge 4}\):
\(\displaystyle{ \left( \frac{p_{n+1}-1}{2}\right)^2 \ge p_1+p_2+\ldots +p_n \ (*)}\)
\(\displaystyle{ 1^{\circ}}\) Mamy \(\displaystyle{ p_5=11}\) i widzimy, że
\(\displaystyle{ \left( \frac{11-1}{2}\right)^2=25\ge 2+3+5+7=p_1+p_2+p_3+p_4}\)
\(\displaystyle{ 2^{\circ}}\) Przypuśćmy, że dla pewnego \(\displaystyle{ n\ge 4}\) zachodzi
\(\displaystyle{ \left( \frac{p_{n+1}-1}{2}\right)^2\ge p_1+p_2+\ldots +p_n}\).
Odnotujmy, że
\(\displaystyle{ \left( \frac{p_{n+2}-1}{2}\right)^2-\left( \frac{p_{n+1}-1}{2}\right)^2=\\= \frac{p_{n+2}-p_{n+1}}{2} \cdot \frac{p_{n+1}+p_{n+2}-2}{2}}\)
i wystarczy skorzystać z nierówności \(\displaystyle{ p_{k+1}\ge p_k+2}\) dla \(\displaystyle{ k\ge 2}\), by wywnioskować stąd, że
\(\displaystyle{ \left( \frac{p_{n+2}-1}{2}\right)^2-\left( \frac{p_{n+1}-1}{2}\right)^2\ge p_{n+1}}\)
Dodając tę nierówność stronami do założenia indukcyjnego, otrzymujemy co chcieliśmy.

Przejdziemy teraz do rozwiązania zadania. Najpierw sprawdzimy małe przypadki:
\(\displaystyle{ S_1=2<2^2<2+3=S_2\\ S_2=2+3<3^2<2+3+5=S_3\\ S_3=2+3+5<4^2<17=2+3+5+7=S_4}\),
czyli OK.
Niech teraz \(\displaystyle{ n\ge 3}\) i niech
\(\displaystyle{ k_1=\max\left\{ k\in \NN^+: k^2<S_n\right\}}\)
(oczywiście \(\displaystyle{ k_1}\) istnieje, bo zbiór \(\displaystyle{ \left\{ k\in \NN^+: k^2<S_n\right\}}\) jest skończonym i niepustym podzbiorem \(\displaystyle{ \NN^+}\), chociażby należy do niego \(\displaystyle{ 1}\)).
Przypuśćmy nie wprost, że
\(\displaystyle{ (k_1+1)^2\ge S_{n+1}=S_n+p_{n+1}}\).
Ponieważ mamy
\(\displaystyle{ (k_1+1)^2=k_1^2+2k_1+1}\) oraz \(\displaystyle{ k_1^2<S_n}\), więc musi być:
\(\displaystyle{ 2k_1+1>p_{n+1}}\), ale wtedy na mocy \(\displaystyle{ (*)}\) jest
\(\displaystyle{ p_1+p_2+\ldots+p_n > k_1^2>\left(\frac{p_{n+1}-1}{2} \right)^2\ge p_1+p_2+\ldots+p_n}\), sprzeczność.
Gdyby się zdarzyło, że \(\displaystyle{ S_n}\) jest kwadratem dla pewnego \(\displaystyle{ n}\), wystarczy zmienić definicję \(\displaystyle{ k_1}\) (z nierównością nieostrą zamiast ostrej) i dalej działa.
Podoba mi się elementarność tej metody, ale może dałoby się napisać rozwiązanie nieindukcyjne? Naprawdę chętnie bym zobaczył. Przekopię może stacka w poszukiwaniu takowego.

Daruję sobie drugą część, bo sorry, ale wygląda na niezły syf.
Nie widzę żadnego porządku w resztach \(\displaystyle{ S_n}\) modulo \(\displaystyle{ 4}\) (czy \(\displaystyle{ 3}\), czy inna mała liczba, która ma niewiele reszt kwadratowych), a to dodatkowe pytanie rozumiem jako pytanie o to, czy \(\displaystyle{ S_n=45^2}\) dla pewnego \(\displaystyle{ n}\) (jeśli nie, to odpowiedź na dodatkowe pytanie jest twierdząca).

PS wolfram powiedział mi, że \(\displaystyle{ S_{33}<2025<S_{34}}\), ale to się raczej nie liczy.

Niech \(\displaystyle{ m=f(n)= \frac{n}{d(n)}= \frac{p_1^{w_1} \cdot ... \cdot p_k^{w_k}}{(w_1+1) \cdot ... \cdot (w_k+1)}}\) gdzie \(\displaystyle{ p _{i}}\) to liczba pierwsza, a \(\displaystyle{ w_i}\) to jej naturalny, dodatni wykładnik.
Przykładowe najmniejsze liczby dobre :
\(\displaystyle{ 1=f(2^1)\\
2=f(2^3)=f(2^23^1)\\
3=f(3^2)=f(2^33^1)}\)
Dobrą będzie każda kolejna liczba pierwsza p gdyż:
\(\displaystyle{ f(p^1 \cdot 2^3)=f(p^1 \cdot 2^23^1)= \frac{p}{1+1} \cdot 2=p}\)
więc najmniejszej naturalnej nie będącej dobrą szukam wśród liczb złożonych:
\(\displaystyle{ 4=f(2^23^2)\\
6=f(2^33^2)\\
8=f(2^45^1)\\
9=f(2^23^3)\\
10=f(2^23^25^1)\\
12=f(2^43^15^1)\\
14=f(2^23^27^1)\\
15=f(2^33^25^1)\\
16=f(2^7)}\)

Szukam n dla \(\displaystyle{ m=18=2 \cdot 3^2}\). Liczba n powinna być złożoną z czynnikiem będącym potęgą trójki.
\(\displaystyle{ 18=2 \cdot 3^2= \frac{3^a\cdot ...}{(a+1)\cdot ...}}\)
Są tylko dwie możliwości:
1)
\(\displaystyle{ f(3^3 \cdot ...)= \frac{3^3\cdot ...}{(3+1)\cdot ...}=9 \cdot \frac{3}{4} \cdot \frac{ ...}{ ...}}\)
2)
\(\displaystyle{ f(3^4 \cdot ...)= \frac{3^4\cdot ...}{(4+1)\cdot ...}=9 \cdot \frac{9}{5} \cdot \frac{ ...}{ ...}}\)
Ponadto liczba n powinna zawierać czynnik będący potęgą dwójki i taki że: f\(\displaystyle{ (2^b) \le \frac{4}{3} \cdot 2}\). Jeśli zawiera także inne czynniki \(\displaystyle{ p^c}\) to i one muszą spełniać \(\displaystyle{ f(p^c)\le \frac{8}{3}}\). Możliwe są tylko: \(\displaystyle{ 2^1 \ , \ 2^2 \ , \ 2^3 \ , \ 5^1}\) ale dla każdej liczby n złożonej z dostępnych czynników \(\displaystyle{ f(n) \neq 18}\).
Wniosek. Najmniejsza dodatnia liczba naturalna która nie jest dobrą to 18.

Teza zadania z pewnością nie jest spełniona, gdy \(\displaystyle{ a\equiv 2\pmod{4}}\) (a tak się dzieje np. dla \(\displaystyle{ a=22, \ a=34}\)…), a to dlatego, że jeśli \(\displaystyle{ a+b+c=u^2, \ b+c=v^2}\) dla pewnych naturalnych \(\displaystyle{ u,v}\), to liczba
\(\displaystyle{ a=u^2-v^2=(u-v)(u+v)}\)
albo jest nieparzysta, albo dzieli się przez \(\displaystyle{ 4}\), gdyż \(\displaystyle{ u+v\equiv u-v\pmod{2}}\).
Treść do poprawy lub zadanie do wyrzucenia.

\(\displaystyle{ x^4-y^4=2z^2}\)
Oczywiście liczby \(\displaystyle{ x,y}\) muszą być tej samej parzystości. Jeśli obie są parzyste, to mamy schodzenie modulo \(\displaystyle{ 2}\):
\(\displaystyle{ x=2p, \ y=2q}\) dla pewnych \(\displaystyle{ p,q\in \NN^+}\), stąd
\(\displaystyle{ 8(p^4-q^4)=z^2}\),
czyli \(\displaystyle{ 8|z^2}\), a więc \(\displaystyle{ 16|z^2}\), stąd \(\displaystyle{ 4|z}\), niech więc \(\displaystyle{ z=4r, \ r\in \NN^+}\)
i po uproszczeniu mamy:
\(\displaystyle{ p^4-q^4=2r^4}\),
czyli to samo równanie, tylko z mniejszymi liczbami. Nie możemy powtarzać tego algorytmu w nieskończoność (wynika to z zasady minimum i faktu, że \(\displaystyle{ x,y}\) w naszym równaniu mają być całkowite dodatnie), wystarczy więc rozważyć przypadek, w którym \(\displaystyle{ 2\nmid x \wedge 2\nmid y}\), co poniżej uczynię.
Niech \(\displaystyle{ d=\NWD(x,y)}\). Wówczas \(\displaystyle{ d}\) jest liczbą nieparzystą oraz \(\displaystyle{ d^4|2z^2}\), stąd \(\displaystyle{ d^4|z^2}\), a zatem \(\displaystyle{ d^2|z}\). Niech więc
\(\displaystyle{ x=da', \ y=db, \ z=d^2 c, \ a,b,c\in \NN^+}\). Równanie przyjmuje postać:
\(\displaystyle{ a^4-b^4=2c^2}\),
przy czym \(\displaystyle{ a,b}\) są nieparzyste oraz \(\displaystyle{ \NWD(a,b)=1}\).
Mamy ze wzoru na różnicę kwadratów:
\(\displaystyle{ (a^2-b^2)(a^2+b^2)=2c^2}\)
Ponadto \(\displaystyle{ a^2+b^2\equiv 2\pmod{4}}\), gdyż obie liczby \(\displaystyle{ a,b}\) są nieparzyste, a stąd
\(\displaystyle{ \frac{a^2+b^2}{2}}\) jest liczbą całkowitą i nieparzystą. Mamy zatem równoważnie:
\(\displaystyle{ (a^2-b^2)\cdot \left( \frac{a^2+b^2}{2}\right)=c^2}\)
Jeżeli teraz \(\displaystyle{ k=\NWD\left( a^2-b^2, \frac{a^2+b^2}{2}\right)}\),
to \(\displaystyle{ k}\) jest liczbą nieparzystą, która dzieli zarówno liczbę \(\displaystyle{ a^2-b^2+2\cdot\frac{a^2+b^2}{2}=2a^2}\),
jak i liczbę \(\displaystyle{ a^2-b^2-2\cdot\frac{a^2+b^2}{2}=-2b^2}\),
ale skoro \(\displaystyle{ \NWD(a,b)=1}\), to \(\displaystyle{ \NWD(a^2, b^2)=1}\) (wystarczy rozważyć liczbę pierwszą \(\displaystyle{ p}\), która dzieliłaby \(\displaystyle{ \NWD(a^2, b^2)}\) i przez sprzeczność łatwo wychodzi), zatem \(\displaystyle{ k=1}\). Zatem zarówno
\(\displaystyle{ a^2-b^2}\), jak i \(\displaystyle{ \frac{a^2+b^2}{2}}\) są kwadratami liczb całkowitych dodatnich.
Niech więc (w całkowitych dodatnich i nieparzystych, \(\displaystyle{ \NWD(a,b)=1}\))
\(\displaystyle{ a^2-b^2=m^2, \ a^2+b^2=2n^2}\).
Jednak rozumując podobnie jak wcześniej (co najwyżej jedna z liczb \(\displaystyle{ a-b, a+b}\) dzieli się przez \(\displaystyle{ 4}\), bo \(\displaystyle{ a,b}\) są nieparzyste i kombinujemy z \(\displaystyle{ \NWD}\)), dochodzimy do wniosku, że bez straty ogólności
\(\displaystyle{ \frac{a-b}{2}}\) oraz \(\displaystyle{ \frac{a+b}{2}}\) są kwadratami liczb całkowitych dodatnich, ponadto ich \(\displaystyle{ \NWD}\) wynosi \(\displaystyle{ 1}\).
Ponadto mamy
\(\displaystyle{ \left( \frac{a-b}{2}\right)^2+\left( \frac{a+b}{2}\right)^2= \frac{a^2+b^2}{2}=n^2}\),
zatem rozwiązanie naszego problemu prowadziłoby do rozwiązania w liczbach całkowitych dodatnich równania:
\(\displaystyle{ s^4+t^4=n^2}\),
przy czym \(\displaystyle{ \NWD(s,t)=1}\), bo \(\displaystyle{ \NWD(s^2, t^2)=1}\).
Zatem \(\displaystyle{ s^2, \ t^2, n}\) tworzą pierwotną trójkę pitagorejską. Próbowałem to wykorzystać, jednak nie wpadłem samodzielnie na absolutnie kluczowy pomysł:
mianowicie przypuśćmy, że \(\displaystyle{ n}\) jest najmniejsze możliwe (istnieje z zasady minimum, o ile zbiór rozwiązań jest niepusty).
Skoro \(\displaystyle{ s^2, \ t^2, \ n}\) tworzą pierwotną trójkę pitagorejską, to dla względnie pierwszych \(\displaystyle{ u, v}\) b.s.o. \(\displaystyle{ s^2=u^2-v^2, \ t^2=2uv, \ n=u^2+v^2}\)
W szczególności \(\displaystyle{ s^2+v^2=u^2}\) i \(\displaystyle{ \NWD(s,v)=1}\), bo \(\displaystyle{ \NWD(u,v)=1}\).
Czyli \(\displaystyle{ s,v, u}\) tworzą kolejną pierwotną trójkę pitagorejską, niech więc
\(\displaystyle{ s=k^2-l^2, \ v=2kl, \ u=k^2+l^2, \ k>l, \NWD(k,l)=1}\)
Mamy jednak \(\displaystyle{ t^2=2uv=4kl(k^2+l^2)}\),
czyli \(\displaystyle{ \left( \frac t 2\right)^2=kl(k^2+l^2)}\)
Skoro jednak \(\displaystyle{ \NWD(k,l)=1}\), to dowolny dzielnik pierwszy liczby \(\displaystyle{ k}\) nie dzieli ani \(\displaystyle{ l}\), ani \(\displaystyle{ k^2+l^2}\) i podobnie z liczbą \(\displaystyle{ l}\): dowolny jej dzielnik pierwszy nie może dzielić ani \(\displaystyle{ k}\), ani \(\displaystyle{ k^2+l^2}\).
Liczby pierwsze w rozkładzie kwadratu liczby całkowitej dodatniej występują z parzystymi wykładnikami, w związku z tym i z powyższym tak \(\displaystyle{ k}\), jak i \(\displaystyle{ l}\) muszą być kwadratami liczb całkowitych dodatnich, tj. niech \(\displaystyle{ k=d^2, \ l=e^2, \ d,e\in \NN^+}\).
Otrzymaliśmy:
\(\displaystyle{ \left( \frac{t}{2de}\right)^2=d^4+e^4}\)
Jednakże skoro \(\displaystyle{ s^4+t^4=n^2}\), to \(\displaystyle{ t^2<n}\), w szczególności tutaj \(\displaystyle{ t<n}\), a tym bardziej \(\displaystyle{ \frac{t}{2de}<n}\), sprzeczność z minimalnością \(\displaystyle{ n}\).
Co kończy dowód.

Natomiast wersję z \(\displaystyle{ x^4-y^4=z^2}\) (nie ma rozwiązania w całkowitych dodatnich, więc nie ma też nieskończenie wielu; gdyby miała choć jedno w całkowitych dodatnich, to od razu miałaby nieskończenie wiele, bo gdy \(\displaystyle{ (p,q,r)}\) pasują, to \(\displaystyle{ (2p, 2q, 4r)}\) też)
robi się podobnie z tym \(\displaystyle{ d=\NWD(x,y)}\), tylko że otrzymujemy potem \(\displaystyle{ a^2-b^2=m^2, \ a^2+b^2=n^2}\) i tu sprzeczność następuje szybciej, bo reszty kwadratowe modulo \(\displaystyle{ 4}\) to \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\), a dla nieparzystego \(\displaystyle{ b}\) mamy \(\displaystyle{ 2b^2\equiv 2\pmod{4}}\).