Results 1 to 5 of 5

Math Help - Abstract Algebra: Congruence and The Division Algorithm 1

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

    Abstract Algebra: Congruence and The Division Algorithm 1

    Hello Mathematicians,

    I've come to bother you again. This is a homework problem, so please, offer only hints if you can, especially since I think this problem should be easy for me (it has the stench of something that is straight forward).

    Problem:

    Prove that if n is a positive integer, and a,b \in \mathbb{Z}, then there is an integer x such that
    a + x \equiv b~(\mbox{mod }n)


    Things that may come in handy:

    As the title suggests, I have a strong gut feeling that I'm supposed to use the Division Algorithm here. But I can't seem to make it fit together nicely.

    The Division Algorithm: If a,b \in \mathbb{Z} with b>0, then there exists unique integers q and rsuch that

    a = bq + r,~~~~~0 \le r < b


    What I've Tried:

    Okay, so I decided to try and make this work by the division algorithm.

    Now, a + x \equiv b~(\mbox{mod }n) means that n | (a - b + x) \Longleftrightarrow a - b + x = kn for k \in \mathbb{Z}

    By the Division Algorithm, if a_1, b_1 \in \mathbb{Z} with b_1 > 0, then there are unique integers q and r such that

    a_1 = b_1q + r for 0 \le r < b_1


    ...and I'm stuck there...

    I was thinking of choosing n = b_1, and a - b = a_1. so the integer x I am looking for would be -r

    but I don't think that proves anything, nor am I sure that I can actually choose them like that...

    Help

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

  2. #2
    Member Henderson's Avatar
    Joined
    Dec 2007
    Posts
    127
    Thanks
    2
    Your problem is a restatement of the division algorithm.

    If the LHS is congruent to b mod n, the for some integer k, it equals kn+b.

    a+x=kn+b should be close enough to the division algorithm that you can take it from there.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Henderson View Post
    Your problem is a restatement of the division algorithm.

    If the LHS is congruent to b mod n, the for some integer k, it equals kn+b.

    a+x=kn+b should be close enough to the division algorithm that you can take it from there.
    Yes. as you can see from my post, that's kind of the direction i wanted to go in. my concern however was the "uniqueness" of x and the "randomness" of a and b. does our algorithm cover that, or do we not have to concern ourselves with that, just go by the definition?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jhevon View Post
    Problem:

    Prove that if n is a positive integer, and a,b \in \mathbb{Z}, then there is an integer x such that
    a + x \equiv b~(\mbox{mod }n)
    x = b-a
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ThePerfectHacker View Post
    x = b-a
    that would mean k has to be zero. but that's fine right? since we only want to find some x in existence. b - a is an integer if a and b are, so i guess that works...

    i guess i was looking for something more general (we don't even need the division algorithm to know that works), but that is simple and nice
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidan Algorithm linear congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 9th 2009, 12:35 PM
  2. Division Algorithm...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 8th 2008, 09:33 PM
  3. congruence and the Division Algorithm...
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: July 8th 2008, 08:56 PM
  4. Abstract Algebra: GCD and Congruence
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: February 27th 2008, 05:52 PM
  5. Replies: 2
    Last Post: February 16th 2008, 03:30 PM

Search Tags


/mathhelpforum @mathhelpforum