6 a) The general formula of The sequence : $x_{n}=(\frac{1+\sqrt{5}}{2})^{n}+(\frac{1-\sqrt{5}}{2})^{n}=a^{n}+b^{n}$ với $\left\{\begin{matrix}a=\frac{1+\sqrt{5}}{2} & \\b=\frac{1-\sqrt{5}}{2} & \end{matrix}\right.$ It is easy to prove that the sequence $x_{n}$ is integer. $=> a^{n}+b^{n}$ is integer. We use the following lemma: $a^{n}+b^{n}$ is integer $\forall n\in \mathbb{N}$, c is odd $=> a^{c}+b^{c}\vdots a+b$ Prove: Using factor $a^{n}+b^{n}=(a+b)...$ Returning to the problem, we use disproof. Assume that $x_{n}$ is prime but n is composite number which has odd , suppose n=x.y, in that x is odd $=> x_{n}=(a^{y})^{x}+(b^{y})^{x}\vdots a^{y}+b^{y}$ $=> x_{n}$ is composite number (it constrast with supposition) => E.Q.D. b) The sentence b is the property of the sequence Lucas.

Duy_Thai2002 wrote: We use the following lemma: $a^{n}+b^{n}$ is integer $\forall n\in \mathbb{N}$, c is odd $=> a^{c}+b^{c}\vdots a+b$ Prove: Using factor $a^{n}+b^{n}=(a+b)...$ Proving that lemma is not that easy. Only factorising is not sufficient. Duy_Thai2002 wrote: b) The sentence b is the property of the sequence Lucas. Also please elaborate. Clearly $(x_n)$ is already Lucas sequence.

My solution:

Attachments:

kahliipreyta wrote: My solution: If you have time, please translate your solution

a) The general formula of the sequence is: $x_n=a^n+b^n$ , with $a=\frac{1+\sqrt5}{2}$ and $b=\frac{1-\sqrt5}{2}$. If n has some odd divisor m distinct from 1 and itself, $x_\frac{n}{m}= a^\frac{n}{m}+b^\frac{n}{m} | a^n+b^n=x_n$, this means $x_n$ cannot be a prime number, as $x_\frac{n}{m}>1$ if $n>m$. b)Let $F_n$ be the fibonacci sequence ($F_0=0, F_1=1$ and $F_{n+2}= F_{n+1} + F_{n}$). Lets prove some relations between $F_n$ and $x_n$. First Lemma: $x_{n+m}= x_{n-1}F_{m} + x_{n}F_{m+1}$. Proof: If $m=1,2$ this identity holds. Inducting on m gives us $x_{n+m+2}=x_{n+m+1}+x_{n+m}=(x_{n-1}F_{m+1}+x_{n}F_{m+2}) + (x_{n-1}F_{m} + x_{n}F_{m+1})= x_{n-1}F_{m+2} + x_nF_{m+3}$, as we wanted. Second Lemma: $x_t=F_{t+1}+F_{t-1}$. Proof: Trivial induction. Third Lemma: $\gcd(F_n,F_m)=F_{\gcd(n,m)}$. Proof: Simmilar to the First Lemma, the following identity holds:$F_{n+m}= F_{n-1}F_{m} + F_{n}F_{m+1} $, then, if $d | F_{n+m}$ and $d|F_n$, then $d|F_m$, and by doing repeatedly, the euclidian algorithm happends on the index of the fibonaccis, giving the desired result. Fourth Lemma: $F_{2n}=F_{n}x_n$. Proof: $F_{n} =\frac{a^n - b^n}{\sqrt{5}}$, by multipliying $x_n,F_n$ with their general formula, we get the desired result. Now we return to the original problem. We claim the only answers are $(0,3k), (1,k)$ and $(n,(2k+1)n)$. As $n=0,1$ is easy to check, let's suppose $n>1$. Let's suppose there exists a pair $(n,m)$ for which $n$ does not divide $m$. By the Fourth Lemma $x_n| x_m| F_{2m}$ and $x_n|F_{2n}$, that means by the Third Lemma, $x_n| F_{2\gcd(n,m)}$, but $x_n>F_{n+1}>F_{2\gcd(n,m)}$, as $\gcd(n,m)\leq\frac{n}{2}$, absurd. Now we have that for all pairs $(t,s), t>1$, satisfying $x_t|x_s$, $s=kt$ for some integer $k$. By the First Lemma with $n=t, m=(k-1)t$ : $x_{kt}=x_{t-1}F_{(k-1)t}+x_{t}F_{(k-1)t +1}$, then, as $x_{t}|x_s$, $x_t|F_{(k-1)t}$, but $x_t|F_{2t}$ then $x_t|F_{t\gcd(2,k-1)}$, which gives us, as by the second lemma $x_t>F_{t+1}$, $2|k-1$, then k must be odd, giving the desired result.