For the first part, it's easy to see that it suffices to show the following: given a prime $p$ and a sequence $x_n,n\ge 0$ of residues $\pmod p$ s.t. $x_0=0,x_1=1$, show that there is some $n>0$ s.t. $x_0=0$. This can be shown as follows: assume there are nu such $n$. The sequence becomes periodic from some point onwards, so we can find $m<n$ s.t. $x_m=x_n,x_{m+1}=x_{n+1}$. Now start from $x_{n+1}$ downwards with the recurrence formula $x_t=\frac{x_{t+2}-1}{x_t}$ (where $\frac 1{x^t}$ is the inverse of $x_t\ne 0\pmod p$). Since $x_{m+1}=x_{n+1}$ and $x_m=x_n$, the portion between $x_m$ and $x_n$ is repeated indefinitely, and since it does not contain $0$, we can't reach $0$ by this procedure. However, we must reach $0$ when we reach $x_0$, so we have a contradiction. As for the second part, take $a_1=22,a_2=15$ (I need $a_2$ to be odd and $6\pmod 11$). $2|a_n$ iff $3|n$, while $11|a_n$ iff $n\equiv 10\pmod 6$.

Approach by dblues: Let $ m > 1$ and $ p$ be a prime divisor of $ a_m$. Define $ \{ u_k \}$ by $ u_k \equiv a_k \pmod{p}$ such that $ 0 \leq u_k \leq p - 1$. Thus, we have $ u_{k + 2} \equiv u_{k + 1}u_k + 1 \pmod{p}$. We note that $ u_m = 0$. Since there are only finitely many distinct pairs $ (u_k, u_{k + 1})$, $ \{ u_k \}$ is eventually periodic. Lemma: $ \exists \ k_p > 0$ such that $ u_{m + k_p} = 0$. Suppose not, then $ \{ u_k \}$ is purely periodic from $ u_r$ for some $ r > m$. (Note that inequality is strict, since otherwise, letting $ d_p$ be the length of this period, we have $ u_{m + d_p} = 0$, implying that we have $ k_p = d_p$ as required, which contradicts our original assumption that no such $ k_p$ exists.) Thus we have $ (u_r, u_{r + 1}, \ldots , u_{r + d_p - 1})$ and $ (u_{r + d_p}, u_{r + d_p + 1}, \ldots , u_{r + 2d_p - 1})$ as the first two periods. Note that $ u_ru_{r - 1} \equiv u_{r + 1} - 1 = u_{r + d_p + 1} - 1 \equiv u_{r + d_p - 1}u_{r + d_p} \pmod{p}$. $ \Rightarrow u_{r - 1} = u_{r + d_p - 1}$, since $ u_r = u_{r + d_p} \not\equiv 0 \pmod{p}$ (by our assumption). This contradicts the fact that $ (u_r, u_{r + 1}, \ldots , u_{r + d_p - 1})$ and $ (u_{r + d_p}, u_{r + d_p + 1}, \ldots , u_{r + 2d_p - 1})$ are the first two periods, thus our assertion must be true. Note that from the above lemma, $ u_m = u_{m + k_p} = 0 \Rightarrow u_{m + 1} = 1 = u_{m + k_p + 1} \Rightarrow \{u_k \}$ is purely periodic from $ u_m$. Denote $ q$ to be the least common multiple of all $ k_p$ corresponding to all the distinct prime divisors $ p$ of $ a_m$. We thus have $ a_{m + tq}$ is divisible by each of these primes $ \forall t \in \mathbb{Z}^ +$. Let $ e_m$ be the highest exponent of all the primes in the prime factorisation of $ a_m$. Choosing a sufficiently large $ t$ such that $ n = m + tq > me_m$, we have $ {a_m}^m \mid {a_n}^n$ as desired. As for the second part of the problem, this is not necessarily true. The argument breaks down when $ m = 1$ because it is not necessarily true that $ u_{m + 1} = u_2 = 1$, due to the fact that $ u_0$ is not defined in the recurrence $ u_{k + 2} = u_{k + 1}u_k + 1$. Thus, $ \{ u_k \}$ is not necessarily purely periodic from $ u_m$. As an example, we let $ a_1 = 33, a_2 = 20$. Taking $ p = 3$, we have for $ n > 1, 3 \mid a_n$ iff $ n \equiv 0 \pmod{4}$, while taking $ p = 11$, we have for $ n > 1, 11 \mid a_n$ iff $ n \equiv 5 \pmod{6}$. Note that both conditions cannot be achieved simultaneously as the first condition implies $ n$ is even, while the second condition implies $ n$ is odd. Thus $ a_1 \nmid a_n \forall n > 1$ and we are done.

