Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##

[issacnewton]

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

 

[docnet]

I'm not a math whiz, but it looks pretty good to me.

Note the statement is true for $n=0$ as well.

 

[Hill]

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

Suppose that $5|(2^1a)$. This means that $2a=5m$ for some $m∈Z$. Now $5m$ is even. Since $5$ is not even, $m$ must be even. Let $m=2n$ for some $n∈Z$. Then $2a=5(2n)$. We have, $a=5n$. So, $5|a$. So, $5|(2^1a)$ implies $5|a$.

Why to use the induction? Just modify your first paragraph (quoted above) like this:

Suppose that $5|(2^na)$. This means that $2^na=5m$ for some $m∈Z$. Since $5$ does not divide $2^n$, $m$ must. Let $m=2^nk$ for some $k∈Z$. Then $2^na=5(2^nk)$. We have, $a=5k$. So, $5|a$. So, $5|(2^na)$ implies $5|a$.

 

[fresh_42]

This is basically the definition of a prime number. A number $p$ is prime if it is not invertible and $p\,|\,a\cdot b$ implies $p\,|\,a$ or $p\,|\,b$.

The only invertible numbers are $\pm 1,$ and $5$ is prime. Since $5\,\nmid\,2^n$ we may conclude $5\,|\,a.$

Now, you could ask why $5$ is prime. The reason is, that $5$ is irreducible (cannot be written as a product with factors that are not invertible - this rules out that we write $5=(-1)\cdot (-1)\cdot 5$) and irreducibility and primality are identical in the domain of integers. You could try to show this equivalence.

 

[WWGD]

This is basically the definition of a prime number. A number $p$ is prime if it is not invertible and $p\,|\,a\cdot b$ implies $p\,|\,a$ or $p\,|\,b$.

The only invertible numbers are $\pm 1,$ and $5$ is prime. Since $5\,\nmid\,2^n$ we may conclude $5\,|\,a.$

Now, you could ask why $5$ is prime. The reason is, that $5$ is irreducible (cannot be written as a product with factors that are not invertible - this rules out that we write $5=(-1)\cdot (-1)\cdot 5$) and irreducibility and primality are identical in the domain of integers. You could try to show this equivalence.

Well, arguably more practical, test the ( finitely many) possible divisors of 5.
Edit: Show too, that $5| 2^{n}$ never happens because all multiples of$5$end in $\{0,5\}$ , while all powers of $2$ end in$\{2,4,6,8\}$

 

[fresh_42]

Well, arguably more practical, test the ( finitely many) possible divisors of 5.
Edit: Show too, that $5| 2^{n}$ never happens because all multiples of$5$end in $\{0,5\}$ , while all powers of $2$ end in$\{2,4,6,8\}$

Or you take the big canon again.

$5\,\nmid\,2.$ If $5\,|\,2^n=2\cdot (2^{n-1})$ then $5\,|\,2^{n-1}$ since $5$ is prime. But $5\,\nmid\,2^{n-1}$ by induction hypothesis, contradicting the assumption that $5\,|\,2^n.$

Of course, the even bigger cannon, the FTA solves all at once.

 

[WWGD]

Or you take the big canon again.

$5\,\nmid\,2.$ If $5\,|\,2^n=2\cdot (2^{n-1})$ then $5\,|\,2^{n-1}$ since $5$ is prime. But $5\,\nmid\,2^{n-1}$ by induction hypothesis, contradicting the assumption that $5\,|\,2^n.$

Of course, the even bigger cannon, the FTA solves all at once.

Seems your phrase doesn't translate that well to English. Do you mean along the lines of " Using a tank to kill a fly"?

 

[fresh_42]

Why to use the induction? Just modify your first paragraph (quoted above) like this:

Suppose that $5|(2^na)$. This means that $2^na=5m$ for some $m∈Z$.

So far so good.

Since $5$ does not divide $2^n$, $m$ must.

What do you use here, FTA? Why is this the case? I do not see it. Maybe a language issue? I complete the missing sentence as

Since $5$ does not divide $2^n$, $m$ must [divide $2^n$].

If we assume $5=2\cdot b$ and $n=1$ then it does not follow that $m\,|\,2.$ Please explain how
$$
5\nmid 2^n \wedge 5m=2^na \Longrightarrow m|2^n
$$

Edit: $5\nmid 2^3=8$ and $5\cdot 24= 2^3\cdot 15$ but $24$ does not divide $8.$

If you wanted to say ...

Since $5$ does not divide $2^n$, $m$ must [be divided by $2^n$].

... then how does this differ from what had to be shown anyway? I'm confused by your argument and the missing part of your sentence.

 

[fresh_42]

Seems your phrase doesn't translate that well to English. Do you mean along the lines of " Using a tank to kill a fly"?

Yes. We say "Shooting at sparrows with cannons". Wiki says cannon is the correct translation:
https://en.wikipedia.org/wiki/Cannon

FTA = fundamental theorem of arithmetics, which is a big cannon to shoot at a prime number

Edit: This idiom is far older than Captain Sparrow's difficulties with authorities having cannons to shoot at him. And before I forget, Captain Sparrow's real-world name has a meaning in German, too, even though not a nice one.

 

[Hill]

So far so good.

What do you use here, FTA? Why is this the case? I do not see it. Maybe a language issue? I complete the missing sentence as


If we assume $5=2\cdot b$ and $n=1$ then it does not follow that $m\,|\,2.$ Please explain how
$$
5\nmid 2^n \wedge 5m=2^na \Longrightarrow m|2^n
$$

Edit: $5\nmid 2^3=8$ and $5\cdot 24= 2^3\cdot 15$ but $24$ does not divide $8.$

If you wanted to say ...

... then how does this differ from what had to be shown anyway? I'm confused by your argument and the missing part of your sentence.

You are right. I actually meant your first version of the completed sentence, but my shortcut is wrong anyway.

 

[Gavran]

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

Suppose that P(k) is true.

5|(2ka)→(5|a)

we have to prove that

5|(2k+1a)→(5|a)

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