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

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

Prove the following conditional; If $\displaystyle x\equiv a \pmod n$ then either $\displaystyle x\equiv a \pmod {2n}$ or $\displaystyle x \equiv a+n \pmod {2n}$

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

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

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

$\displaystyle 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 $\displaystyle (x-a)=n*q$ by 2 but that doesn't seem too profitable.

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

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

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

And

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

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

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

Neither of which seem too promising.

Any ideas or errors?

2. ## 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.

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

Assume $\displaystyle x\equiv a \pmod n$

$\displaystyle (x-a=qn)$

Since q is either even or odd,

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

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

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

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

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

OK that looks great thanks!