Benutzer:Tanik/Lucas-Test

„Es wird wohl noch mindestens eine Million Jahre vergehen, bevor wir die Primzahlen verstehen“ Paul Erdös

Lucas-Test

Lucas-Folgen

Definition (Lucas-Folgen)

Gegeben sei die Gleichung ${}X^{2}-PX+Q=0$ mit ${}P,Q\in \mathbb {Z}$ und ${}P\not =0,\,Q\not =0$, die Lösungen seien die reellen Zahlen ${}a$ und ${}b,\,a\not =b$. ${}U_{n}$ und ${}V_{n}$ werden durch

${}U_{n}={\frac {a^{n}+b^{n}}{a-b}},\,n\geq 0\,$

${}V_{n}={\frac {a^{n}+b^{n}}{a+b}},\,n\geq 0\,$

definiert und Lucas-Folgen genannt.

Bemerkung  

Die Gleichung ${}X^{2}-PX+Q=0$ hat Diskriminante ${}D=P^{2}-4Q\not =0$ und damit die Lösungen

${}a={\frac {P+{\sqrt {D}}}{2}}{\text{ und }}b={\frac {P+{\sqrt {D}}}{2}}.\,$

Man beachte, dass ${}D\equiv 0\,\,(mod\,4)\,\,oder\,\,D\equiv 1\,\,(mod\,4).$

Bemerkung (Eigenschaften der Folgeglieder)  

Die Folgenglieder für ${}n=0\,\,{\text{und}}\,\,n=1$ kann man leicht ablesen:

${}U_{0}=0,\,\,U_{1}=1\,$

${}V_{0}=2,\,\,V_{1}=a+b=P\,$

Die Lucas-Folgen erfüllen die Rekursion

${}U_{n+2}=PU_{n+1}-QU_{n}\,\,\,$

bzw.

${}V_{n+2}=PV_{n+1}-QV_{n}\,\,,{\text{wobei}}\,\,n\geq 0\,,$

Das heisst, dass jeder Term hängt linear von den zwei vorherigen ab.

Diese Rekursionen kann man durch Nachrechnen überprüfen.

${}{\begin{aligned}PU_{n+1}-QU_{n}&=(a+b){\frac {a^{n+1}-b^{n+1}}{a-b}}-ab{\frac {a^{n}-b^{n}}{a-b}}\\&={\frac {a^{n+2}-ab^{n+1}+ba^{n+1}-b^{n+2}-a^{n+1}b+ab^{n+1}}{a-b}}\\&={\frac {a^{n+2}-b^{n+2}}{a-b}}\\&=U_{n+2}\,.\end{aligned}}$

Die Richtigkeit der zweiten Rekursion kann analog gezeigt werden.

Die Lucas-Folgen haben noch weitere Eigenschaften. Man geht davon aus, dass ${}m\not \geq n$ ist, dann gilt:

${}{\begin{aligned}U_{m+n}&={\frac {a^{m+n}-b^{m+n}}{a-b}}\\&={\frac {(a^{m}-b^{m})(a^{n}+b^{n})}{a-b}}-{\frac {a^{n}b^{n}(a^{m-n}-b^{m-n})}{a-b}}\\&=U_{m}V_{n}-Q^{n}U_{m-n}\,;\end{aligned}}$

${}{\begin{aligned}V_{m+n}&=a^{m+n}+b^{m+n}\\&=(a^{m}+b^{m})(a^{n}+b^{n})-a^{n}b^{n}(a^{m-n}+b^{m-n})\\&=V_{m}V_{n}-Q^{n}V_{m-n}\,.\end{aligned}}$

Daraus für ${}m=n\,$ folgt:

${}U_{2n}=U_{n}V_{n}-Q^{n}U_{0}=U_{n}V_{n}\,$

${}V_{2n}=V_{n}U_{n}-Q^{n}V_{0}={V_{n}}^{2}-2Q^{n}\,$

und für ${}m=n+1\,$:

${}U_{2n+1}=U_{n+1}V_{n}-Q^{n}U_{1}=U_{n+1}V_{n}-Q^{n}\,$

${}V_{2n+1}=V_{n+1}V_{n}-Q^{n}V_{1}=V_{n+1}V_{n}-Q^{n}P\,.$

Damit wurde gezeigt, dass alle Folgeglieder aus $\mathbb {Z}$ sind.

Teilbarkeitseigenschaften der Folgeglieder $\,\,\,\,\,U_{n}$

Definition (Quadratischer Zahlenkörper)

Für ein quadratfreies ${}D\,\,\,$ heisst die Menge

${}Q({\sqrt {D}})={a+b{\sqrt {D}}\,\,{\text{mit}}\,\,a,b\in \mathbb {Q} -\,\,\,\,}$ quadratischer Zahlenkörper.

Für ein ${}a=a_{1}+a_{2}{\sqrt {D}}$ ist dann ${}\,\,\,\ {\overline {a}}=a_{1}-a_{2}{\sqrt {D}}$.

Sei $P^{2}-4Q=c^{2}D$ mit $c,D\in \mathbb {N}$ und $D$ quadratfrei. Ist $D>1\,,$ so sind die Lösungen $a,b$ der Gleichung $X^{2}-PX+Q=0\,$ irrationale Zahlen aus dem quadratischen Zahlenkörper $Q({\sqrt {D}}).$

