Prove: If $d | n$ and $d > 1$, then d does not divide $(2n + 1)$ for $d, n ∈ N.$

Question

I don't want a full proof or whole answer, just some explanation - my proof so far follows the idea that:

$d|n$ therefore $n=dk$ for some integer $k$, and so $2n=d(2k)$ meaning $2n|d.$

My tutor told me something along the lines of the next step (or something) being $2n+d$, and then $2n+2d$, but because $d>1$ then $2n$ does not divide $2n+1$.

I would like some explanation/advice please, and thanks.

Answer 1

Suppose $d$ divides $n$, then certainly $d$ divides $2n$.

Assume $d$ also divides $2n+1$. Then should also divide the difference $2n+1-2n$.

Hence $d$ divides 1 $\implies d=1$

Answer 2

Hint: $$\gcd(2n+1,n)=\gcd(n,n+1)$$

This is due to the property that $\gcd(a, b) = \gcd(a, b+ka)$.

Answer 3

Given $a, b \in \mathbb Z$ $\exists! (q, r) $ such that $a=bq+r$ and $0\leq r<|b|$ (euclidean division theorem).

You have $$ 2n+1=2kd+1 $$ so $(2k,1)$ is the unique $(q,r)$ for $a=2n+1$ and $b=d$.