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

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

Things that may come in handy:

The following statments are equivalent:

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

$\displaystyle n | (a - b)$

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

What I've Tried:

All kinds of foolishness. On my latest attempt:

...wait! does $\displaystyle 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)

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

3. Originally Posted by Jhevon
Disprove with a counter-example: If $\displaystyle n$ is a positive integer and $\displaystyle a,b \in \mathbb{Z}$, then there is an integer $\displaystyle x$ such that $\displaystyle ax \equiv b~(\mbox{mod }n)$
This is not always true.
Consider $\displaystyle 2x \equiv 1(\bmod ~ 4)$.
The left hand side is always even and right hand side is odd, so it is impossible.

However, if $\displaystyle n\geq 2 \mbox{and }a$ are positive integers and we have $\displaystyle ax\equiv b(\bmod n)$ so that $\displaystyle d=\gcd(a,n)$ divides $\displaystyle b$ then it is solvable.