Results 1 to 4 of 4

Math Help - Question to do with congreuncy

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    50

    Question to do with congreuncy

    Hi, i need help with the following question.
    Let a,b\in\mathbb{Z}and n\in\mathbb{N}. Set d=gcd(a,n).If d\nmid b then prove that ax\equiv b(modn)has no integer solutions for x.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2
    You're given ax-mn=b for some integral m. d divides the LHS, but not the RHS, which is impossible for integral a,x,m,n & b.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by cooltowns View Post
    Hi, i need help with the following question.
    Let a,b\in\mathbb{Z}and n\in\mathbb{N}. Set d=gcd(a,n).If d\nmid b then prove that ax\equiv b(modn)has no integer solutions for x.
    Suppose towards a contradiction that ax\equiv b\mod n has an integer solution.

    Then n\big|(ax-b) and d\big|(ax-b), such that

    ax\equiv b\mod d and 0\equiv b\mod d,

    meaning d\big|b, which is a contradiction.

    EDIT: Ah, qmech beat me to it!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Mar 2009
    Posts
    50
    thank you.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum