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

Question

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?

Answer 1

Taking the base case with $n=0$ (by convention or for convenience), we get $5\mid 2^0a=a$.

For the inductive step, assume that we know that $5\mid 2^{n-1}a\implies 5\mid a$, and suppose that $5\mid 2^na$. Then $$5k=2^na$$ for some integer $k$. Since $5$ is odd and the RHS is even, it follows that $k$ is even, say $k=2k'$. Hence $$5k' = 2^{n-1}a$$ so $5\mid 2^{n-1}a$, and the result follows by induction.

Notice that at no point do we need the far stronger fact that $p\mid ab \iff p\mid a\text{ or }p\mid b$.

Answer 2

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.

Answer 3

$1)$ assume $5\nmid a$

$2)$ by the Division Algorithm $a=5q+r$, $\space\space r\lt 5$,$r<q\space\space\space\space\space\space\space 1)$

$3)$ $2^na=2^n(5q+r)=2^n(5q)+2^nr=5(2^nq)+2^nr$, $\space\space r<5\space\space\space\space\space\space\space 2)$

$4)$ $5\nmid 2^na\space\space\space\space\space\space\space1),2),3)$

$5)$ $F_0$(contradiction)$\space\space\space\space\space\space\space 4)$

$6)$ $5\nmid a\rightarrow F_0\space\space\space\space\space\space\space 5)$

$7)$ $5|a\space\space\space\space\space\space\space 6)$