Proving that $19\mid 5^{2n+1}+3^{n+2} \cdot 2^{n-1}$

Question

How can I prove that $$5^{2n+1}+3^{n+2} \cdot 2^{n-1} $$ can be divided by 19 for any nonnegative n? What modulo should I choose?

Answer 1

You can prove this by induction.

---

First, show that this is true for $n=1$:

$5^{2\cdot1+1}+3^{1+2}\cdot2^{1-1}=19\cdot8$

Second, assume that this is true for $n$:

$5^{2n+1}+3^{n+2}\cdot2^{n-1}=19k$

Third, prove that this is true for $n+1$:

$5^{2(n+1)+1}+3^{n+1+2}\cdot2^{n+1-1}=$

$5^{2+2n+1}+3^{1+n+2}\cdot2^{1+n-1}=$

$5^{2}\cdot5^{2n+1}+3^{1}\cdot3^{n+2}\cdot2^{1}\cdot2^{n-1}=$

$5^{2}\cdot5^{2n+1}+3^{1}\cdot2^{1}\cdot3^{n+2}\cdot2^{n-1}=$

$25\cdot5^{2n+1}+\color\green{6}\cdot3^{n+2}\cdot2^{n-1}=$

$25\cdot5^{2n+1}+(\color\green{25-19})\cdot3^{n+2}\cdot2^{n-1}=$

$25\cdot5^{2n+1}+25\cdot3^{n+2}\cdot2^{n-1}-19\cdot3^{n+2}\cdot2^{n-1}=$

$25\cdot(\color\red{5^{2n+1}+3^{n+2}\cdot2^{n-1}})-19\cdot3^{n+2}\cdot2^{n-1}=$

$25\cdot\color\red{19k}-19\cdot3^{n+2}\cdot2^{n-1}=$

$19\cdot25k-19\cdot3^{n+2}\cdot2^{n-1}=$

$19\cdot(25k-3^{n+2}\cdot2^{n-1})$

---

Please note that the assumption is used only in the part marked red.

Answer 2

Denote $\mathcal{P}(n)$ the statement that $5^{2n+1} + 3^{n+2}\cdot 2^{n-1}$ is divisible by $19$. You can check for yourself that $\mathcal{P}(1)$ is true. A setup for the proof of $\mathcal{P}(n+1)$:

\begin{align} 5^{2(n+1)+1} + 3^{(n+1)+2}\cdot 2^{(n+1)-1} & = \\ 25 \times 5^{2n+1} + 6 \times 3^{n+2}\cdot 2^{n-1} & = \\ 19 \times 5^{2n+1} + 6 \times 5^{2n+1} + 6 \times 3^{n+2}\cdot 2^{n-1} & = \cdots \end{align} can you finish the proof from here?

Answer 3

$5^{2n+1} = 5 \times 25^n \equiv 5 \times 6^n$ (modulo 19). Hence we have $5^{2n+1} + 3^{n+2}\times2^{n-1} \equiv 6^{n-1} \times (30 + 27) = 6^{n-1}\times3\times 19$ (modulo 19)

Answer 4

$2^{n-1} = \frac12 2^n \equiv 10 \cdot 2^n \pmod {19}$. Hence:

$5^{2n+1} +3^{n+2} \cdot 2^{n-1} \equiv 5 \cdot 6^n + 90 \cdot 6^n \pmod {19} \equiv 95 \cdot 6^n \pmod {19} \equiv 0 \pmod {19}$

Answer 5

For $n=0$, the formula says that $\left.19\middle|\frac{19}2\right.$, which is false. So consider $n\ge1$: $$ \begin{align} 5^{2n+1}+3^{n+2}2^{n-1} &=125\cdot25^{n-1}+27\cdot6^{n-1}\\ &\equiv11\cdot6^{n-1}+8\cdot6^{n-1}&\pmod{19}\\ &=19\cdot6^{n-1}\\ &\equiv0&\pmod{19} \end{align} $$ Since $$ \begin{align} 125&\equiv11&\pmod{19}\\ 25&\equiv6&\pmod{19}\\ 27&\equiv8&\pmod{19} \end{align} $$

Answer 6

Its arithmetical essence is clarified using Congruence Product and Power Rules, namely

$$\begin{align}{\rm mod}\,\ 19\!:\qquad \big[\,\ 5^{\large\color{#c00}1} \ &\equiv\, -3^{\large\color{#c00} 2}\ \cdot\, 2^{\large\color{#c00}{-1}}\big]\ \ \ {\rm by}\ \ \ \ \,2\cdot 5\equiv -3^{\large 2}\\ \times\ \ \, \big[\, 5^{\large 2n} &\equiv\ \ \ 3^{\large n}\,\cdot\, 2^{\large n}\ \ \ \big]\ \ \ {\rm by} \ \ \Big[\,5^{\large 2}\equiv 3\cdot 2\,\Big]^{\large n}\\[.1em] \Rightarrow\,\ 5^{\large 2n+\color{#c00}1}\!&\equiv -3^{\large n+\color{#c00}2} 2^{\large n\color{#c00}{-1}} \end{align}\qquad\qquad\quad\ $$

Therefore we infer that $\ 19\mid 5^{\large 2n+1}+\ 3^{\large n+2} 2^{\large n-1}$ when it is integral, i.e. for all $\,n\ge 1$

Remark $ $ It is even clearer when written in fractional form, namely

$$ \dfrac{5^{\large 2n+1}}{3^{\large n+2}2^{\large n-1} }\ \equiv\ \left[\dfrac{2\cdot 5}{3\cdot 3}\right]\left[\dfrac{5^{\large 2}}{3\cdot 2}\right]^{\large n}\!\!\equiv\, -1\cdot 1^{\large n}\equiv\, -1$$

Notice how use of congruence language greatly simplifies the inductive step, reducing it to the trivial induction that $\,1^n\equiv 1.$