Results 1 to 3 of 3

Math Help - [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 n is a positive integer and a,b \in \mathbb{Z}, then there is an integer x such that ax \equiv b~(\mbox{mod }n)


    Things that may come in handy:

    The following statments are equivalent:

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

    n | (a - b)

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


    What I've Tried:

    All kinds of foolishness. On my latest attempt:

    ...wait! does 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 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
    9
    Quote Originally Posted by Jhevon View Post
    Disprove with a counter-example: If n is a positive integer and a,b \in \mathbb{Z}, then there is an integer x such that ax \equiv b~(\mbox{mod }n)
    This is not always true.
    Consider 2x \equiv 1(\bmod ~ 4).
    The left hand side is always even and right hand side is odd, so it is impossible.

    However, if n\geq 2 \mbox{and }a are positive integers and we have ax\equiv b(\bmod n) so that d=\gcd(a,n) divides 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: June 17th 2010, 10:10 PM
  2. congruence and the Division Algorithm...
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: July 8th 2008, 07:56 PM
  3. [SOLVED] Abstract Algebra: Homomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 16th 2008, 08:57 AM
  4. Abstract Algebra: GCD and Congruence
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: February 27th 2008, 04:52 PM
  5. Abstract Algebra: Congruence and The Division Algorithm 1
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 18th 2008, 11:13 AM

Search Tags


/mathhelpforum @mathhelpforum