Suppose that $m \ge 0$ show that $49 \mid 5\cdot3^{4m + 2} + 53\cdot2^{5m}$

Question

I've re-written the equation in a few different ways hoping for a few different approaches:

$$49y = 5 \cdot 3^{4m + 2} + 53 \cdot 2^{5m} $$

I think the first equation has more potential, since it looks like I should be able to just solve for $m$, or get to a point where I can say that any positive $m$ will work, but there doesn't seem to be an easy way to proceed to solve for $m$.

or

$5\cdot3^{4m + 2} + 53 \cdot 2^{5m} \equiv 0 \mod 49$ I'm not fabulous at congruence equations, but I was thinking I could reduce this down to something more manageable to solve the problem, but none of my congruence equation tricks really help.

Anyways I'm at a loss as to where to proceed, if you all have any tips on ways to proceed, that'd be great :D

Answer 1

\begin{align*} 5\cdot 3^{4(m + 1) + 2} + 53 \cdot 2^{5(m + 1)} &= 5 \cdot 3^{4m + 2} \cdot 3^4 + 53 \cdot 2^{5m} \cdot 2^5 \\ &= 81 \cdot \Big(5\cdot 3^{4m + 2}\Big) + 32 \cdot \Big(53 \cdot 2^{5m}\Big) \\ &= (49 + 32) \cdot\Big(5\cdot 3^{4m + 2}\Big) + 32 \cdot \Big(53 \cdot 2^m\Big) \\ &= 49 \cdot \Big(5 \cdot 3^{4m + 2}\Big) + 32 \cdot\Big(5 \cdot 3^{4m + 2} + 53 \cdot 2^m\Big) \end{align*}

Can you finish from here?

Answer 2

Work modulo $49$. Note that the first term is $45\cdot 81^m$, which is congruent to $45\cdot 32^m$.

The second term is congruent, indeed equal, to $53\cdot 32^m$.

Altogether, $98\cdot 32^m$. Finished!

Answer 3

Note that $$ 5\times 3^{4m + 2} + 53\times 2^{5m} = (49 -4)81^m + (49 + 4)32^m = 49\times(81^m + 32^m) - 4\times (81^m - 32^m) $$ But, $$ 81^m - 32^m = (49 + 32)^m - 32^m = \sum_{k=1}^{m - 1}{m \choose k}32^k 49^{m-k} = 49N $$ Thus, $5\times 3^{4m + 2} + 53\times 2^{5m} = 49\times(81^m + 32^m) - 49N = 49M$

Answer 4

Observe that \begin{align*} 2^{5} & \equiv 32 \pmod{49}\\ 2^{5m} & \equiv 32^m \pmod{49}\\ 53 \cdot 2^{5m} & \equiv 53 \cdot 32^m \equiv 4 \cdot 32^m \pmod{49} \end{align*} Likewise \begin{align*} 3^{4} & \equiv 81 \equiv 32 \pmod{49}\\ 3^{4m} & \equiv 32^m \pmod{49}\\ 3^{4m+2} & \equiv 32^m \cdot 9 \pmod{49}\\ 5 \cdot 3^{4m+2} & \equiv 32^m \cdot 45 \equiv 32^m \cdot (-4) \pmod{49}\\ \end{align*} Now add the last two congruences of both systems to get $$53 \cdot 2^{5m} + 5 \cdot 3^{4m+2} \equiv 4 \cdot 32^m + 32^m \cdot (-4) \equiv 0\pmod{49}$$

Answer 5

We will prove by induction on $m \geq 0$ that:

There is some $y \in \mathbb Z$ such that $49y = 5 \cdot 3^{4m + 2} + 53 \cdot 2^{5m}$.

Base Case: This holds for $m = 0$, since we can take $y = 2$.

Induction Hypothesis: Assume that the claim holds for $m' = m - 1$, where $m \geq 1$.

It remains to show that the claim holds for $m' = m$. Now by the induction hypothesis, we know that there is some $z \in \mathbb Z$ such that: $$ 49z = 5 \cdot 3^{4m - 2} + 53 \cdot 2^{5m - 5} \tag{1} $$

But then observe that: \begin{align*} 5 \cdot 3^{4m + 2} + 53 \cdot 2^{5m} &= (3^4)(5 \cdot 3^{4m - 2}) + 53 \cdot 2^{5m} \\ &= (3^4)(49z - 53 \cdot 2^{5m - 5}) + 53 \cdot 2^{5m} &\text{by }(1)\\ &= 49(81z) - 53 \cdot 2^{5m - 5} \cdot 81 + 53 \cdot 2^{5m - 5} \cdot 2^5 \\ &= 49(81z) - 53 \cdot 2^{5m - 5}(81 - 32) \\ &= 49(81z) - 53 \cdot 2^{5m - 5}(49) \\ &= 49\underbrace{(81z - 53 \cdot 2^{5m - 5})}_{\in ~ \mathbb Z} \\ \end{align*} So we can take $y = 81z - 53 \cdot 2^{5m - 5}$, as desired.$~~\blacksquare$

Answer 6

Since $49 \mid (5*3^{4m+2} + 53*2^{5m})$, only a few manipulations are needed,

$$49 \mid (5*3^2*3^{4m} + 53*2^{5m})$$ $$49 \mid 45*3^{4m} + 53*2^{5m}$$

You can stop here, since if you add $45$ and $53$, we get $98 = 49*2$. You can use the properties of mode $a_1 \equiv b_1 (\bmod c) + a_2 \equiv b_2(\bmod c) = a_1 + a_2 \equiv b_1 + b_2 (\bmod c)$, hence

$$45*3^{4m} 53*2^{5m}\equiv 0(\bmod 49)$$

Finishing the proof.

Answer 7

Hint $\ {\rm mod}\ 49\!:\ \color{#c00}{3^4} \equiv\, \color{#c00}{2^5}$

$\!\begin{eqnarray}{\rm Therefore} &&5\cdot 3^2\cdot \color{#c00}3^{\large \color{#c00}4m} + 53\cdot 2^{\large 5m}\\ \equiv &&\ \ \ \ 45\,\cdot \color{#c00}2^{\large \color{#c00}5m} +\ 4\cdot 2^{\large5m}\\ \equiv && \ \ \ \ 49\cdot 2^{\large 5m}\,\equiv\ 0 \end{eqnarray}$