# If x is congruent to a modulo n then either x is congruent to a modulo 2n or...

• Mar 21st 2014, 06:56 PM
bkbowser
If x is congruent to a modulo n then either x is congruent to a modulo 2n or...
Prove the following conditional; If $x\equiv a \pmod n$ then either $x\equiv a \pmod {2n}$ or $x \equiv a+n \pmod {2n}$

So just fiddling with x's and a's...

$14 \equiv 0 \pmod 7 \rightarrow [14 \equiv 0 \pmod{2*7} \lor 14 \equiv 0+7 \pmod{2*7}]$

$8 \equiv 1 \pmod 7 \rightarrow [ 8 \equiv 1 \pmod {2*7} \lor 8 \equiv 1+7 \pmod {2*7}]$

$9 \equiv 2 \pmod {7} \rightarrow [9 \equiv 2 \pmod {2*7} \lor 9 \equiv 2+7 \pmod {2*7}]$

These all look like good conditionals to me so I'm satisfied that I can write a proof.

I've tried a direct proof where I just multiply $(x-a)=n*q$ by 2 but that doesn't seem too profitable.

My other idea is to assume that $(a=0) \lor (a=k but that doesn't seem to work out well either.

$\frac{x-0}{n}=q$

$x=2n(q\frac{1}{2})$

And

$\frac{x-k}{n}=q$

$x-k-n+n=n*q$

$x-k-n=n*q-n$

Neither of which seem too promising.

Any ideas or errors?
• Mar 21st 2014, 07:20 PM
johng
Re: If x is congruent to a modulo n then either x is congruent to a modulo 2n or...
Hi,
Hint: From $x\equiv a\pmod n$, there is $q\in\mathbb Z$ with $x-a=nq$. Consider the two cases q even and q odd.
• Mar 22nd 2014, 08:14 AM
bkbowser
Re: If x is congruent to a modulo n then either x is congruent to a modulo 2n or...
Assume $x\equiv a \pmod n$

$(x-a=qn)$

Since q is either even or odd,

$Let \, (q=2m) \lor (q=2m+1)$

$(x-a=(2m)n) \lor (x-a=(2m+1)n)$

$(x-a=2n(m)) \lor (x-a=2mn+1n)$

$(x-a=2n(m)) \lor (x-(a+n)=2n(m))$

$(x\equiv a \pmod{2n}) \lor (x \equiv (a+n) \pmod{2n})$

OK that looks great thanks!