Results 1 to 8 of 8

Math Help - Abstract Algebra: GCD and Congruence

  1. #1
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3

    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
    Last edited by Jhevon; February 26th 2008 at 03:20 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    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.. ‹
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote 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...

    Quote Originally Posted by kalagota View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by Jhevon View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by JaneBennet View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by JaneBennet View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by Jhevon View Post
    did you mean to consider m | b \mbox{ and } m \nmid b?
    Yes, youíre right. Sorry, my mistake.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 6th 2010, 03:03 PM
  2. Replies: 0
    Last Post: April 23rd 2010, 11:37 PM
  3. abstract algebra!
    Posted in the Advanced Algebra Forum
    Replies: 9
    Last Post: March 10th 2010, 05:54 PM
  4. Abstract Algebra: Congruence and The Division Algorithm 1
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 18th 2008, 11:13 AM
  5. Replies: 2
    Last Post: February 16th 2008, 02:30 PM

Search Tags


/mathhelpforum @mathhelpforum