1

I'm trying to prove that if $x$ divides $2^a$ for some integer $a \geq 0$, then $x = 2^b$, where $a \geq b$. In other words, if $x$ divides a power of 2, then $x$ is a power of 2. This makes sense, since the all the factors of a power of 2 are also powers of 2, e.g. the factors of 256 are 1, 2, 4, 8, 16, 32, 64, 128, 256. But I'm not so sure how to word this in a rigorous fashion.

A related question: Does this extend to powers of any integer, instead of just 2? If $x$ divides $k^a$, does $x = k^b$?

devin64
  • 13

1 Answers1

1

In answer to the related question, no. Let $k=4$ and $x=8$. $8$ divides $4^2$, but $8$ is no integer power of 4.

This does extend to any prime $k$, however.

vadim123
  • 82,796
  • Superb, thanks. This is what I'm thinking: assume the contrary, so x divides 2^a but x is not a power of 2. Thus, x contains a prime factor greater than 2. Since 2^a has no prime factors greater than 2, x does not divide 2^a, which is a contradiction. Am I missing anything? – devin64 Oct 26 '13 at 05:03
  • I suppose I could also generalize this to any prime p: assume the contrary, so x divides p^a but x is not a power of p. Thus, x contains some prime factor q such that p == q. Since p^a has no prime factors q, x does not divide p^a, which is a contradiction. – devin64 Oct 26 '13 at 05:09