Abstract Algebra: Congruence and The Division Algorithm 1

**Jhevon** · February 15th 2008, 12:59 PM

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

Thanks guys (and gals -- dedicated to JaneBennet)

**Henderson** · February 15th 2008, 01:16 PM

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.

**Jhevon** · February 18th 2008, 09:24 AM

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?

**ThePerfectHacker** · February 18th 2008, 10:54 AM

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

**Jhevon** · February 18th 2008, 11:13 AM

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

Thread: Abstract Algebra: Congruence and The Division Algorithm 1

LinkBack

Thread Tools

Display

Abstract Algebra: Congruence and The Division Algorithm 1

Similar Math Help Forum Discussions

Euclidan Algorithm linear congruence

Division Algorithm...

congruence and the Division Algorithm...

Abstract Algebra: GCD and Congruence

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

Search Tags