Proof $13 \mid (k\cdot 2^n+1)$ if $n\equiv2 \pmod{12}$ and $k\equiv3 \pmod{13}$?

Question

Proof $13 \mid (k \cdot 2^n + 1)$ if $n\equiv2 \pmod{12}$ and $k\equiv3 \pmod{13}$

Hint: for $k$ odd: $2^n \equiv-k' \pmod p$ and $kk' \equiv1 \pmod p$

My thoughts:

$13\mid(k-3) \Rightarrow k=13a+3$

and

$12|(n-2) \Rightarrow n=12b+2$

so

$\begin{align}k\cdot 2^n+1 &=(13a+3)2^{12b+2}+1 \\ &=4(13a+3)(2^{b})^{12}+1\\ \textrm{ or } &=(k-3+3)\cdot 2^{n-2+2}+1\\ &=4\cdot 2^{n-2}(k-3+3)+1\\ &=4\cdot 2^{n-2}(k-3)+3\cdot2^n+1\end{align}$

I don't kow how to use the hint :(

Answer 1

${\rm mod}\ 13\!:\!\! \overbrace{\color{#c00}{ 2^{\large n}}\!\equiv 2^{\large 2+12j}}^{\large\quad\ \ \color{#c00}n\ \equiv\ 2\pmod{\!12}}\!\!\!\!\!\!\!\equiv 2^{\large 2}\color{#0a0}{(2^{\large 12})}^{\large j}\!\equiv 4\color{#0a0}{(1)}^{\large j}\!\equiv \color{#c00}4\,\ $ by $\ \rm\color{#0a0}{ Fermat}$

therefore $\ k\equiv 3\,\Rightarrow\, k\,\color{#c00}{2^{\large n}}\!+1\equiv 3\cdot \color{#c00}4+1\equiv 0\pmod{13}$

Answer 2

If $n=12N+2$ and $k=13K+3$ then $$ k2^n+1=13K2^n+3\cdot 4\cdot \left(\underbrace{2^{12}}_{\equiv 1\bmod{13}}\right)^{N}+1. $$

Answer 3

By Fermat we have $2^{12} \equiv 1 \pmod{13}$ so $2^{12b}=1+13c$.

So \begin{eqnarray*} k2^n+1=(3+13a)(4+4 \times 13 c)+1=13(1+4a+12c+52ac) \end{eqnarray*}