# If $d$ divides $2n$ and $d$ doesn't divide $n$, then $d$ is even

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?

• Hint: if $d$ was odd, $m$ would be even. – Wojowu Mar 15 at 19:28
• $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$. – 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

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

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

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

• Convention: $\ d/p\mid n\$ means $\ d/p\,$ is an integer, so $\,p\mid d\ \$ – 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$$.

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.