Prove that if $n$ is a positive odd integer then $1947\mid (46^n+296\cdot 13^n)$

Question

This is an exercise from The Kürschák Mathematics competition from the year 1947:

Prove that if $n$ is a positive odd integer then $1947\mid (46^n+296\cdot 13^n)$.

I have the solutions in the back of the book but I would like to tackle the problem myself. I don't really know how to start, any HINTS are appreciated.

Thank you!

Answer 1

Let $x_n = 46^n+296\cdot 13^n$. Let $a= 46^n$ and $b=296\cdot 13^n$.

Then $x_{n} = a + b$ and $x_{n+2} = 46^2 a + 13^2b$.

Now $46^2 \equiv 169 = 13^2 \bmod 1947$ and so $x_{n+2} \equiv 169(a+b) = 169x_n \equiv 0 \bmod 1947$ by induction.

Answer 2

Hint. Note that $46^2-13^2=(46+13)(46-13)=59\cdot 33=1947$ and $$46^{2n+1}+296\cdot 13^{2n+1}=46^2\cdot 46^{2n-1}+296\cdot 13^2\cdot 13^{2n-1} \\=13^2(46^{2n-1}+296\cdot 13^{2n-1})+(46^2-13^2)\cdot 46^n$$

Answer 3

Note that $$ \begin{cases} 46\equiv 1(\mod 3)\\ 46\equiv 2(\mod 11)\\ 46\equiv -13(\mod 59) \end{cases} \ \text{and}\ \begin{cases} 296\equiv -1(\mod 3)\\ 296\equiv -1(\mod 11)\\ 296\equiv 1(\mod 59) \end{cases} \ \text{and}\ \begin{cases} 13\equiv 1(\mod 3)\\ 13\equiv 2(\mod 11)\\ 13\equiv 13(\mod 59) \end{cases} $$ Hence $$ 46^n+296\cdot 13^n\equiv 1+(-1)\cdot 1=0(\mod{3}) $$ $$ 46^n+296\cdot 13^n\equiv 2^n+(-1)\cdot 2^n=0(\mod{11}) $$ and $$ 46^n+296\cdot 13^n\equiv (-13)^n+1\cdot 13^n=0(\mod{59}) $$ Thus $$ \begin{cases} 46^n+296\cdot 13^n\equiv0(\mod{3})\\ 46^n+296\cdot 13^n\equiv0(\mod{11})\\ 46^n+296\cdot 13^n\equiv0(\mod{59})\\ \end{cases} $$ Since $1947=3\cdot 11\cdot 59$, then $$ 46^n+296\cdot 13^n\equiv0(\mod{1947}) $$

Answer 4

Because for $n=1$ it's true and for all odd $n\geq3$ we obtain: $$46^n+296\cdot13^n=46\cdot46^{n-1}-46\cdot13^{n-1}+(46+296\cdot13)13^{n-1}=$$ $$=46\cdot(46^2-13^2)\left(46^{\frac{n-1}{2}-1}+...+13^{\frac{n-1}{2}-1}\right)+2\cdot1947\cdot13^{n-1}=$$ $$=1947\left(46\left(46^{\frac{n-1}{2}-1}+...+13^{\frac{n-1}{2}-1}\right)+2\cdot\cdot13^{n-1}\right).$$