Let $a_0$ be a positive integer and $a_n=5a_{n-1}+4$ for all $n\ge 1$. Can $a_0$ be chosen so that $a_{54}$ is a multiple of $2013$?
Problem
Source: 2013 Baltic Way, Problem 19
Tags: algebra, polynomial, modular arithmetic, number theory unsolved, number theory
31.12.2013 07:23
$a_n = 5a_{n-1}+4$ and $a_{n+1} = 5a_{n}+4$ so subtraction gives $a_{n+1} = 6a_n-5a_{n-1}$. Then the characteristic polynomial is $x^2-6x+5$ so $a_n = c_1+c_25^n$ for constants $c_1, c_2$. Then $a_{54} = c_1+c_25^{54} \equiv c_1+1681c_2 \pmod {2013}$. Now $c_0 = c_1+c_2 \equiv k \pmod {2013} \implies c_1 \equiv k-c_2$. Then this forces $1680$ to have an inverse $\pmod {2013}$ which is absurd since $\gcd(1680, 2013) = 3$, so not possible.
31.12.2013 08:00
$a_n=5^n(a_0+1)-1=2013k$ for some $k\in\mathbb Z$ is always possible since $5^n$ and $2013$ are coprime.
04.01.2014 22:00
ssilwa wrote: Then $a_{54} = c_1+c_25^{54} \equiv c_1+1681c_2 \pmod {2013}$. Now $c_0 = c_1+c_2 \equiv k \pmod {2013} \implies c_1 \equiv k-c_2$. Then this forces $1680$ to have an inverse $\pmod {2013}$ which is absurd since $\gcd(1680, 2013) = 3$, so not possible. $c_1, c_2$ need not be integers though.
06.01.2014 16:49
mathisfun7 wrote: Let $a_0$ be a positive integer and $a_n=5a_{n-1}+4$ for all $n\ge 1$. Can $a_0$ be chosen so that $a_{54}$ is a multiple of $2013$? $a_{54}=5^{54}(a_0+1)-1$. from Euler`s theorem we have $5^{1200}\equiv 1\pmod {2013}$. By setting $a_0=5^{1146}-1$ we get that $a_{54}$ is divisible by 2013
07.01.2014 12:04
$a_{54}=5^{54}(a_0+1)-1$ In fact $\gcd(5^{54},2013)=1$,From Bezout Theorem,we pick $x,y\in\mathbb{Z}$ such that $5^{54}x-2013y=1$ Let $a_0=x-1$ we get $2013|a_{54}$
16.08.2021 02:04
Answer. Any positive $a_0$ satisfying $a_0\equiv -\dfrac{5^{54}-1}{5^{54}}\pmod{2013}$ works. The whole problem is just definitions of Chinese reminder theorem and inverse modulo, essentially. Note that if $a_k\equiv -\dfrac{5^{54-k}-1}{5^{54-k}}\pmod{2013}$, then \begin{align*} a_{k+1}=5a_k+4\equiv \dfrac{1-5^{54-k}}{5^{54-(k+1)}}+4\\\equiv \dfrac{1-5^{54-k}+4\cdot 5^{54-(k+1)}}{5^{54-(k+1)}}\equiv -\dfrac{5^{54-(k+1)}-1}{5^{54-(k+1)}}\pmod{2013}, \end{align*}this implies that $a_{54}\equiv 0\pmod{2013}$.