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?
On
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
$$n=2n-n=md-(qd+r)=(m-q)d-r=(m-q+1)d+(d-r)=q'd+r'$$
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$.
On
$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'.$
$2n=2k'd$;
$n=k'd$, i.e. $d|n$ , a contradiction.
2) Hence $2|d$ , and we are done.
On
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 $
On
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$
On
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$.
So
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.
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.
The proof goes exactly the same as for $p=2$.