1
$\begingroup$

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!

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

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.

$\endgroup$
3
$\begingroup$

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$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.