Pascual2005 wrote: Define the sequence $ a_1, a_2, a_3, ...$ as follows. $ a_1$ and $ a_2$ are coprime positive integers and $ a_{n + 2} = a_{n + 1}a_n + 1$. Show that for every $ m > 1$ there is an $ n > m$ such that $ a_m^m$ divides $ a_n^n$. Is it true that $ a_1$ must divide $ a_n^n$ for some $ n > 1$? See http://www.mathlinks.ro/viewtopic.php?t=150805

Here is my solution for the first part. Define a sequence $\{ x_n \}$ such that $x_1=x_2=1, x_{n+1}=x_{n}x_{n-1}+1$. We have $x_{n+1} \equiv x_1 \pmod{x_n}, x_{n+2} \equiv x_2 \pmod{x_n}, x_{n+3} \equiv x_3 \pmod{x_n}$. Eventually, $x_{2n} \equiv x_n \pmod{x_n}$ or $x_n \mid x_{2n}$. It is not hard to prove that $x_a \mid x_{ab}$ and $x_{ab+k} \equiv x_k \pmod{x_{a}}$. Note that $a_{m+1} \equiv x_1 \pmod{a_m}, a_{m+2} \equiv x_2 \pmod{a_m}, ...$ Eventually, $a_{m+k} \equiv x_k \pmod{a_m}$. From this, my idea is to prove that for every prime divisor $p$ of $a_m$, there exist $x_k$ such that $p \mid x_k$. Indeed, for any prime $p$, in sequence $\{ x_n \}$, there are infinitely many $i$ such that $x_i \equiv t \pmod{p}$ for some $1 \le t \le p-1$ (otherwise $\{ x_n \}$ will be not a infinite sequence). For such $x_i$, we consider $x_{i-1}$. There will exist $2<k<l$ such that $x_k \equiv x_l \equiv t \pmod{p}$ and $x_{k-1} \equiv x_{l-1} \pmod{p}$ (otherwise if $x_{k-1} \not\equiv x_{l-1} \pmod{p}$ for every $k,l$ then there won't exist infinitely number $x_i$). If we know $x_k,x_{k-1} \pmod{p}$, we can determine $x_{k-2},x_{k-3}, \cdots x_2,x_1 \pmod{p}$. Similarly to $x_l,x_{l-1}$. Since $x_2 \equiv x_1 \equiv 1 \pmod{p}$ so eventually, there will exist $x_{h} \equiv x_{h-1} \equiv 1 \pmod{p}$ for $h>2$. This implies that $p \mid x_{h-2}$. Back to our sequence $\{ a_n \}$, we consider every prime divisor $p_i \; (1 \le i \le k)$ of $a_m$. According to the proof above, there exist $b_i$ such that $p_i \mid x_{b_i}$. Therefore, $\prod_{i=1}^k p_i \mid x_{b_1b_2 \cdots b_k}=x_l$. Thus, $a_{m+lk} \equiv x_{lk} \pmod{a_m}$. This prove that every prime divisor of $a_m$ is also a prime divisor of $a_{m+lk}$. We can find $l_0$ large enough such that $m v_p \left( a_m \right) \le (m+l_0k) v_p \left( a_{m+l_0k} \right)$ for every $p \mid a_m$. Thus, this follows $a_m^m \mid a_{m+l_0k}^{m+l_0k}$ or $a_m^m \mid a_n^n$. $\blacksquare$

For the first part, we only need to show that $a_i$ modular $p$ is purely periodic starting at $i$, for all prime $p|a_i$. Then, taking a large $N$ which divides all such periods of all such primes, we can see that $a^i_i$ is a divisor of $a^{i+N}_{i+N}$. To prove this, we will look at the structure $f(a,b)=(b,ab+1)$. (in mod $p$, of course) Since $i>1$, we know that $a_{i+1} \equiv 1 \pmod{p}$. So we are starting at $(0,1)$. Denote $T_n= f^n (0,1)$. By PHP, we will have $T_n = T_m$ for some $0 \le n < m$. Take one pair with minimum $n+m$. I claim that $n=0$. Assume otherwise - $n \ge 1$. Note that $T_m$ is not $(0,1)$. Otherwise, we can take $n=0$. Now since $T_m \neq (0,1)$, $f^{-1} (T_m)$ exists, and it is unique. (this is the key to this problem) So if $T_m \neq T_0$ and $n \neq 0$, $T_{m-1}=T_{n-1}$ and we have a contradiction. This shows that there is a cycle. For Part 2, now we know that starting with stuff like $(0,2)$ may lead us into problems. Use that to form a construction.

Pascual2005 wrote: Define the sequence $ a_1, a_2, a_3, ...$ as follows. $ a_1$ and $ a_2$ are coprime positive integers and $ a_{n + 2} = a_{n + 1}a_n + 1$. Show that for every $ m > 1$ there is an $ n > m$ such that $ a_m^m$ divides $ a_n^n$. Is it true that $ a_1$ must divide $ a_n^n$ for some $ n > 1$? The answer is $\boxed{\text{Yes}}$ for $\textit{a)}$ and $\boxed{\text{No}}$ for $\textit{b)}$ $\textit{a)}$Define a sequence $x_i$ of integers satisfying $\;\;\;\;\;\;\; \bullet$ $x_i \equiv a_i \pmod {p^C}$ where $p|a_m$ and $C\ge m\nu_p(a_m)$ $\;\;\;\;\;\;\; \bullet$ $x_i =x_{i-1} x_{i-2}+1$ and $0=x_0 \equiv x_m \equiv x_{2m} .................. \equiv x_{km} \pmod {p^C}$ Define $i_j$ as $$\underbrace{x_m}_{i_0=0},\underbrace{x_1}_{i_1=1}.................$$Lemma #1:- $i_{mk+t} \equiv i_t \pmod {p^C}$ This trivally follows from the second $\bullet$ from which we obtain both $x_j$ and $i_j$ periodic. The result follows from choosing $n=m^{k \nu_p(m)} $ of which there are clearly infinitely many.

