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

• issacnewton
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

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

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

issacnewton said:
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##.

Last edited:
fresh_42 and issacnewton
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.

dextercioby, docnet and WWGD
fresh_42 said:
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\}##

MatinSAR and fresh_42
WWGD said:
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.

docnet
fresh_42 said:
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"?

Hill said:
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.
Hill said:
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
Hill said:
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 ...
Hill said:
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.

Last edited:
docnet
WWGD said:
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.

docnet
fresh_42 said:
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.

docnet and fresh_42
issacnewton said:
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 ##

• Precalculus Mathematics Homework Help
Replies
4
Views
120
• Precalculus Mathematics Homework Help
Replies
19
Views
558
• Precalculus Mathematics Homework Help
Replies
11
Views
342
• Precalculus Mathematics Homework Help
Replies
11
Views
529
• Precalculus Mathematics Homework Help
Replies
4
Views
890
• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
13
Views
1K
• Precalculus Mathematics Homework Help
Replies
9
Views
389
• Precalculus Mathematics Homework Help
Replies
15
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K