Results 1 to 3 of 3

Thread: [SOLVED] Abstract Algebra: Congruence and The Division Algorithm 2

  1. #1
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3

    [SOLVED] Abstract Algebra: Congruence and The Division Algorithm 2

    Hello again,

    Now this problem makes me feel even stupider than the last one. But then again, I was always bad at choosing examples. Again, hints are what I want, but it may be hard to do here, since this is a give-an-example question. So if you give an example, tell me your thought process and I'll try to come up with one on my own.


    Problem:

    Disprove with a counter-example: If $\displaystyle n$ is a positive integer and $\displaystyle a,b \in \mathbb{Z}$, then there is an integer $\displaystyle x$ such that $\displaystyle ax \equiv b~(\mbox{mod }n)$


    Things that may come in handy:

    The following statments are equivalent:

    $\displaystyle a \equiv b~(\mbox{mod }n)$

    $\displaystyle n | (a - b)$

    $\displaystyle a - b = kn$ for some $\displaystyle k \in \mathbb{Z}$


    What I've Tried:

    All kinds of foolishness. On my latest attempt:

    ...wait! does $\displaystyle a = n = 2,~b = 3$ work?!

    That just came to me when I was typng out my "method" (I'll let you see it if you're interested, so you can comment on whether or not my reasoning was sound).

    Still check the example, I didn't sleep last night, so it might be that this is obviously wrong, but I'm too tired to tell.

    Thanks guys (and gals -- dedicated to JaneBennet... again)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Henderson's Avatar
    Joined
    Dec 2007
    Posts
    127
    Thanks
    2
    Quote Originally Posted by Jhevon View Post
    ...wait! does $\displaystyle a = n = 2,~b = 3$ work?!
    Yes.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jhevon View Post
    Disprove with a counter-example: If $\displaystyle n$ is a positive integer and $\displaystyle a,b \in \mathbb{Z}$, then there is an integer $\displaystyle x$ such that $\displaystyle ax \equiv b~(\mbox{mod }n)$
    This is not always true.
    Consider $\displaystyle 2x \equiv 1(\bmod ~ 4)$.
    The left hand side is always even and right hand side is odd, so it is impossible.

    However, if $\displaystyle n\geq 2 \mbox{and }a$ are positive integers and we have $\displaystyle ax\equiv b(\bmod n)$ so that $\displaystyle d=\gcd(a,n)$ divides $\displaystyle b$ then it is solvable.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euclids algorithm & congruence equations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jun 17th 2010, 10:10 PM
  2. congruence and the Division Algorithm...
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Jul 8th 2008, 07:56 PM
  3. [SOLVED] Abstract Algebra: Homomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Mar 16th 2008, 08:57 AM
  4. Abstract Algebra: GCD and Congruence
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: Feb 27th 2008, 04:52 PM
  5. Abstract Algebra: Congruence and The Division Algorithm 1
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Feb 18th 2008, 11:13 AM

Search Tags


/mathhelpforum @mathhelpforum