Part A For all natural integers $n$, we define the integers $a _ { n } = 6 \times 5 ^ { n } - 2$ and $b _ { n } = 3 \times 5 ^ { n } + 1$.
a. Show that, for all natural integers $n$, each of the integers $a _ { n }$ and $b _ { n }$ is congruent to 0 modulo 4. b. For all natural integers $n$, calculate $2 b _ { n } - a _ { n }$. c. Determine the GCD of $a _ { n }$ and $b _ { n }$.
a. Show that $b _ { 2020 } \equiv 3 \times 2 ^ { 2020 } + 1$ [7]. b. By noting that $2020 = 3 \times 673 + 1$, show that $b _ { 2020 }$ is divisible by 7. c. Is the integer $a _ { 2020 }$ divisible by 7? Justify your answer.
Part B We consider the sequences $\left( u _ { n } \right)$ and $\left( v _ { n } \right)$ defined by: $$u _ { 0 } = v _ { 0 } = 1 \text { and, for every natural integer } n , \left\{ \begin{array} { l }
u _ { n + 1 } = 3 u _ { n } + 4 v _ { n } \\
v _ { n + 1 } = u _ { n } + 3 v _ { n }
\end{array} \right.$$ For a given natural integer $N$, we wish to calculate the terms of rank $N$ of the sequences $(u_n)$ and $(v_n)$ and we wonder if the algorithm below allows this calculation.
\multicolumn{2}{|c|}{Algorithm}
1.
$U \leftarrow 1$
2.
$V \leftarrow 1$
3.
$K \leftarrow 0$
4.
While $K < N$
5.
$U \leftarrow 3 U + 4 V$
6.
$V \leftarrow U + 3 V$
7.
$K \leftarrow K + 1$
8.
End While
We run the algorithm with $N = 2$. Copy and complete the table below by giving the values successively assigned to the variables $U, V$ and $K$.
$U$
$V$
$K$
1
1
0
7
10
1
Does the algorithm actually allow us to calculate $u _ { N }$ and $v _ { N }$ for a given value of $N$? If not, write on your paper a corrected version of this algorithm so that the variables $U$ and $V$ contain the correct values of $u _ { N }$ and $v _ { N }$ at the end of its execution.
Part C For every natural integer $n$, we define the column matrix $X _ { n } = \binom { u _ { n } } { v _ { n } }$.
Give, without justification, a square matrix $A$ of order 2 such that, for every natural integer $n$: $$X _ { n + 1 } = A X _ { n } .$$
Show by induction that, for every natural integer $n$, we have: $X _ { n } = A ^ { n } X _ { 0 }$.
We admit that, for every natural integer $n$, $A ^ { n } = \frac { 1 } { 4 } \left( \begin{array} { c c } 2 \times 5 ^ { n } + 2 & 4 \times 5 ^ { n } - 4 \\ 5 ^ { n } - 1 & 2 \times 5 ^ { n } + 2 \end{array} \right)$. Show that, for every natural integer $n$, $u _ { n } = \frac { a _ { n } } { 4 }$ and $v _ { n } = \frac { b _ { n } } { 4 }$, where $a _ { n }$ and $b _ { n }$ are the integers defined in Part A.
Justify that, for every natural integer $n$, $u _ { n }$ and $v _ { n }$ are coprime.
\textbf{Part A}
For all natural integers $n$, we define the integers $a _ { n } = 6 \times 5 ^ { n } - 2$ and $b _ { n } = 3 \times 5 ^ { n } + 1$.
\begin{enumerate}
\item a. Show that, for all natural integers $n$, each of the integers $a _ { n }$ and $b _ { n }$ is congruent to 0 modulo 4.\\
b. For all natural integers $n$, calculate $2 b _ { n } - a _ { n }$.\\
c. Determine the GCD of $a _ { n }$ and $b _ { n }$.
\item a. Show that $b _ { 2020 } \equiv 3 \times 2 ^ { 2020 } + 1$ [7].\\
b. By noting that $2020 = 3 \times 673 + 1$, show that $b _ { 2020 }$ is divisible by 7.\\
c. Is the integer $a _ { 2020 }$ divisible by 7? Justify your answer.
\end{enumerate}
\textbf{Part B}
We consider the sequences $\left( u _ { n } \right)$ and $\left( v _ { n } \right)$ defined by:
$$u _ { 0 } = v _ { 0 } = 1 \text { and, for every natural integer } n , \left\{ \begin{array} { l }
u _ { n + 1 } = 3 u _ { n } + 4 v _ { n } \\
v _ { n + 1 } = u _ { n } + 3 v _ { n }
\end{array} \right.$$
For a given natural integer $N$, we wish to calculate the terms of rank $N$ of the sequences $(u_n)$ and $(v_n)$ and we wonder if the algorithm below allows this calculation.
\begin{center}
\begin{tabular}{ | l | l | }
\hline
\multicolumn{2}{|c|}{Algorithm} \\
\hline
1. & $U \leftarrow 1$ \\
\hline
2. & $V \leftarrow 1$ \\
\hline
3. & $K \leftarrow 0$ \\
\hline
4. & While $K < N$ \\
\hline
5. & $U \leftarrow 3 U + 4 V$ \\
\hline
6. & $V \leftarrow U + 3 V$ \\
\hline
7. & $K \leftarrow K + 1$ \\
\hline
8. & End While \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}
\item We run the algorithm with $N = 2$. Copy and complete the table below by giving the values successively assigned to the variables $U, V$ and $K$.
\begin{center}
\begin{tabular}{ | c | c | c | }
\hline
$U$ & $V$ & $K$ \\
\hline
1 & 1 & 0 \\
\hline
7 & 10 & 1 \\
\hline
& & \\
\hline
\end{tabular}
\end{center}
\item Does the algorithm actually allow us to calculate $u _ { N }$ and $v _ { N }$ for a given value of $N$? If not, write on your paper a corrected version of this algorithm so that the variables $U$ and $V$ contain the correct values of $u _ { N }$ and $v _ { N }$ at the end of its execution.
\end{enumerate}
\textbf{Part C}
For every natural integer $n$, we define the column matrix $X _ { n } = \binom { u _ { n } } { v _ { n } }$.
\begin{enumerate}
\item Give, without justification, a square matrix $A$ of order 2 such that, for every natural integer $n$:
$$X _ { n + 1 } = A X _ { n } .$$
\item Show by induction that, for every natural integer $n$, we have: $X _ { n } = A ^ { n } X _ { 0 }$.
\item We admit that, for every natural integer $n$, $A ^ { n } = \frac { 1 } { 4 } \left( \begin{array} { c c } 2 \times 5 ^ { n } + 2 & 4 \times 5 ^ { n } - 4 \\ 5 ^ { n } - 1 & 2 \times 5 ^ { n } + 2 \end{array} \right)$.
Show that, for every natural integer $n$, $u _ { n } = \frac { a _ { n } } { 4 }$ and $v _ { n } = \frac { b _ { n } } { 4 }$, where $a _ { n }$ and $b _ { n }$ are the integers defined in Part A.
\item Justify that, for every natural integer $n$, $u _ { n }$ and $v _ { n }$ are coprime.
\end{enumerate}