Let $a, b$, and $c$ be positive integers such that $gcd(a, b) = 1$. Sequence $\{u_k\}$, is given such that $u_0 = 0$, $u_1 = 1$, and u$_{k+2} = au_{k+1} + bu_k$ for all $k \ge 0$. Let $m$ be the least positive integer such that $c | u_m$ and $n$ be an arbitrary positive integer such that $c | u_n$. Show that $m | n$.
HIDE: PS. There was a typo in the last line, as it didn't define what n does. Wording comes from tst-2011-1.pdf from here. Correction was made according to #2Problem
Source: 2011 Indonesia TST stage 2 test 1 p4
Tags: number theory, recurrence relation, number theory with sequences, Sequence
15.12.2020 21:05
It's most probably parmenides51 wrote: ...$n$ be an arbitrary positive integer such that $c | u_n$...
20.12.2020 23:53
parmenides51 wrote: Let $a, b$, and $c$ be positive integers such that $gcd(a, b) = 1$. Sequence $\{u_k\}$, is given such that $u_0 = 0$, $u_1 = 1$, and u$_{k+2} = au_{k+1} + bu_k$ for all $k \ge 0$. Let $m$ be the least positive integer such that $c | u_m$ and $n$ be an arbitrary positive integer such that $c | u_n$. Show that $m | n$.
The property is equivalent to prove that $\gcd(u_n,u_m) = u_{\gcd(m,n)}$ We can prove by induction that \[\begin{pmatrix} u_{n+1} & bu_{n} \\ u_{n} & bu_{n-1} \end{pmatrix} = U^n\]where $U = \begin{pmatrix} a &b \\ 1 &0 \end{pmatrix}$ Note that $U$ is invertible in $\textbf{Z}/u_n\textbf{Z}$ and $U^{-1} = 1/b\begin{pmatrix} 0 &-b \\ -1 &a \end{pmatrix}$ where $1/b$ is an element in $\textbf{Z}/u_n\textbf{Z}$ satisfying $1/b.b =1\mod u_n$ this element exist because by induction it's easy to show $\gcd(b,u_n) = 1 \quad \forall n > 0$ from the first claim we can see that $U^n$ is diagonal in $\textbf{Z}/u_n\textbf{Z}$ this implies that $(U^n)^k$ is also diagonal in $\textbf{Z}/u_n\textbf{Z}$ from this follows that $u_n \mid u_{kn} \quad \forall k$ and consequently $ u_{\gcd(m,n)} \mid \gcd(u_n,u_m) $. The other way round follows from the fact $U^{\gcd(m,n)} = (U^{m})^{s} \times (U^{n})^{t}$ for some $t,s$ as $U^m$ and $U^n$ are diagonal in $\textbf{Z}/ \gcd(u_n,u_m)\textbf{Z}$ so is $U^{\gcd(m,n)}$ which proves that $ \gcd(u_n,u_m) \mid u_{\gcd(m,n)}$ as desired.
28.12.2021 19:26
NICE ONE!