- #1

issacnewton

- 1,010

- 31

- Homework Statement
- Suppose ##a \mathbb{Z}##. Prove that ##5 | (2^n a) \rightarrow (5 | a)## for any ##n \in \mathbb{N}##

- Relevant Equations
- Mathematical Induction

Following is my proof. Let ##P(n)## be the statement that ##5 | (2^n a) \rightarrow (5 | a)##. Here ## n \in \mathbb{N}## and ##a \in \mathbb{Z}##. Base case is ##n = 1##. Suppose that ##5 | (2^1 a)##. This means that ## 2a = 5m## for some ##m \in \mathbb{Z}##. Now ##5m## is even. Since ##5## is not even, ##m## must be even. Let ##m = 2n## for some ##n \in \mathbb{Z}##. Then ##2a = 5(2n)##. We have, ##a = 5n##. So, ##5 | a##. So, ##5 | (2^1 a)## implies ##5 | a##. So, ##P(1)## is true. Now, let ## k \geq 1## be arbitrary in ##\mathbb{N}##. Suppose that ##P(k)## is true.

$$ 5 | (2^k a) \rightarrow (5 | a) $$

we have to prove that

$$ 5 | (2^{k + 1} a) \rightarrow (5 | a) $$

Suppose, ## 5 | 2^{k+1} a##. So, ## 2^{k+1} a= 5m## for some ##m \in \mathbb{Z}##. It means that ## 2(2^k a) = 5m##. As before, since ##5m## is an even number, ##m## must be even. Let ##m = 2n## for some ##n \in \mathbb{Z}##. So, we get ##2^k a = 5n##. Hence ##5 | (2^k a)##. Using, induction hypothesis, it follows that ##5 | a##. This means that ##P(k+1)## is true. This means that

$$ \forall k \geq 1 [P(k) \rightarrow P(k+1)] $$

So, by induction, its proven that

$$ 5 | (2^n a) \rightarrow (5 | a) $$

for any ## n \in \mathbb{N}##. Is this a valid proof ?

Thanks

$$ 5 | (2^k a) \rightarrow (5 | a) $$

we have to prove that

$$ 5 | (2^{k + 1} a) \rightarrow (5 | a) $$

Suppose, ## 5 | 2^{k+1} a##. So, ## 2^{k+1} a= 5m## for some ##m \in \mathbb{Z}##. It means that ## 2(2^k a) = 5m##. As before, since ##5m## is an even number, ##m## must be even. Let ##m = 2n## for some ##n \in \mathbb{Z}##. So, we get ##2^k a = 5n##. Hence ##5 | (2^k a)##. Using, induction hypothesis, it follows that ##5 | a##. This means that ##P(k+1)## is true. This means that

$$ \forall k \geq 1 [P(k) \rightarrow P(k+1)] $$

So, by induction, its proven that

$$ 5 | (2^n a) \rightarrow (5 | a) $$

for any ## n \in \mathbb{N}##. Is this a valid proof ?

Thanks