# Abstract Algebra: Congruence and The Division Algorithm 1

• Feb 15th 2008, 12:59 PM
Jhevon
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 $r$such 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 :D

Thanks guys (and gals -- dedicated to JaneBennet)
• Feb 15th 2008, 01:16 PM
Henderson
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.
• Feb 18th 2008, 09:24 AM
Jhevon
Quote:

Originally Posted by Henderson
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?
• Feb 18th 2008, 10:54 AM
ThePerfectHacker
Quote:

Originally Posted by Jhevon
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
• Feb 18th 2008, 11:13 AM
Jhevon
Quote:

Originally Posted by ThePerfectHacker
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