Results 1 to 4 of 4

Thread: Question to do with congreuncy

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    66

    Question to do with congreuncy

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

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    283
    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 $\displaystyle a,b\in\mathbb{Z}$and $\displaystyle n\in\mathbb{N}$. Set $\displaystyle d=gcd(a,n)$.If $\displaystyle d\nmid b$ then prove that $\displaystyle ax\equiv b(modn)$has no integer solutions for $\displaystyle x$.
    Suppose towards a contradiction that $\displaystyle ax\equiv b\mod n$ has an integer solution.

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

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

    meaning $\displaystyle 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
    66
    thank you.
    Follow Math Help Forum on Facebook and Google+

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum