Mamy ciąg Lucasa zdefiniowany w sposób rekurencyjny:
\(\displaystyle{ L_{0}=2}\), \(\displaystyle{ L_{1}=1}\), \(\displaystyle{ L_{k+2}=L_{k+1}+L_{k}}\) dla \(\displaystyle{ k\geq0}\).
Czy wszystkie liczby pierwsze \(\displaystyle{ p}\) spełniają kongruencję \(\displaystyle{ L_{p}\equiv1\pmod{p}}\)? Czy istnieją liczby złożone \(\displaystyle{ c}\), które spełniają kongruencję \(\displaystyle{ L_{c}\equiv1\pmod{c}}\)?
Pierwsze wyrazy tak zdefiniowanego ciągu Lucasa () to:
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282
Edit:
No to sam sprawdziłem już...
Co prawda wszystkie liczby pierwsze faktycznie spełniają pożądaną kongruencję: \(\displaystyle{ L_{p}\equiv1\pmod{p}}\), dowód zapowiada się długi a bazuje na Małym Tw. Fermata, z którego wynika w końcu dla liczby pierwszej p: \(\displaystyle{ L_{p}\equiv L_{1}\equiv 1\pmod{p}}\)
jednak niestety niektóre liczby złożone także spełniają podaną kongruencję, sprawdziłem liczby w zakresie \(\displaystyle{ 2,3,...6000}\) i znalazłem wśród nich następujące kontrprzykłady: \(\displaystyle{ 705, 2465, 2737, 3745, 4181, 5777}\). Warto zauważyć, że wszystkie z nich są bezkwadratowe, a \(\displaystyle{ 2465}\) jest liczbą Carmichaela.
-- 22 lis 2009, o 11:24 --
Szkic dowodu na to, że wszystkie liczby pierwsze spełniają kongruencję \(\displaystyle{ L_{p}\equiv1\pmod{p}}\):
Niech \(\displaystyle{ a=\frac{1+\sqrt{5}}{2}}\) oraz \(\displaystyle{ b=\frac{1-\sqrt{5}}{2}}\). Wówczas \(\displaystyle{ L_{k}=a^k+b^k}\)
Skorzystajmy z tego, że dla liczby pierwszej \(\displaystyle{ p}\) spełnione jest następujące zdania:
\(\displaystyle{ (x+y)^p\equiv x^p+y^p\pmod{p}}\), oraz: \(\displaystyle{ z^p\equiv z\pmod{p}}\), co zachodzi dla całkowitej liczby \(\displaystyle{ z}\), a także z: \(\displaystyle{ z^{\frac{p-1}{2}}\equiv\pm1\pmod{p}}\) dla liczby całkowitej \(\displaystyle{ z}\) w zależności od tego, czy ta liczba jest resztą kwadratową modulo p (\(\displaystyle{ +1}\)), czy też jest nieresztą kwadratową modulo p (\(\displaystyle{ -1}\)).
Wobec powyższych:
\(\displaystyle{ a^p=(\frac{1+\sqrt{5}}{2})^p=(1+\sqrt{5})^p\cdot2^{-p}\equiv(1^p+\sqrt{5}\cdot5^\frac{p-1}{2})\cdot2^{-p}\equiv(1\pm\sqrt{5})\cdot2^{-1}\pmod{p}}\)
w zależności od tego, czy \(\displaystyle{ 5}\) jest kwadratową resztą czy kwadratową nieresztą modulo p.
Mamy także:
\(\displaystyle{ b^p=(\frac{1-\sqrt{5}}{2})^p=(1+(-\sqrt{5}))^p\cdot2^{-p}\equiv(1^p+(-\sqrt{5}\cdot5^\frac{p-1}{2}))\cdot2^{-p}\equiv(1\mp\sqrt{5})\cdot2^{-1}\pmod{p}}\)
również w zależności od tego, czy \(\displaystyle{ 5}\) jest kwadratową resztą czy kwadratową nieresztą modulo p.
Po zsumowaniu:
\(\displaystyle{ L_{p}=a^p+b^p\equiv(1\pm\sqrt{5})\cdot2^{-1}+(1\mp\sqrt{5})\cdot2^{-1}=1\pmod{p}}\), co było do udowodnienia.
Tu moja prośba, czy mógłby ktoś sprawdzić poprawność tego dowodu? Czy może przemilczałem jakieś dodatkowe założenia które należałoby poczynić by było dobrze?