Abstract Algebra: GCD and Congruence

**Jhevon** · February 26th 2008, 01:39 AM

Stupid little question. Just wanted you to check my work. This was the quickest way I saw to do it, but i'm not convinced it's the best way, or even valid at all.

Problem:

Prove that if $\mbox{gcd}(a,m) = 1$ , then there is a solution (for $x$ ) to the congruence $ax \equiv b~(\mbox{mod }m)$ .

Solution:

Proof.

Assume $\mbox{gcd}(a,m) = 1$ . Then $ak + ml = 1$ for $k,l \in \mathbb{Z}$ . We want to show that there exists an $x$ such that $ax = mn + b$ , for $n,b \in \mathbb{Z}$ (since this would mean
$mk = ax - b \Longleftrightarrow ax \equiv b~(\mbox{mod }m)$ ). Rearranging our first equation we have $ak = m(-l) + 1$ . It suffices to take $x = k,~n = -l, \mbox{ and }b = 1$

QED

does that work?

Thanks guys

**kalagota** · February 26th 2008, 07:14 AM

ahmm, we were taught this way..

we have to consider that $gcd(a,n) | b$ for that linear congruence have solutions (in fact, exactly $gcd(a,n)$ solutions), otherwise, there would be no solution.

besides, i think, b and n are already fixed.. however, based from your proof, you took values for n and b..
hmm, anyways, this are just my intuitions and probably, our number thoerist could answer it more precisely.. Ü

**ThePerfectHacker** · February 26th 2008, 08:51 AM

Exactly

Try to prove a stronger result (if you have free time)

Let $a,n$ be positive integers. Let $\gcd(a,n)=d$ . Prove that the congruence $ax\equiv b (\bmod n)$ has exactly $d$ solutions mod $n$ if $d|n$ .

**Jhevon** · February 26th 2008, 11:51 AM

Originally Posted by kalagota

besides, i think, b and n are already fixed.. however, based from your proof, you took values for n and b..
hmm, anyways, this are just my intuitions and probably, our number thoerist could answer it more precisely.. Ü

ok. i can kind of see where you're going with this...

Originally Posted by kalagota

ahmm, we were taught this way..

we have to consider that $gcd(a,n) | b$ for that linear congruence have solutions (in fact, exactly $gcd(a,n)$ solutions), otherwise, there would be no solution.

this part went over my head however.

forgive me, i'm taking a baby algebra course (the grown-up algebra course is in the Fall, and i needed something to do 'till then. God forbid that i took another liberal arts course!

)

anyway, we have not examined congruences to the point where we can tell how many solutions they have or any other such properties. we pretty much only learnt how to turn them into regular equations.

however, i'll try to run with your observation and see if i get in trouble.

Proof.

Assume $\mbox{gcd}(a,m) = 1$ . Then $ak + ml = 1$ for $k,l \in \mathbb{Z}$ . We want to show that there exists an $x$ such that $ax = mn + b$ , for $n,b \in \mathbb{Z}$ (since this would mean
$mk = ax - b \Longleftrightarrow ax \equiv b~(\mbox{mod }m)$ ).

Now, note that $gcd(a,n) | b$ ... (wait i don't see that! we have $ax + n(-m) = b$ , would that not mean $gcd(a,n) = b$ ? i mean, to have it divide $b$ , won't we need $p(ax + n(-m)) = b$ for some $p \in \mathbb{Z}$ ?)

...er, anyway, note that $gcd(a,n)|b$ . this means $p(aq + nw) = b$ , that is, $a(pq) + n(pw) = b \implies a(pq) = n(-pw) + b$ . We have the desired result if $x = pq$ , and ...

ok, i can't fake this anymore, I don't know what's going on. my "proof" doesn't even use the fact that $gcd(a,m) = 1$ . what's the game plan here?

**JaneBennet** · February 26th 2008, 03:31 PM

Originally Posted by Jhevon

It suffices to take $x = k,~n = -l, \mbox{ and }b = 1$

QED

does that work?

