Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $r$, $d$ be positive integers, with $d>1$.

Suppose that $d$ divides $2^{r+1}$ but does not divide $2^r$ or $2$. Show that $d$ must equal $2^{r+1}$.

share|cite|improve this question
I have no idea where to go from here. I've been sitting looking at it for ages. Could really use some tips/guidance. – confused Aug 18 '12 at 22:25
If $d$ doesn't divide $2^r$, it doesn't divide $2$ so you can ignore that part. – Ross Millikan Aug 19 '12 at 0:03
up vote 3 down vote accepted

By unique prime factorization, $d = 2^k$ for some $1 \leq k \leq r + 1$. If $k \leq r$, then $d$ divides $2^r$. Hence $k = r + 1$ and you have $d = 2^{r + 1}$.

share|cite|improve this answer
Why does d = 2^k by unique prime factorisation? Is there some rule/result that implies this? – confused Aug 18 '12 at 22:28
Let $d = p_1^{e_1} ... p_r^{e_r}$ be the unique prime factorization of $d$. Since $d$ divides $2^{r + 1}$ and $2$ is prime, you must have that $d$ have only a single prime (to some power) in it prime factorization. The prime must be $2$. Hence $d = 2^k$ for some $k$. – William Aug 18 '12 at 22:31
Oh, right! Of course. – confused Aug 18 '12 at 22:31

Hint $\, $ For $\rm\,p\,$ prime, $\rm\: p^{n+1} = cd\:\Rightarrow\:\color{#0A0}{\frac{p^n}d} = \color{#C00}{\frac{c}p}\:$ so $\rm\:\color{#0A0}{d\nmid p^n}\:$ $\Rightarrow$ $\rm\:\color{#C00}{p\nmid c}\:\Rightarrow\:p^{n+1}\:|\:d\:$ $\Rightarrow$ $\rm\:c=1\ \ $ QED

Remark $\, $ It's a special case of the following widely-applicable factorization refinement Lemma.

Lemma $\rm\ \ ab = cd\:\Rightarrow\:(a,d)(b,d) = d,\ $ if $\rm\:(\color{#C00}{a,b,c,d}) = 1\:$ and $\rm\:a,b,c,d\in \Bbb N$

Proof $\rm\ \ \ \ (a,d)(b,d)\, =\, (ab,d(a,b,d)) \,=\, d(\color{#C00}{c,a,b,d}) = d$

share|cite|improve this answer

Think this way: if $d$ divides $2^{r+1}$ then what does $d$ look like? Well, first take the prime factorization of $2^{r+1} = 2 \cdot 2 \cdot \ldots \cdot 2$ (where there are $r+1$ 2's in the product). So if $d$ divides this, we know $d = 2 \cdot 2 \cdot \ldots \cdot 2$ with $k$ 2's, where $0 \leq k \leq r+1$, right?

Now you have conditions that say $d$ doesn't divide $2^r$, and $d$ would divide $2^r$ if $k$ were anything up to $r$. (You also know $d$ doesn't divide $2$, which is a useless condition since anything dividing $2$ also divides $2^r$.) Since $k$ must be $> r$ and $\leq r+1$, the only choice is $k=r+1$ and you're done.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.