matematikk.net

La p være et primtall, og la [tex]a_i[/tex] være en heltallsfølge slik at [tex]a_0=0[/tex], [tex]a_1=1[/tex], [tex]a_{k+2}=2a_{k+1}-pa_k[/tex] for [tex] k \geq 0[/tex]. For hvilke verdier av [tex]p[/tex] er [tex]-1[/tex] et ledd i følgen?

For et primtall [tex]p[/tex] har vi gitt en rekursiv følge definert ved

[tex](1) \;\; a_k \: = \: 2a_{k-1} \:-\: pa_{k-2} \, , \,\, a_0 = 0, \, a_1 = 1[/tex].

Ved å anvende (1) og deretter induksjon får vi henholdsvis

[tex](2) \;\; a_k \: \equiv \: 2a_{k-1} \:-\: a_{k-2} \: = \: k \: \pmod{p-1},[/tex]

[tex](3) \;\; a_k \: \equiv \: 2a_{k-1} \: \equiv \: 2^{k-1} \: \pmod{p}.[/tex]

Anta at [tex]a_k = - 1[/tex] for et naturlig tall [tex]k[/tex]. Setter vi dette inn i (2), blir resultatet [tex] p-1 | k + 1[/tex], dvs. at

[tex](4) \;\; k + 1 \: = \: (p - 1)n[/tex]

for et naturlig tall [tex]n[/tex].

Vi observerer at [tex]p = 2[/tex] i (1) medfører at [tex]a_k[/tex] er et partall for alle [tex]k \, \neq \, 1[/tex]. Siden [tex]a_1 \,=\, 1 \, \neq \, -1[/tex], er [tex]p \, \neq \, 2.[/tex] M.a.o. er [tex]p[/tex] et odde primtall. Dermed gir Fermats lille teorem at

[tex](5) \;\; 2^{p-1} \, \equiv 1 \, \pmod {p}.[/tex]

Ved å kombinere (3), (4) og (5) blir resultatet

[tex]- 4 \, = \, 4a_k \, \stackre{(3)}{\equiv} \, 2^{k+1} \, \stackre{(4)}{=} \, 2^{(p-1)n}\, \stackre{(5)}{\equiv} \, 1^n \, = \, 1 \, \pmod{p},[/tex]

dvs. at [tex]p|5[/tex]. Følgelig må [tex]p=5[/tex], som innsatt i (1) gir dette [tex]a_2 = 2[/tex] og [tex]a_3 = -1.[/tex]

Konklusjon: Den rekursive følgen (1) inneholder leddet -1 hvis og bare hvis [tex]p = 5[/tex].