Results 1 to 3 of 3

Math Help - If x is congruent to a modulo n then either x is congruent to a modulo 2n or...

  1. #1
    Member
    Joined
    Oct 2009
    From
    Detroit
    Posts
    195
    Thanks
    5

    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<n) 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    708
    Thanks
    293

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    From
    Detroit
    Posts
    195
    Thanks
    5

    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!
    Last edited by bkbowser; March 22nd 2014 at 08:16 AM. Reason: Something redundant floating around in line 2
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 21st 2014, 07:00 PM
  2. [SOLVED] congruent modulo n
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 8th 2009, 11:53 AM
  3. congruent to modulo; the fundamentals
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 4th 2009, 06:08 PM
  4. Replies: 1
    Last Post: October 6th 2009, 12:11 AM
  5. [SOLVED] Congruent Modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 27th 2006, 07:25 PM

Search Tags


/mathhelpforum @mathhelpforum