# Thread: Abstract Algebra: GCD and Congruence

1. ## Abstract Algebra: GCD and Congruence

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

2. 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.. Ü

3. 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$.

4. 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?

5. 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.

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. 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}$.

6. 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.

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. 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?

7. 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.
did you mean to consider $m | b \mbox{ and } m \nmid b$?

8. Originally Posted by Jhevon
did you mean to consider $m | b \mbox{ and } m \nmid b$?
Yes, you’re right. Sorry, my mistake.