I have encountered a proof regarding dihedral groups we this fact is used:

If $d\mid 2n$ and $d\nmid n$, then $d$ is even and ${d\over 2}\mid n$.

I can't seem to understand why this is true. If $d\nmid n$, then there are $q,r \in \mathbb{Z}$ so that $0 < r < d$ and $n = qd + r$. On the other hand, $d\mid 2n$ means that there is $m \in \mathbb{Z}$ so that $2n = md$. We need to somehow use these two facts.

Also, my second question is how we can naturally generalize this result?

  • $\begingroup$ Hint: if $d$ was odd, $m$ would be even. $\endgroup$ – Wojowu Mar 15 at 19:28
  • $\begingroup$ $2n =md$. And $2$ is prime. So $2|m$ or $2|d$. If $2|m$ then $n = \frac m2 d$ and $d|n$. If $2|d$ then $d$ is even. General. If $d|pn$ for a prime $p$ and $d\not \mid n$ then $p|d$. Even more general. If $d|ab$ then $\frac d{\gcd(d,b)}|a$. $\endgroup$ – fleablood Mar 15 at 21:22

Suppose $d$ is odd. Then $d$ and $2$ are relatively prime and $d\mid 2n$, so by Euclid lemma we have $d\mid n$.

A contradiction. So $d$ must be even.

We could have more general situation.

Say $d\mid pn$ for some prime $p$ and $d$ doesn't divide $n$. Then $p\mid d$.

The proof goes exactly the same as for $p=2$.


It's also possible to see what's going on simply by keeping track of factors of $2$; note that this kind of analysis could also be generalized to other prime factors, as has been illustrated in previously posted answers.

Let $n:= 2^aQ,\ 2n=2^{a+1}Q, d:=2^bP$ where $Q$ represents the product of all of the odd prime factors of $n$ and $P$ represents the product of all of the odd prime factors of $d$. We could write out all of those factors and explicitly show this, but it should be plain that $d\mid 2n \Rightarrow P\mid Q$. Note that thus far, the exponents $a,b$ might be $0$, so we have not assumed that $d$ is even.

$d\mid 2n \Rightarrow b\le a+1$

$d\not \mid n \Rightarrow b>a$

Together, these establish $b=a+1$, meaning that $d$ has at least one factor of $2$ and is even, even if $a=0$.

This also illustrates the second point: the exponent of $2$ in $d\over 2$ is simply $b-1=a$. Hence $\frac{d}{2} \mid n$


If you know that the remainder $r$ in $n=qd+r$ with $0\lt r\lt d$ is unique, then from $2n=md$ we get


with $0\lt r'=d-r\lt d$, so that, by uniqueness of the remainder, we have $r'=r$, i.e. $d-r=r$, hence $d=2r$.


$d| 2n$ then $2n=kd;$

Since $kd$ is even, $2| kd $.

Euclid's lemma:

1) $2| k$ or 2) $2|d$.

1) If $2|k$ then $k=2k'.$


$n=k'd$, i.e. $d|n$ , a contradiction.

2) Hence $2|d$ , and we are done.


By below $\ d\mid pn\iff\!\!\!\! \overbrace{d\mid n}^{\large\color{#0a0}{(d,p)}\ =\ \color{#c00}1}\!\! $ or $\ \overbrace{{d/\color{#c00}p}\mid n}^{\large\color{#0a0}{ (d,p)}\ =\ \color{#c00} p}\!,\ $ by $\ \color{#0a0}{(d,p)}\mid \color{#c00}p\, $ prime.

Lemma $\,\ d\mid an\iff\smash[t]{\overbrace{ d/\color{#0a0}{(d,a)}\,\mid\, n,\,}\ }$ where $\,\ (x,y) := \gcd(x,y)$

Proof $\quad\ d\mid an\iff d\mid dn,an,\iff d\mid (dn,an)=(d,a)n\iff d/(d,a)\mid n $

  • $\begingroup$ Convention: $\ d/p\mid n\ $ means $\ d/p\,$ is an integer, so $\,p\mid d\ \ $ $\endgroup$ – Bill Dubuque Mar 15 at 20:23

Intuitively. If $d|ab$ and $d\not \mid b$ then "some part of $d$ must divide $a$". So if $d|2n$ but $d\not \mid n$ then some (non-trivial) part must divide $2$ and that part must be $2$ so $d$ is even.


That's intuition. Let's make a proof.


If $d|ab$. Let $\gcd(d,b) = g$ and let $d = d'g$ and $b = b'g$. It's easy to see that $d'$ and $b'$ are relatively prime: if $b'$ and $d'$ had any non-trivial factor, $k$, in common then $kg$ would be a common divisors of $b$ and $d$ contradicting that $g$ is the greatest common divisor.

So $d=d'g$ and $ab = ab'g$ and $d'g|ab'g$ so $d'|ab'$. But $d'$ and $b'$ are relatively prime so they have no factors in common. So $d'|a$.

Now if $d|b$ then $d'g|b'g$ so $d'|b'$ but $d'$ and $b'$ are relatively prime so $d' = 1$ and $d = \gcd(d,b)$.

Lemma 1: $d|b \iff \gcd(d,b) = d$.

If $d|ab$ the $d'|a$ but if $d\not \mid b$ then $\gcd(d,b)=g \ne d$ so $d' = \frac dg > 1$. $d'\ne 1$ and $d'|a$.


Lemma 2: If $d|ab$ but $d\not \mid b$ then $d' = \frac d{\gcd(d,b)} > 1$ and $d'|a$.

So if $d|2n$ and $d\not \mid n$ then $\frac d{\gcd(d,n)} > 1$ and $\frac d{\gcd(d,n)} |2$.

So $\frac d{\gcd(d,n)} = 2$ and $d = \frac d{\gcd(d,n)}\gcd(d,n) = 2\gcd(d,n)$. And $d $ is even.


Actually, this may be the best most general Theorem:

Theorem: If $d|mn$ then $\frac d{\gcd(d,n)}|m$.

I'll leave the proof to you, and I'll leave it to you to figure out how that implies if $d|2n$ and $d\not\mid n$ then $d$ is even.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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