Jeztz kann man ein Pendant zum Kleinen Fermatschen Satz in $A_{d}$ formulieren.

Satz

Wenn ${}a\in A_{D}$ und ${}p$ eine ungerade Primzahl, dann

${}a^{p}\equiv a\,\,(mod\,p),{\text{falls}}\left({\frac {D}{p}}\right)=+1\,\,$

oder

${}a^{p}\equiv {\overline {a}}\,\,(mod\,p),{\text{falls}}\left({\frac {D}{p}}\right)=-1\,\,.$

Beweis

Benutzer:Tanik/Lucas-Test/Fakt/Beweis

$\Box$

Falls $a(mod\,p)\,$ in $A_{d}\,$ eine Einheit ist, dann folgt aus dem Satz, dass

$a^{p-1}\equiv 1\,\,\,(mod\,p)\,,$ falls $\,\left({\frac {D}{p}}\right)=1\,$

oder

$a^{p+1}\equiv a{\overline {a}}\,\,\,(mod\,p)\,,$ falls $\,\left({\frac {D}{p}}\right)=-1\,.$

Lemma

Die Bedingung ${}ggT(a,p)=1\,$ in ${}A_{D}\,$, ist identisch mit der Bedingung ${}ggT(Q,p)=1\,$ in ${}\ N\,$.

Beweis

Benutzer:Tanik/Lucas-Test/ggt-Lemma/Fakt/Beweis

$\Box$

Aus Identitäten ergeben sich für $U_{p-1}\,$ und $U_{p+1}\,$ folgende Berechnungen(beachte $b={\overline {a}}\,$):

$U_{p-1}={\frac {a^{p-1}-{\overline {a}}^{p-1}}{a-{\overline {a}}}}\equiv {\frac {a{\overline {a}}-{\overline {a}}}{a-{\overline {a}}}}\equiv 0\,\,(mod\,p)\,,$falls$\,\left({\frac {D}{p}}\right)=1\,$

$U_{p+1}={\frac {a^{p+1}-{\overline {a}}^{p+1}}{a-{\overline {a}}}}\equiv {\frac {1-1}{a-{\overline {a}}a}}\equiv 0\,\,(mod\,p)\,,$falls$\,\left({\frac {D}{p}}\right)=-1\,$

Bemerkung  

1. ${}a-{\overline {a}}$ soll wegen Division nicht ${}0\,\,\,$ sein
2. ${}(a-{\overline {a}})^{2}=c^{2}D\,\,$ daraus folgt, dass ${}ggt(c,p)=1\,$ sein muss
3. Zusammen mit ${}ggT(Q,p)=1\,\,\,$ muss die Bedingung ${}ggT(cQ,p)=1\,$ erfüllt sein.

Verhalten Potenzen von $a$ bzw. $\,\,\,\,\,U_{n}$ bezüglich der Teilbarkeit durch $p^{n}$

Falls $\left({\frac {D}{p}}\right)=1\,$ ist $a^{p}=a+kp\,$ für ein bestimmtes $k\in \mathbb {N} \,$ und deshalb gilt $a^{p^{n}}=(a^{p})^{p^{n-1}}=(a+kp)^{p^{n-1}}\equiv a^{p^{n-1}}\,\,(mod\,\,p^{n})\,$ , weil alle Terme abseits des ersten $a^{p^{n-1}}\,$ stets den Faktor $p^{n}\,$ enthalten. Man kann unter der Bedingung, dass $a(mod\,p)\,$ in $A_{d}\,$ eine Einheit ist, durch Division durch $a^{p^{n-1}}\,$ das Folgende erhalten:

$a^{p^{n}}\equiv a^{p^{n-1}}\Rightarrow a^{{p^{n}}-{p^{n-1}}}\equiv 1\Rightarrow a^{p^{n-1}(p-1)}\equiv 1(mod\,\,p^{n})\,.$

Analog erhält man

$a^{p^{n}}\equiv {\overline {a}}^{p^{n-1}}\Rightarrow a^{p^{n}}a^{p^{n-1}}\equiv ({\overline {a}}a)^{p^{n-1}}\equiv a^{p^{n-1}(p-1)}\equiv (a{\overline {a}})^{p^{n+1}}(mod\,\,p^{n})\,.$

Mit diesen Identitäten können die folgenden Folgeglieder $U_{i}\$ berechnet werden:

$U_{p^{n-1}(p-1)}\equiv 0\,\,\,(mod\,\,p^{n})\,$ für $\,\left({\frac {D}{p}}\right)=1\,$

$U_{p^{n-1}(p+1)}\equiv 0\,\,\,(mod\,\,p^{n})\,$ für $\,\left({\frac {D}{p}}\right)=-1\,.$

Das lässt sich wie folgt zusammenfassen:

$U_{p^{n-1}(p-\left({\frac {D}{p}}\right))}\equiv 0(mod\,\,p^{n})\,$ für $\,ggT(2QcD,p)=1\,.$

Die Beschränkung $\,ggT(2QcD,p)=1\,,$ folgt aus dem Lemma und Bemerkung oben.