Wykaż podzielność p-tego wyrazu ciągu.

[calka_oznaczona]

Ciąg \(\displaystyle{ (a_{n})}\) zdefiniowany jest rekurencyjnie: \(\displaystyle{ a_{n+1} = a_{n} + a_{n-1}, a_{0} = 2, a_{1} = 1}\). Wykazać, że \(\displaystyle{ p|a_{p} - 1}\) dla dowolnej liczby pierwszej \(\displaystyle{ p}\).

Byłabym bardzo wdzięczna za pomoc.

[Vax]

Zauważmy, że \(\displaystyle{ a_n = F_{n+1}+F_{n-1} , n\ge 1}\), gdzie \(\displaystyle{ F_n}\) jest n-tym wyrazem ciągu Fibonacciego. Istotnie, dla \(\displaystyle{ n=1, n=2}\) działa, załóżmy, że działa dla pewnych liczb \(\displaystyle{ k}\), \(\displaystyle{ k+1}\) wówczas:

\(\displaystyle{ a_{k+2} = a_k+a_{k+1} = F_{k+1}+F_{k-1}+F_{k+2}+F_k = (F_{k+2}+F_{k+1})+(F_k+F_{k-1}) = F_{k+3}+F_{k+1}}\) cnd.

Mamy więc pokazać, że dla dowolnej liczby pierwszej p zachodzi:

\(\displaystyle{ p | F_{p+1}+F_{p-1}-1}\)

Dla \(\displaystyle{ p=2}\) łatwo sprawdzić, że działa, załóżmy więc, że \(\displaystyle{ p \ge 3}\), korzystając ze wzoru Bineta dostajemy:

\(\displaystyle{ F_{p+1}+F_{p-1}-1= \frac{{p+1 \choose 1}+{p+1 \choose 3}\cdot 5 + {p+1 \choose 5}\cdot 5^2+...+{p+1 \choose p}\cdot 5^{\frac{p-1}{2}}}{2^p} + \frac{{p-1 \choose 1}+{p-1 \choose 3}\cdot 5+...+{p-1 \choose p-2}\cdot 5^{\frac{p-3}{2}}}{2^{p-2}}-1 = \frac{{p+1 \choose 1}+{p+1 \choose 3}\cdot 5+...+{p+1 \choose p}\cdot 5^{\frac{p-1}{2}}+4\left({p-1 \choose 1}+{p-1 \choose 3}\cdot 5+...+{p-1 \choose p-2}\cdot 5^{\frac{p-3}{2}}\right)-2^p}{2^p}}\)

Dodatkowo \(\displaystyle{ (p,2^p) = 1}\), więc wystarczy pokazać, że licznik dzieli się przez p. Łatwo zauważyć, że dla \(\displaystyle{ 2 \le k \le p-1}\) mamy:

\(\displaystyle{ p | {p+1 \choose k} = \frac{(p+1)!}{k!(p+1-k)!}}\).

Dla \(\displaystyle{ k=1}\) mamy oczywiście \(\displaystyle{ {p+1 \choose 1} \equiv 1 \pmod{p}}\)

Zauważmy również, że dla \(\displaystyle{ 0 \le k \le \frac{p-3}{2}}\) mamy:

\(\displaystyle{ {p-1 \choose 2k+1} \equiv \frac{(p-1)!}{(2k+1)!\cdot (p-2k-2)!} \equiv \frac{(p-(2k+1))(p-2k)(p-(2k-1))(p-(2k-2))...(p-1)}{(2k+1)!} \equiv \frac{(-1)^{2k+1}(2k+1)!}{(2k+1)!} \equiv -1 \pmod {p}}\)

(Ponieważ \(\displaystyle{ 1 \le 2k+1 \le p-2}\) więc \(\displaystyle{ (2k+1)!}\) w \(\displaystyle{ \mathbb{Z}_p}\) zawsze będzie posiadało element odwrotny)

Oraz z MTF mamy \(\displaystyle{ 2^p \equiv 2 \pmod{p}}\)

Tak więc:

\(\displaystyle{ {p+1 \choose 1}+{p+1 \choose 3}\cdot 5+...+{p+1 \choose p}\cdot 5^{\frac{p-1}{2}}+4\left({p-1 \choose 1}+{p-1 \choose 3}\cdot 5+...+{p-1 \choose p-2}\cdot 5^{\frac{p-3}{2}}\right)-2^p \equiv 1 +5^{\frac{p-1}{2}}+4\left(-1-5-5^2-...-5^{\frac{p-3}{2}}\right)-2 \equiv 1+5^{\frac{p-1}{2}}-4(\frac{5^{\frac{p-1}{2}}-1}{4})-2 \equiv 1+5^{\frac{p-1}{2}}-5^{\frac{p-1}{2}}+1-2 \equiv 2-2 \equiv 0\pmod{p}}\)

cnd.

[arek1357]

Mi się wydaje że można łatwiej sprowadzając ten ciąg do postaci jawnej mamy:


\(\displaystyle{ a_{p}= \frac{2 \sqrt{5}+5 }{5}( \frac{1- \sqrt{5} }{2} )^{p}+ \frac{5-2 \sqrt{5} }{5}( \frac{1+ \sqrt{5} }{2} )^{p}}\)

teraz jeśli to zwiniemy modulo p mamy:

\(\displaystyle{ \frac{2 \sqrt{5}+5 }{5}* \frac{1}{2^p}+ \frac{5-2 \sqrt{5} }{5}*\frac{1}{2^p}= \frac{2 \sqrt{5}+5 }{5}* \frac{1}{2}+ \frac{5-2 \sqrt{5} }{5}*\frac{1}{2}= \frac{10}{10}=1}\)

Oczywiście wykonywałem te działania w ciele:

\(\displaystyle{ Z_{p}[ \sqrt{5}]}\)