Solved with elcinmusazade. First part: Let $p_1,p_2,\ldots p_s$ be all prime divisors of $a_m$. Now let's look at $a_m,a_{m+1},...$ in $\pmod{p_1}$. We will get sequence $x_1,x_2,x_3,...$ where $x_1=0,x_2=1$. It's obvious that $(x_i)_{i\geq 1}$ is finally periodic starting from some point. Let's assume that this point is $x_j$ where $x_j\ne x_1=0$. So we will get the sequence like this $$x_1,x_2,...,x_j,x_{j+1},...x_r,x_j,x_{j+1},...$$So we get that $x_j\cdot x_{j-1}+1\equiv x_{j+1}\equiv x_j\cdot x_r+1 \implies p_1\mid x_j\cdot (x_r-x_{j-1})$. Since $x_j\not\equiv x_1\pmod{p_1}$ we get $x_r\equiv x_{j-1}\pmod{p_1}$, but then we get that period starts from $x_{j-1}$, not from $x_j$, which is contradiction. So $x_j=x_1=0$ and $x_{j+1}=x_2=1$. So $(x_i)_{i\geq 1}$ is periodic starting from $x_1$. Let $r_1$ be the length of this period. Then we get that $x_{tr_1+1}=0$ for all $t\in \mathbb{N}_0$, so $p_1\mid a_{tr_1+m}$ for all $t\in \mathbb{N}_0$ Similarly define $r_2,r_3,...,r_s$ according to $p_2,p_3,...,p_s$. So $p_i\mid a_{tr_i+m}$ for all $t\in \mathbb{N}_0$ and for all $i=1,2,...,s$. Now choose $n=Tr_1r_2\cdots r_s+m$ where $T$ is very large that $n=Tr_1r_2\cdots r_s+m>max\{m\cdot v_{p_1}(m),..., m\cdot v_{p_s}(m)\}$. And this gives that $n\cdot v_{p_i}(n)\geq n>m\cdot v_{p_i}(m)$ for all $i=1,2,...,s$. So we get that $a_m^m\mid a_n^n$ as desired. Second part: The answer is negative. Choose $a_1=33,a_2=31$. Now lets look at residues $a_i$ gives in $\pmod{3}$ over all $n$. We get sequence $0,2,1,0,1,1,2,0,1,1,2,...$ We get that sequence has period starting from $4$th term. So $3\mid a_i\iff 4\mid i$ or $i=1$. Now lets look at residues $a_i$ gives in $\pmod{11}$ over all $n$. We get sequence $0,9,1,10,0,1,1,2,3,7,0,1,1,....$ We get that sequence has period starting from $5$th term. So $11\mid a_i\iff i\equiv 5\pmod{6}$ or $i=1$. If there is $a_i$ which is divisible by $33$, then$4\mid i$ and $i\equiv 5\pmod{6}$, so $i$ is both odd and even, which is contradiction. So there is no $a_i$ which is divisible by $a_1=33$. So there is no $n>1$ such that $a_1\mid a_n^n$. So we are done!!!