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

• February 15th 2008, 01:11 PM
Jhevon
[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)
• February 15th 2008, 01:18 PM
Henderson
Quote:

Originally Posted by Jhevon
...wait! does $a = n = 2,~b = 3$ work?!

Yes.
• February 16th 2008, 02:30 PM
ThePerfectHacker
Quote:

Originally Posted by Jhevon
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.