[Math] Suppose $a \in \mathbb{Z}.$ Prove that $5 \mid 2^na$ implies $5 \mid a$ for any $n \in \mathbb{N}$

discrete mathematicsdivisibilityinduction

This question is supposed to be solved by induction, however I'm unsure of where to get my base case from exactly, because the question is asking about both $a$ and $n$. I started with my base case being $n = 1$, but then I get $5\mid 2a$, and I'm unsure what to do from there. Am I just barking up the wrong tree here? Or how should I go about getting a start to this problem?

Best Answer

Basis ($n=0$):

If $5|2^0a$ then $5|a$ (trivial).

Inductive step:

Hypothesis: $5|2^na \Rightarrow 5|a$

Thesis: $5|2^{n+1}a \Rightarrow 5|a$

Proof: Suppose $5|2^{n+1}a$, then, by definition $\exists k \in \mathbb{Z} $ such that $2^{n+1}a = 5k \Rightarrow 2^na=\frac{5k}{2} \in \mathbb{Z} \overset{j=k/2}{\Rightarrow} 2^na=5j, j\in\mathbb{Z} \Rightarrow 5|2^na \overset{Inductive\ hypothesis}{\Rightarrow} 5|a $

EDIT: $k/2 \in \mathbb{Z}$ because $k$ is even.

Let's prove it: suppose $k$ is not even, then $5k$ is not even, but $5k=2^{n+1}a$, which is even; and that's a contradiction. Hence, $k$ is even.

Related Question