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

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}$.

-
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

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}$.

-
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$

-

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.

-