I don’t think so. What the question is saying is that if a and m are coprime, then a can be made congruent to any integer modulo m by multiplying by a suitable x.

I think you can do it this way. If $b\mid m$ , then $x=0$ is a solution to the congruence equation. So assume $b\nmid m$ and write $b=qm+r,\ 0<r<m$ .

Now consider the numbers $a,2a,\ldots,(m-1)a$ . If $ai\equiv aj\!\!\!\pmod{m}$ , where $1\leq i,j\leq m$ , then $m\mid a(i-j)$ . But $\gcd{(a,n)}=1$ . Hence $m\mid i-j\ \Rightarrow\ i-j=0$ (since $0<i,j<m)$ . So $i\ne j\ \Rightarrow\ ai\not\equiv aj\!\!\!\pmod{m}$ . It follows that $a,2a,\ldots,(m-1)a$ are all distinct modulo m; thus $a,2a,\ldots,(m-1)a\!\!\!\pmod{m}$ is a permutation of $1,2,\ldots,m-1\!\!\!\pmod{m}$ .

Now r is one of the numbers $1,2,\ldots,m-1$ . Thus there is an integer x such that $ax\equiv r\!\!\!\pmod{m}$ . This concludes the proof as $r\equiv b\!\!\!\pmod{m}$ .

**Jhevon** · February 26th 2008, 04:18 PM

Originally Posted by JaneBennet

I don’t think so. What the question is saying is that if a and m are coprime, then a can be made congruent to any integer modulo m by multiplying by a suitable x.

I think you can do it this way. If $b\mid m$ , then $x=0$ is a solution to the congruence equation. So assume $b\nmid m$ and write $b=qm+r,\ 0<r<m$ .

Now consider the numbers $a,2a,\ldots,(m-1)a$ . If $ai\equiv aj\!\!\!\pmod{m}$ , where $1\leq i,j\leq m$ , then $m\mid a(i-j)$ . But $\gcd{(a,n)}=1$ . Hence $m\mid i-j\ \Rightarrow\ i-j=0$ (since $0<i,j<m)$ . So $i\ne j\ \Rightarrow\ ai\not\equiv aj\!\!\!\pmod{m}$ . It follows that $a,2a,\ldots,(m-1)a$ are all distinct modulo m; thus $a,2a,\ldots,(m-1)a\!\!\!\pmod{m}$ is a permutation of $1,2,\ldots,m-1\!\!\!\pmod{m}$ .

Now r is one of the numbers $1,2,\ldots,m-1$ . Thus there is an integer x such that $ax\equiv r\!\!\!\pmod{m}$ . This concludes the proof as $r\equiv b\!\!\!\pmod{m}$ .

Awed Jane, truly awed. It took me a while to get your proof (you're on a whole other level of thinking than i am) but i understand it perfectly now.

it was almost like one of those magic proofs, i kept wondering, "where is she going with this?" then i saw the light. how did you come up with this? it doesn't seem to me to be a "standard approach," is it? for instance, starting out by considering whether b|m or not, why did you do that? is that something i should always look out for?

**Jhevon** · February 27th 2008, 05:26 PM

Originally Posted by JaneBennet

If $b\mid m$ , then $x=0$ is a solution to the congruence equation. So assume $b\nmid m$ and write $b=qm+r,\ 0<r<m$ .

did you mean to consider $m | b \mbox{ and } m \nmid b$ ?

**JaneBennet** · February 27th 2008, 05:52 PM

Originally Posted by Jhevon

did you mean to consider $m | b \mbox{ and } m \nmid b$ ?

Yes, you’re right. Sorry, my mistake.

Thread: Abstract Algebra: GCD and Congruence

LinkBack

Thread Tools

Display

Abstract Algebra: GCD and Congruence

Similar Math Help Forum Discussions

Is linear algebra considered to be a type of abstract algebra?

terminology about ring/algebra in abstract algebra and measure theory

abstract algebra!

Abstract Algebra: Congruence and The Division Algorithm 1

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

Search Tags