matematikk.net

Definer følgen [tex]a_i[/tex] ved [tex]a_1=2[/tex], [tex]a_k=2^{a_{k-1}}[/tex] .

Vis at [tex]a_{n-1} \equiv a_n \pmod n[/tex] .

Tror dette skal være riktig:

Definer [tex]\phi_2[/tex] slik: [tex]\phi_2(2^kr)=\phi(r)[/tex] hvis [tex]r[/tex] er odde. Den er veldefinert siden [tex]2^kr[/tex] der [tex]r[/tex] er odde er en unik representasjon.

Skriv t på formen [tex]2^kr[/tex] og anta n > 2. Da har vi at
[tex]a_n \equiv a_{n-1} \pmod{2^kr} \Leftrightarrow 2^{2^{a_{n-2}}} \equiv 2^{a_{n-2}} \pmod{2^kr} \Leftrightarrow 2^{2^{a_{n-2}}-k} \equiv 2^{a_{n-2}-k} \pmod{r} \\ \Leftrightarrow 2^{2^{a_{n-2}}-k-(a_{n-2}-k)} \equiv 1 \pmod{r} \Leftrightarrow 2^{a_{n-1}-a_{n-2}} \equiv 1 \pmod{r}[/tex]
Av Eulers teorem stemmer forrige uttrykk dersom [tex]a_{n-1}-a_{n-2} \equiv 0 \pmod{\phi(r)} \Leftrightarrow a_{n-1}-a_{n-2} \equiv 0 \pmod{\phi_2(2^kr)} \Leftrightarrow a_{n-1} \equiv a_{n-2} \pmod{\phi_2(t)}[/tex].

Fortsetter vi induktivt får vi at [tex]a_{2} \equiv a_{1} \pmod{\phi_2^{(n-2)}(t)} \Rightarrow a_{n} \equiv a_{n-1} \pmod{t}[/tex]. Men [tex]\phi_2(x) \leq x-1[/tex], så [tex]\phi_2^{(n-2)}(n) \leq n-(n-2) = 2[/tex], og siden [tex]a_2 \equiv a_1 \pmod{s}[/tex] for s = 1 og 2, har vi at [tex]a_{n} \equiv a_{n-1} \pmod{n}[/tex]. For n = 2 stemmer selvagt uttrykket.

Dette ser bra ut.

Oppfølger: Vis at en sterkere konklusjon holder - dvs at [tex]a_{n+1} \equiv a_n \pmod k[/tex] for alle [tex]k \leq n[/tex].

Vi har at [tex]a_{n+1-r} \equiv a_{n-r} \pmod{\phi_2^{r}(k)} \Rightarrow a_{n+1} \equiv a_{n} \pmod{k}[/tex] av samme argument. Lar vi r = n-1 får vi at [tex]a_{2} \equiv a_{1} \pmod{\phi_2^{(n-1)}(k)} \Rightarrow a_{n+1} \equiv a_{n} \pmod{k}[/tex]. Men [tex]k \leq n \Rightarrow \phi_2^{(n-1)}(k) \leq \max(k-(n-1),1) = 1[/tex], så ekvivalensen følger.