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

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!

• Hint: $1947=3\cdot 11 \cdot 59$. – Batominovski Nov 10 '17 at 8:45

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.
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$$
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})$$
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).$$