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

  • #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
 
Physics news on Phys.org
  • #2
I'm not a math whiz, but it looks pretty good to me.

Note the statement is true for ##n=0## as well.
 
  • #3
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:
  • Like
  • Skeptical
Likes fresh_42 and issacnewton
  • #4
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.
 
  • Like
Likes dextercioby, docnet and WWGD
  • #5
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\}##
 
  • Like
Likes MatinSAR and fresh_42
  • #6
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.
 
  • Like
Likes docnet
  • #7
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"?
 
  • #8
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:
  • Like
Likes docnet
  • #9
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.
 
  • Like
Likes docnet
  • #10
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.
 
  • Like
Likes docnet and fresh_42

Similar threads

  • Precalculus Mathematics Homework Help
Replies
4
Views
839
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
13
Views
1K
  • Precalculus Mathematics Homework Help
Replies
15
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
797
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
996
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
821
Back
Top