Thread: 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 $\displaystyle \mbox{gcd}(a,m) = 1$, then there is a solution (for $\displaystyle x$) to the congruence $\displaystyle ax \equiv b~(\mbox{mod }m)$.

Solution:

Proof.

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

QED


does that work?


Thanks guys

ahmm, we were taught this way..

we have to consider that $\displaystyle gcd(a,n) | b$ for that linear congruence have solutions (in fact, exactly $\displaystyle 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.. Ü

Exactly

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

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

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 $\displaystyle gcd(a,n) | b$ for that linear congruence have solutions (in fact, exactly $\displaystyle 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 $\displaystyle \mbox{gcd}(a,m) = 1$. Then $\displaystyle ak + ml = 1$ for $\displaystyle k,l \in \mathbb{Z}$. We want to show that there exists an $\displaystyle x$ such that $\displaystyle ax = mn + b$, for $\displaystyle n,b \in \mathbb{Z}$ (since this would mean
$\displaystyle mk = ax - b \Longleftrightarrow ax \equiv b~(\mbox{mod }m)$).

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

...er, anyway, note that $\displaystyle gcd(a,n)|b$. this means $\displaystyle p(aq + nw) = b$, that is, $\displaystyle a(pq) + n(pw) = b \implies a(pq) = n(-pw) + b$. We have the desired result if $\displaystyle 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 $\displaystyle gcd(a,m) = 1$. what's the game plan here?

Originally Posted by Jhevon

It suffices to take $\displaystyle 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 $\displaystyle b\mid m$, then $\displaystyle x=0$ is a solution to the congruence equation. So assume $\displaystyle b\nmid m$ and write $\displaystyle b=qm+r,\ 0<r<m$.

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

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

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 $\displaystyle b\mid m$, then $\displaystyle x=0$ is a solution to the congruence equation. So assume $\displaystyle b\nmid m$ and write $\displaystyle b=qm+r,\ 0<r<m$.

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

Now r is one of the numbers $\displaystyle 1,2,\ldots,m-1$. Thus there is an integer x such that $\displaystyle ax\equiv r\!\!\!\pmod{m}$. This concludes the proof as $\displaystyle 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?

Originally Posted by JaneBennet

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

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

Originally Posted by Jhevon

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

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